프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #33

지난주 일요일 4월 16일이 S사 시험이었지요?

  

시험을 다들 잘 보셨나요? 재수?를 하지 않으면 1번만 보는 시험이니 시험을 보시고 나면 다시 이걸 보실 필요는 없을 것 같기는 하지만 하반기도 있으니 기출 문제는 잘 정리를 해두어야지요.

모든 시험의 기본은 기출문제이니 기출문제를 잘 찾아보세요.

구글과 네이버에서 검색하면서 날짜를 조정을 잘하면 쉽게 찾아 보실 수 도 있습니다. 잘 정리된 곳도 있구요.

 

이게 그룹공채는 없어진다고 하고 회사별로 수시로 본다고 하는데 그러면 여러번 보시는 분들도 생길 것 같습니다.

시험 바뀐지 얼마 안되었기 때문에 쉽게 바뀔 것 같지 않고 회사에 안에서 화이트 보드에 알고리즘을 물어볼 수 있는

분을 모든 응시생에게 붙일 수 도 없고

 

몇개의 후기를 봤는데 이번 시험 후기를 보면서 알게 된 것이 아래와 같습니다.

 

1) STL 라이브러리를 사용할 수 있다.

   STL를 쓰게되면 기본 코드를 외울 필요가 없고 사용법만 익히면 됩니다.

  

2) 1번과 2번 문제의 구분이 없어졌다.

    지난번 까지는 1번은 간단한 게임류 2번은 알고리즘에 가까운 문제 였는데 이번 시험에는

    모두 예전 2번과 같은 형태의 문제였습니다.

  

3) 대부분 최대/최소 문제였지요. 경우의 수도 완전탐색으로 풀수 있을 정도였구요.

    DP로 풀었다고 된 것도 그냥 완전 탐색으로 풀 수 있을 것이지만 간단한 DP까지는

    공부해 두는 것이 좋습니다. 너무 명확하나 것을 완전탐색으로 풀면 시간도 많이 걸리고

   

4) 작년 후기에는 잘?본사람은 나중에 다시 불러서 한번 더 보게 한다고 합니다.

    (더 어려운 문제인가요?)

  

후기는 구글과 네이버에서 날짜를 잘 맞추면서 찾으면 쉽게 찾을 수 있습니다. 잘 정리된 곳도 있고요.

  

그 중 문제 하나를 생각해보면 오전인지 오후였는지 모르곘는데 여기에 자세히 쓸 수 는 없지만 찾아서 풀어보시고 나서

아래는 읽어보세요.

  

후기중에 2차원 배열중에서 4개의 면이 이어진 도형이 차지하는 부분의 숫자 합의 최대값을 물어본 것이 있었는데.

접근하는 생각의 흐름이 이럴 수 있을 것 같습니다. 

 

1) 큰 숫자들이 모여있는 곳을 찾아서 큰 숫자들을 연결하여 이어진 도형이면 그것을 답으로 하자

    > 사람이라면 보통 이렇게 하겠죠, 전체 숫자들을 보고 큰 수들을 이어보고 모두 연결되어 있으면 선택하 수 있습니다.

       그것이 최대값인지는 알 수 없는 것이지요.

  

2) 전체 탐색을 해야 한다면 (NxM)C4를 뽑아서 뽑힌 4개가 서로 연결되어 있는지 확인하고 연결되어 있으면 4개의 좌표

     에 해당하는 수를 더해서 가장 큰값을 구함

     이 경우 NxM 이 작은 수이면 가능합니다. 또한 서로 연결되어 있는지에 대한 판단방법은 생각해 봐야 겠지요.

 

3) 4개가 붙어 있는 테트리스 같은 모양을 미리 구해 놓고 그 도형을 모든 지점에 놓아 보고 값을 구해 최대값을 구함

   주의 할 것은 도형의 모양이 0도 90도 180도 270도 돌린 것 처럼 4배가 나오는 것이 있기도 하고

   어떤 것은 돌릴 필요가 없는 것도 있고 90 돌린 것도 있는데 이렇게 어려가지를 생각할 수 있도 있지만

   경우의 수를 구하는 것이 아니라 최대값을 구하는 것이므로 모든 도형을 0 90 180 270 도 돌린다고 생각하면 더 쉬울 수 도 있고

   미리 돌린 모든 좌표의 경우를 구한 테이블을 움직이면 쉽게 구할 수 있음

  

4) 이런 종류의 문제는 NxM 배열을 잡는 것 보다 (N+4)x(M+4) 배열을 잡는 것이 더 쉽게 풀릴 수 있습니다.

    NxM 밖의 부분은 -1000 씩 채워두고

  

이 문제는 STL 같은 라이브러리 도움을 받거나 기본 코드도 필요없는 앞에서 했던 2차원 배열의 완전탐색의 변형으로 볼 수 있을 것 같습니다.

 

 

#삼성_소프트웨어_역량_테스트