문제 링크는 따로 걸지 않겠다. 어차피 구름 로그인해서 풀어야하는 문제라서.
나는 코스프로는 사실 존재만 알고잇었다. 그런 코딩 자격증 같은게 있고, 평소에 코딩테스트 연습을 열심히 했다면 쉽게 풀 수 있을 거라는 말들을 많이 들어서 신경 안 쓰고 있었다.
그리고 프로그래머스에 있는 기출을 먼저 풀어보니까 유형에만 익숙해지면 쉽게 풀 수 있을 것 같다는 생각을 했고, (알고리즘 자체가 쉽다) 천천히 공부했다. 그런데 웬걸, 구름에 있는걸 풀어보니까 프로그래머스거 만큼 쉽지가 않았다 ^^;;
특히 이 소용돌이 수 라는 문제는 어떻게 풀지 알 것 같으면서도 정말 이렇게 복잡하게 풀어야한다고?하는 생각이 들어서 20분 가량 소요하면서.. 쉽게 푸는 방법을 알아냈다. 근데 이상한 방식으로 풀려고 하다보니까 머리가 터질거같아서 일단 넘기고 다른 문제들을 먼저 풀었다. 60분안에 10문제를 다 풀려다가 75분 걸려서 9문제를 풀고 다시 이 문제로 넘어왔다. 그리고 노트를 꺼내서 규칙을 다시 적은 후에야 쉬운 풀이를 찾을 수 있었다.
이 풀이를 정리한 몇몇 블로그 글이 있어서 봤는데 내가 처음에 구현하려고 했던 것처럼 dir = [[0, 1] ..]을 써서 계속해서 방향을 바꿔주면서 풀었다. 그리고 어느 블로그에서는 심지어 공식 답변이라며 써놓은 코드가 있었는데 그 코드도 이렇게 푸는게 맞다고 써있다. 그런데 사실 아마도 문제의 출제자는 그걸 의도하고 출제를 한게 아닐지도?
왜냐면 재귀를 사용하면 엄청나게 쉽게 풀 수 있는 문제니까. 나도 재귀라는걸 생각하는 과정이 오래걸렸지, 막상 재귀구나! 하고 나니까 엄청나게 쉬운 문제라는걸 알 수 있었다.
왼쪽은 n = 3일때의 모양이고, 오른쪽은 n = 5일때 모양이다. 잘 보면 n = 5 소용돌이의 가운데 3*3행렬은 n = 3 행렬에서 모든 값에 16을 더한 값과 같다. 재귀라는 뜻.
따라서 n = 5일때 위 문제의 답은
양 끝 값, 1 + 9 (= 5*2) 에 +
17 + 25 + 21인데 이는 1+ 9+ 5 +16*3 (n = 3인 경우의 답 + 16 * 3) 이다.
이 규칙을 잘 찾아보면 solution(n) 함수의 답은 n*2 + (n-1)*4*(n-2) + solution(n-2)이다.
n = 1인 경우, n = 2인 경우만 예외처리를 해서 함수를 종료시키면 문제 끝.
답은 아래와 같다.
def solution(n):
answer = 0
if n == 1:
return 1
if n == 2:
return 4
else:
answer = n*2 + (n-1)*4*(n-2) + solution(n-2)
return answer
print(solution(6))사실 나는 이게 맞는 풀이라고 생각을 하는데 다른 블로그에서 '오피셜' 풀이라고 올라온게 있다보니까 비교를 해보지 않을 수 없었다. 문제 조건에 1~100까지 n값이 주어진다기에 공식 풀이와 값을 비교했는데 값은 모두 같다.
공식 풀이라고 올라온게 정말 출제자가 원했던 풀이 방식이 맞을까..싶다. 물론 그것도 훌륭한 풀이이고.. 좋지만.. 이렇게 쉽게 푸는 방법이 있는데. 나도 이렇게 푸는게 오래걸렸지만, 앞으로는 cos pro문제는 어렵게 생각하지 않고 기초적인 풀이방법을 활용할 수 있는지를 먼저 생각해봐야 할 것 같다.
여담.
코스프로가 조금.. 아무래도 개발자들은 굳이 이걸로 시작하진 않을 것 같고 비개발자들이 자격증 느낌으로 따려고 하는 사람들이 많은 것 같다. 인터넷에 있는 풀이 들을 봤을 때 지금 나 처럼 푼 사람이 없는 것 같은데, 아무리 봐도 이건 이런식으로 푸는 문제가 맞으며 다른 코테 준비좀 했다 싶은 개발자들이 이 문제를 봤다면 나처럼 재귀로 푸는 방법을 생각하지 않았을 리 없다.
만약 이 글을 보는 사람중에 정말로 자기가 코스 프로만 따야지~ 하는 마음으로 코딩테스트를 공부하는 사람이 있다면 그건 방법이 조금 잘못됐다고 말해주고 싶습니다. cos pro로 공부하면 좋은 코드를 보기는 힘들겁니다..! 여기저기 배열 옮겨다니면서 문제 푸는거, 틀린건 아니지만 재귀로 풀면 몇줄 안으로 끝나는 문제는 재귀로 푸는게 더... '파이썬 알고리즘 인터뷰'라는 책의 표현을 빌리자면, 우아하다고 볼 수 잇겠죠. 코스프로 시험 시간을 생각해봤을 때 이 문제는 재귀로 푸는게 맞는 것 같아요. 근데 코스 프로가 워낙 아직까지는 비주류느낌이다보니까 좋은 풀이를 올린 블로그가 없어서 그냥 cos pro만 딸려고 공부하는 분들은 더 좋은 코딩을 배울 수가 없을 것 같습니다. 그냥 이 말이 누군가에겐 도움이 됐으면 좋겠습니다 .. 혼자 풀어보고 좋은 풀이도 보고 하면서 공부하려면 다른 훌륭한 소스들이 많다는 거죠…!
이제와서 보니 반복이나 dp로 풀어도될듯 ?