[코드트리 조별과제] 4주차 레포트

 

코드트리 4주차다. 이번 주도 DP 위주로만 풀이했다.

> 문제 풀이

# DP

📝 서로 다른 BST 개수 세기 - https://www.codetree.ai/missions/2/problems/number-of-unique-bst/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

정답률 49% 제출 974회 예상 소요 시간 100분

BST란 자식을 2개 이하로 갖는 이진 탐색 트리입니다. 각 노드마다 왼쪽에 있는 모든 노드들의 값이 해당 노드의 값 보다 작아야 하고, 오른쪽에 있는 모든 노드들의 값이 해당 노드의 값 보다 커야 합니다.
1부터 N까지의 숫자들을 단 한 번씩만 써서 만들 수 있는 노드의 개수가 N인 서로 다른 이진 탐색 트리 개수를 세는 프로그램을 작성해보세요.

 
입력 예제

3

 
 
출력 예제

5

 
제출 결과

 
코멘트

- BST의 루트 값을 잡는 순간, 왼쪽에 올 수 있는 값들과 오른쪽에 올 수 있는 값들이 정해진다.

- 이로 인해 왼쪽 서브트리과 오른쪽 서브트리 간의 상관관계가 완전히 끊어지게 된다.

- BST의 특성상 왼쪽 서브트리와 오른쪽 서브트리 또한 BST여야만 한다.

- 그룹들은 독립적이다 + 서브트리들은 BST이다 -> 이전에 미리 구한 노드 수가 적은 BST의 경우의 수를 그대로 활용하면 된다.

- 작은 크기의 BST부터 루트에 위치 가능한 모든 값들의 각 경우의 수를 합치면 최종 경우의 수가 나온다.

- 정리해보자면, N개의 값중 i라는 값을 루트로 잡으면 'i-1개의 노드를 가진 왼쪽 서브트리' + 'N-i개의 노드를 가진 오른쪽 서브트리'가 된다.

 

📝 정수 사각형 최장 증가 수열 - https://www.codetree.ai/missions/2/problems/lis-on-the-integer-grid/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

정답률 44% 제출 926회 예상 소요 시간 172분

n×n 크기의 격자 정보가 주어졌을 때, 시작점을 적절하게 잡아 상하좌우로 인접한 칸으로 계속 칸에 적혀있는 정수값이 커지도록 이동한다고 했을 때 밟고 지나갈 수 있는 최대 칸의 수를 구하는 프로그램을 작성해보세요.

 
입력 예제

3
2 2 1
3 1 2
4 1 2

 
 
출력 예제

35

 
제출 결과

1)

2)

 
코멘트

- 전형적인 메모리제이션 활용 문제다.

- 조건에 맞는 즉, 현재 값보다 더 큰 인접칸들로 갈 수 있는 모든 길을 탐색하고 그 중 가장 큰 값이 현재 칸의 최대 칸 수이다.

- 갈 수 있는 최대한의 길들을 끝까지 가보고 다시 돌아오면서 정보들을 취합하고 그 중 가장 큰 값들을 다시 모아오며 비교하는 방식을 반복해야하기 때문에 재귀로 구현한 dfs를 활용했다.

- 큰 값을 찾기 위해 방문한 칸들도 다시 돌아오는 과정에서 자연스럽게 그 칸들의 최대 칸 수를 구할 수 있다.

- 따라서 돌아오는 길에 값들을 미리 저장해 두면 탐색 횟수를 현저하게 줄일 수 있다.

하지만, 현 문제의 테스트 케이스는 미흡한 부분이 있다.

1)번 풀이의 경우 시간은 더 걸렸지만 솔브에 성공한 방법인데, 실수로 돌아오며 방문한 칸들의 최대 칸을 저장하는 한 줄을 빼먹어버렸고, 시간 초과가 뜨게 되었다. 하지만 실수를 인지하지 못하고, '이래도 통과가 안되네? 그럼 가장 값이 작은 칸들이 큰 값들 보다는 비교적 많은 칸들을 거치게 될 것이고, 그만큼 미리 저장되는 값들이 많아지지 않을까?'라는 생각으로 격자의 칸들을 정렬해서 dfs를 시도했는데 통과해버렸다. 개인적인 생각으론 시작 칸의 최대 칸 수만 저장하는, 절대 통과하면 안되는 코드인데 입력을 정렬했다는 이유로 통과한 것을 보면 테스트 케이스가 미흡한 것으로 추정된다.