0) 들어가기 앞서
지난 4주차에 학습하던 IL단계의 DFS/BFS유형을 완료하지 못했다. BFS의 돌 잘 치우기 문항부터 고전중이다.
1) 실력 진단 결과
DP 문항을 접하고 테스트케이스 까진 통과하였으나 제출에서 실패하였다. (맞왜틀🤔?) 실력 진단 결과에 따라 이번 주차는 DP유형을 학습한다!
리뷰
- 중복 순열
from itertools import product
_list = product([1,2,3], repeat=3)
print(*_list)- 정수형 튜플을 하나의 문자열로 합쳐서 반환
tup = (1, 2, 3)
s = ''.join(map(str, tup))
print(s) # 1232) DP
지금까지의 유형중 가장 많은 해설을 열어봐야 했으며 그 때문인지 가장 집중하지 못한 유형이었다. 다음주차도 DP 유형을 학습할 것 같다.
문제1
사각형 채우기 3(링크 : https://www.codetree.ai/missions/2/problems/rectangle-fill-3?&utm_source=clipboard&utm_medium=text)
리뷰
- 1X1 타일이 주어지면서 부터
dp[i-1], dp[i-2]만 고려해선 안되었다.
문제2
정수 사각형 최솟값의 최댓값(링크 : https://www.codetree.ai/missions/2/problems/maximin-path-in-square?&utm_source=clipboard&utm_medium=text)
리뷰
- 0행 및 0열은 제공된 해설과 동일하게 초기화 하였다.
- 점화식을 세우는데 어려움을 겪었다. 문제를 충분히 이해하지 않고 코드를 바로 작성하는 경향이 문제였던 것 같다.
문제3
정수 사각형 최장 증가 수열(링크 : https://www.codetree.ai/missions/2/problems/lis-on-the-integer-grid?&utm_source=clipboard&utm_medium=text)
리뷰
- 재귀함수를 이용해 접근했다. dx/dy 기법을 이용해 next_x, next_y 의 위치가 격자 범위 밖이거나, 이미 탐색한 위치이거나, 증가하는 수열이 아닌 경우 탐색을 중단했다. 그러나 왜 테스트케이스 에서 시간초과가 발생하는지 의문이다.
- 아래 캡처의 좌측은 나의 풀이, 우측은 타인의 풀이이다.
- 다음 두 가지 의문이 생겨 토론 탭 질문을 이용해 해소하였다.
- 테스트케이스 3번에서 시간초과가 발생하는 이유가 이미 탐색한 결과를 반환하지 않았기 때문인지
- 나의 풀이는 visited 배열을 활용해 Memoization을 적용했으나, 모든 (i,j)에 대하여 DFS 탐색이 이루어져 이중for문 O(n^2) * DFS탐색 O(n^2) → O(n^4) 시간복잡도가 발생한다.
- 타인의 풀이는 dp 배열의 (i,j) 좌표에 이미 탐색한 값이 저장되어 있으면 탐색을 중단한다. 즉, 모든 (i,j) 좌표에 대하여 1번의 탐색만 수행된다. 따라서 이중for문 O(n^2) * DFS탐색 O(1) → O(n^2) 시간복잡도가 발생한다.
- 23번째 라인에서 max_cnt = max(max_cnt, 1 + dfs(nx, ny)) 이미 1에서 카운팅이 시작되는데도 출력 시 1을 더해주어야 하는 이유가 무엇인지.
시작위치에 대한 경우가 처리되어있지 않아서 그렇습니다. main의 (i, j)에서 시작했으니 해당 칸이 포함되어야 합니다 :)라는 답변을 받았다.
- 테스트케이스 3번에서 시간초과가 발생하는 이유가 이미 탐색한 결과를 반환하지 않았기 때문인지
공룡, 다람쥐 그리고 돌고래!