오랜만에 알고리즘 문제를 풀고자 한다. 어떤 문제를 풀지 고민하던 도중, solved.ac에서 내가 푼문제들의 종류를 보여주는 그림을 보았다.
수학과 구현 관련 문제는 여럿 풀었으나 다른 유형의 문제들은 취약하다는 걸 깨달았다. 특히 그래프 관련 문제는 하나도 풀지 않았더라. 실제로 학교에서 알고리즘 수업을 들을 때도 이 파트에서 시험을 잘 못 봤던 거로 기억한다...
적절한 난이도로 찾아보다가 실버4 수준의 문제 '점프왕 쩰리'를 골랐다.
문제는 위치를 찾아가는 단순한 유형이다. 어째 교내 코딩테스트 할 때 풀어본 거 같은 st
얼렁뚱땅 처음 쓴 코드는
이따위 코드. 이건 진짜 하나부터 열까지 잘못 짰다. 이건 i,j가 모든 영역을 탐색하는데 이러면 안 되고 이동했을 경우 이동한 위치의 i,j만 탐색해야한다는 점을 잊어버리고 짠 코드이다. 나는 바보다.
이 코드가 그렇게 2번째(사실 한 4번째 정도) 수정한 코드인데 이 코드의 문제점은 바로 2번째 elif 문이다. i+move와 j+move가 모두 n보다 작은 경우, i에 move를 더하는 행 이동을 선택하였는데, 이 점이 문제가 될 수 있다.
왜냐하면
3
1 10 10
1 1 1
10 10 -1
이와 같은 경우, (0,0), (1,0) 자리에서 모두 위에 말한 조건에 걸리게 되는데 (0,0)에서는 문제가 없다. 하지만 (1,0)에서 열 이동이 아닌 행 이동을 택하게 될 경우 -1을 찾을 수 없지만, 열 이동을 먼저 택한다면 -1을 찾을 수 있기 때문이다. 이와 같은 상황을 어떻게 해결할 수 있을까?
안에 이렇게 더 세부적인 조건을 주었다. 한 번 제출하여 보자!
64%까지 채점하길래 기대했건만 웬 시간초과... 장난하냐
진정하고 조건을 다시 살펴보자
n이 2 혹은 3이라는 간단한 조건임을 확인하여 반례를 직접 찾아보고자 하였다.
바로 찾았지롱
이 문제는 어디서 생겼냐면 아까와 추가로 준 조건 때문이다. 왜냐하면 여기서 (1,1)의 경우 행 이동을 하여도, 열 이동을 하여도 상관이 없으나 그런 경우에는 이동을 하지 못 하기 때문이다.
조건을 살짝 수정해주었다. 위에서는 미리 열 이동을 해보고 문제가 발생할 시에만 행 이동을 해주었는데 그 부분을 지워
행 이동 시 문제가 있을 때는 열 이동, 그렇지 않은 상황에는 모두 행 이동을 하게끔 변경하였다.
그만 틀려줘... 나 슬펑
근데 내가 뭐가 부족한지는 확실히 알 수 있었다. 이상하게 수업 시간에 비슷한 그래프 탐색 문제를 풀어보고 다양한 방법으로 풀이해본 것 같은데 생각이 안 난단 말이지.
오늘은 이만 풀고 그걸 복습하는 방향으로 생각해보아야겠다.
관련 이론들... 들어봤지만 다 너무 오랜만인걸 공부해야지 아자 아자
