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

많은 문제가 "전처리" + "모든 경우 탐색" + "조건확인" 이런 식으로 되었다고 말씀을 드렸는데

"전처리"에 해당하기도 하고 가벼운 퀴즈/퍼즐에도 사용되는 것이 있습니다.

 

예를 들어 특정 변화를 보여주고 일정 시간 후에 변화된 상태를 묻는 경우가 있습니다.

이 일정 시간이 100처럼 for문을 돌려서 해볼만한 것도 있고 1000000000 처럼 무지 큰값을 주는 경우도 있는데

이런 경우는 for문을 돌리지 말라는 뜻이겠죠?

 

1. NxN 배열의 1초일때 (1, 1)에 있을때 계속 해서 대각선 아래로 이동한다고 하고 경계를 넘으면 다음 줄로 이동 할때

    1초 1,1

    2초 2,1

    3초 1,2

    4초 3,1

    5초 2,2

    6초 1,3

    ......

          n,n

          1,1

    그림이면 쉬운데 글로는 어렵네요.

    10000000000초 후에 위치는?

 

    

 

힌트는 NxN 초 후에는 다시 돌아오니 10000000000%(NxN) 만 따지면 됩니다.

이것도 대각선이니 조금 처리가 필요합니다.

아마 이동이 대각선이 아니라 수평이나 수직 방향이었으면 좀 더 쉽게 생각을 할 수 도 있었을거에요.

 

이런 종류가 나온 책이 번역본은 없던데 아마존에서 algorithm quiz나 Algorithm puzzle을 찾아보면

기본적인 형태의 문제가 많이 있습니다. 

 

보통 문제가 여기서 끝나지 않고 이것은 전처리이고 그 후 다른 문제가 겹쳐지는 경우도 많이 있습니다.

 

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