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

 

어느덧 5주차다 조별과제 이벤트도 얼마남지 않았다.

기간이 길지 않아서 DP를 졸업하겠다는 마인드로 계속해서 풀고 있다.

 

> 문제 풀이

# DP

📝 2차원 최대 증가 수열 - https://www.codetree.ai/missions/2/problems/longest-increasing-sequence-2d/description

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

 

문제

정답률 40% 제출 615회 예상 소요 시간 84분

n * m 크기인 직사각형의 각 칸에 수들이 하나씩 적혀있습니다. 왼쪽 상단 (1, 1)에서 출발한다고 헀을 때 특정 룰을 만족하면서 밟을 수 있는 칸의 최대 수를 구하는 프로그램을 작성해보세요.
아래는 특정 룰에 대한 설명입니다.
1. 이동은 항상 점프를 통해서만 가능합니다. 또, 점프 진행시 항상 현재 위치에 적혀있는 수보다, 점프한 이후의 칸에 적혀있는 수가 더 커야만 합니다.
2. 점프 진행시 현재 위치에서 적어도 한칸 이상 오른쪽에 있는 위치이며 동시에 현재 위치에서 적어도 한칸 이상 아래쪽에 있는 위치인 곳으로만 점프가 가능합니다.

 
입력 예제

4 4
1 1 1 1
1 1 1 3
1 4 5 2
1 1 2 5

 
 
출력 예제

3

 
제출 결과

 
코멘트

- 다소 충격적이었다.

- 당연히 for문을 4번 돌리면 안 된다는 생각에 큐를 이용하여 n^3 안에 끝내보고자 했다. 하지만 큐안에 들어가는 노드의 중복을 막을 조건이 없었고, 결국 시간초과가 뜨게 되었다.

- 밑져야 본전이라는 마음으로 넣은 n^4짜리 코드가 통과가 돼서 허탈했다.

- 팁을 말해보자면, 시작지점부터 이어져있는지와 이전 노드와 행, 열이 같지 않은지를 잘 처리해야 한다.

 

 

📝 증가했다가 감소하는 부분 수열 - https://www.codetree.ai/missions/2/problems/increasing-and-descreasing-subsequence/description

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

 

문제

정답률 57% 제출 272회 예상 소요 시간 132분

N개의 숫자가 주어졌을 때, 가장 긴 증가-감소 부분 수열의 길이를 구하는 프로그램을 작성해보세요.
부분 수열이란 수열의 원소들 중 임의로 몇 개를 골라 순서대로 나열한 수열을 의미합니다. 증가-감소 부분수열은 순서대로 나열했을 때 원소들이 계속 증가하다가 특정 순간부터는 계속 감소하기 시작하는 수열을 증가-감소 부분 수열이라고 합니다. 단, 처음부터 끝까지 계속 증가만 하거나 계속 감소만 하는 부분수열 역시 증가-감소 부분수열임에 유의합니다.
예를 들어, N=7, 주어진 수열이 1,4,2,5,6,2,1 이라 했을 때
2,4,5,2는 순서대로 나열해 만들 수 없으므로 부분 수열이라 할 수 없습니다.
1,4,2,5는 부분 수열 이지만 증가, 감소 후 다시 값이 증가하였기에 증가-감소 부분 수열이 아닙니다.
1,4,5는 부분 수열이고 증가만 일어났기에 증가-감소 부분 수열입니다.
4,2는 부분 수열이고 감소만 일어났기에 증가-감소 부분 수열입니다.
1,2,5,6,2,1은 계속 증가하다가 6에서부터 계속 감소만 하기에 증가-감소 부분 수열 입니다.

 
입력 예제

7
1 4 2 5 6 2 1

 
 
출력 예제

6

 
제출 결과

 
코멘트

- 생각보다 풀이법이 간단한 문제이다.

- 하나의 dp 배열에서 증가와 감소의 가장 긴 길이를 구하는 것이 아닌, 두 번에 나눠서 구하고 합친다는 생각으로 접근하면 된다.

