dbfs 외 기타 재귀 (분할정복, 백트래킹 등)

코템보단 대회에서 더많이본것같은데, 1182.

 

카카오 2020 기출: https://programmers.co.kr/learn/courses/30/lessons/60058

와 진짜 재귀로선 난이도 너무 극악이었음 내겐... 겨우 풀었다 한 3일 소요? 여태 풀어봤던 재귀 중 가장 헷갈리고 별 희한한 재귀 다 들어간다고 생각한 아이임

수도코드 설명 부분이 뭔말인지 못알아먹겠고 지금도 사실 완전힌 몰겠어서 이해못한채 그냥 써있는 대로 코딩하는 능력을 기르는 문제였음

다행히 맞았고... 평소 풀던 스탈대로 풀었

다만 최고 투표수 풀이(폴더엔 4_1로 복붙저장)는 solution 함수를 재귀하는 방식을 이용했고 나의 더티 코드를 이렇게 바꾸면 되겠구나 하고 학습하면 된다.

*유사문제: 리트코드 2116(자료구조란에 회고 넣어둠)

 

- 1780: https://www.acmicpc.net/problem/1780

쉬운 문제지.. 그치만 감도 좀 떨어지고, 더 안 복잡하고 예쁘게 풀어야 한다는 강박이 생기기도 했고, 오히려 쉬운 문제니까 그냥 최상위 풀이 보고 공부함. 이런 경우 어떻게 코드 짰을 때 풀이 시간 짧게 나오는지 1780_1 통해 공부할 수 있다.!

 

 

- 11729: https://www.acmicpc.net/problem/11729

점화식을 기억하면 더 의미가 있고, 문제를 어떻게 쪼개 생각하는지 사고를 배우기 좋다. 블로그 풀이까지만 보고 상위권 풀이는 안봄

 

 

- 16987: https://www.acmicpc.net/problem/16987

국어가 막혀서 안풀리는 문제.. 그게 안되면 문제 그대로 코드로 옮기면 되는데, 그것마저 안돼서 코드 읽고 문제를 역으로 이해했는데 그것도 한 부분 이해 안됨... 코드에 일일이 설명 달아준: https://velog.io/@yoonuk/%EB%B0%B1%EC%A4%80-16987-%EA%B3%84%EB%9E%80%EC%9C%BC%EB%A1%9C-%EA%B3%84%EB%9E%80%EC%B9%98%EA%B8%B0-Java%EC%9E%90%EB%B0%94

여기서 "타겟이 된 계란 깨지면 cnt++" 하는 부분 이해 안됨

 

- 14712: https://www.acmicpc.net/problem/14712

"판의 네모를 포함할 때 현재 네모의 위치의 왼쪽, 위쪽, 좌상단 네모가 하나라도 없어야 2 X 2가 되지 않으므로 포함시킨 후 다음 네모로 이동할 수 있다"

요거 하나 때문에 (도저히 몰겠어서) 이런저런 풀이를 찾아봤었다. 저 풀이 아이디어가 이해 안돼서 한참 헤맸는데 드디어 무슨말인지 알겠다. 이해 안됐던 이유는, 생각해보면 한 위치에 대해 2*2 존재 여부 확인을 위해 검사할 위치가 너무 많지 않냐는 거였다. 근데 그래프 탐색 방법, 로직을 생각해보니, 우측&아래로만 나가지 위쪽&좌측으로는 뻗지 않도록 설계돼있단 점에서, 한 위치의 오른쪽, 우하단, 우상단 등에는 노드가 존재할 수가 없다는 거... 진짜 그런가? 생각해보니 좌측&위쪾은 진짜 안가나..? 언젠가부터 이거 안가도 되는 뭔가 있었던것 같은데...

[참고했던 풀이글 목록]

https://velog.io/@qkralsgud1324/Python-%EB%B0%B1%EC%A4%80-14712-%EB%84%B4%EB%AA%A8%EB%84%B4%EB%AA%A8Easy

https://velog.io/@silver_star/%EB%B0%B1%EC%A4%80-14712-%EB%84%B4%EB%AA%A8%EB%84%B4%EB%AA%A8-Easy-Backtracking-Brute-Force

https://rudyprogramming.tistory.com/124