[BOJ] 좋은수열_2661

 

 

이 문제는 내 힘으로 풀지 못하였다.

요 몇일 백트래킹 문제를 풀고 있는데, 내가 이 개념을 아는 줄 알았는데 잘 모르는 것 같다.

이 상태로 문제를 더 푸는건 의미가 없는 것 같다.

여기서 바로 잡고 가자. 재귀와 basecase를 어떻게 활용하는지 공부해보자.

 

재귀와 base case를 공부하여 밑에 정리하고 왔다.

조금은 보이지 않던 것들이 보이는 것 같다.

그래도 다시 흠칫하는 것은, data[-i:] == data[-i*2:-i]부분이다.

나라면 길이가 if cnt == n이 된다면 이때 판별할 것 같았다. 하지만 이렇게 되면 길이가 n이 될떄까지의 모든 경우의 수를 다 구해놓고, 나쁜 수열이 된다면 버려야 한다. 즉, 소모가 매우 크다.

data[-i:] == data[-i*2:-i] -> 이 생각을 어찌했을지 신기하다... 대충 보면 "음 그렇구나"싶지만 더 자세히 들여다 봤을 때, 와 이것까지 다 고려가 된 것이구나 싶다. ( 1. 위에 bold칠한 부분, 2. 이렇게 하면 이중 for문을 하지 않고도 판별할 수 있다. 왜냐면 쌓일 때 마다 검사하니까,,,).

 

 

 

 

 

 

 

-- 공부한 내용 정리 -- 

재귀함수는 Base case를 잘 지정해야 한다.

재귀함수의 무한루프를 막아주는 것이 Base case이다.

그렇다면 어떻게 Base case를 잡아줘야할까?

 

Base case

모든 재귀함수는 반복문으로 설계가 가능하고, 그 반대도 가능하다.

그렇다면 Base case는 원하는 상태가 되었을 때, 더 반복하지 않고 멈추기 위해 걸어줘야 하지 않을까?

위 문제를 보았을 때, if cnt == n으로 Base case를 잡았다. 즉, 원하는 조건이 충족되었을 떄 멈추는 것이다.

 

 

Recursive case

나는 Base case보다도 Recursive case부분이 더 어렵게 느껴졌다.

단순히 재귀호출 부분만 신경쓸게 아니라, 그 이후의 부분도 상당히 생각을 많이 해야 했기 때문이다.

위 문제 답 코드에서는 data.pop()이 해당된다.

이게 무슨 의미일까??

 

마지막에 Hi 0까지 있다.

위 예시가 내가 헷갈려 했던 부분들이다. Hello 0부터 시작해서 4까지 실행한 후, 재귀호출 뒤에 문장들은 4부터 시작해 0로 끝나게 된다.

 

이를 활용한 예시가 있다.

이 코드인데, 쉽게 볼 수 있는 dfs문제 코드이다.

 

왜 for i in range(n)일까?
-> 각 칸마다 0~n까지의 모든 경우의 수를 고려해 주기 위해서이다.
1, 1, 1, 1, 1 -> 이게 첫번째이다.
그다음은 1, 1, 1, 1, 2 (하지만 이거 딱 시작하기 이전에는 1, 1, 1, 1, 1 뒤의 코드가 먼저 실행된 후 처리된다.
여기서 1, 1, 1, 1, 1 뒤에 코드는 visited[i] = 0이므로 맨 마지막이 다시 방문되지 않음으로 처리된 후, 1, 1, 1, 1, 2 가 처리될 수 있다.