- 먼저 왼쪽부터 각 위치에서 가장 긴 증가하는 수열의 길이를 구하고, 방향을 바꾸어 오른쪽부터 각 위치에서 가장 긴 증가하는 수열의 길이를 저장한다. 그 뒤 각 위치에서의 두 값을 더한 뒤 1을 빼면(기준 값이 중복) 기준 위치에서의 가장 긴 증가-감소 부분 수열의 길이를 구할 수 있다.

 

 

📝 신전 탐험하기 - https://www.codetree.ai/missions/2/problems/explore-temple/description

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

 

문제

정답률 82% 제출 51회 예상 소요 시간 측정 불가

신전은 n층으로 이루어져 있습니다. 각 층에는 왼쪽, 가운데, 오른쪽 세 개의 방이 있으며 이 중 하나의 방만을 들어가 그 방 안에 있는 보물을 가져갈 수 있습니다.
신전에는 특이한 장치가 있어서, 바로 직전 층에서 들어갔던 방향의 방을 한번 더 들어가면, 예를 들어 3층에서 오른쪽 방을 들어갔는데 4층에서도 오른쪽 방을 들어갈 경우 위험 장치가 발동해 쫓겨납니다.
남우는 1층부터 시작해서 n층까지 차례대로 올라가면서 방을 들어가되, 쫓겨나지 않고 최대한 많은 보물을 가져가고자 합니다. 남우가 가져갈 수 있는 보물의 최대 개수를 구하는 프로그램을 작성하세요.

 
입력 예제

2
10 9 8
10 7 6

 
 
출력 예제

19

 
제출 결과

 
코멘트

- 쉬운 문제이다.

- 그냥 3xn짜리 dp 배열을 만든 뒤, 이전 값에서 현재 방향과 동일한 값을 제외한 두 값 중 큰 값을 채택하는 방식으로 채워나가면 된다.

 

 

📝 신전 탐험하기2 - https://www.codetree.ai/missions/2/problems/explore-temple-2/description

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

 

문제

정답률 63% 제출 57회 예상 소요 시간 측정 불가

신전은 n층으로 이루어져 있습니다. 각 층에는 왼쪽, 가운데, 오른쪽 세 개의 방이 있으며 이 중 하나의 방만을 들어가 그 방 안에 있는 보물을 가져갈 수 있습니다.
신전에는 특이한 장치가 있어서, 바로 직전 층에서 들어갔던 방향의 방을 한번 더 들어가면, 예를 들어 3층에서 오른쪽 방을 들어갔는데 4층에서도 오른쪽 방을 들어갈 경우 위험 장치가 발동해 쫓겨납니다.
또한 꼭대기 층인 n층에서는 한가지의 장치가 더 있으며, n층에서 들어갔던 방의 방향과 1층에서 들어갔던 방의 방향이 같을 경우에도 위험 장치가 발동해 쫓겨납니다.
남우는 1층부터 시작해서 n층까지 차례대로 올라가면서 방을 들어가되, 쫓겨나지 않고 최대한 많은 보물을 가져가고자 합니다. 남우가 가져갈 수 있는 보물의 최대 개수를 구하는 프로그램을 작성하세요.

 
입력 예제

2 
10 9 8 
10 7 6

 
 
출력 예제

19

 
제출 결과

 
코멘트

- 이전 문제 신전 탐험하기의 응용 문제이다.

- 마찬가지로 3xn 배열에 메모리제이션을 이용하는 것을 동일하다.

- 하지만 특수 조건이 붙었기 때문에 어느 한 방향을 정해 시작 지점 값을 0으로 설정하고, 마지막 n층에서도 해당 위치를 제외한 나머지 두 방향의 값만 확인한다.

- 이런 방식을 각 방향마다 즉, 3번 시행하면 나오는 6개의 값 중 가장 큰 값이 문제의 정답이다.