⭕️ 1949번 : 우수 마을 (골드2)
- 문제 유형 : dp, tree
- 시간 복잡도 : O(n)
- 풀이 방식 :
- ArrayList를 이용해서 트리를 저장
- 방문한 정점 체크용 visit배열 이용
- 현재 노드를 선택했을 때의 경우와 선택하지 않았을 경우의 주민수를 저장하는 2차원 dp[n][2]를 이용
- 현재 노드를 선택한 경우 -> 자식노드는 무조건 선택하지 않음
- 현재 노드를 선택하지 않은 경우 -> 자식노드를 선택했을 경우와 자식노드를 선택하지 않았을 두 경우 중 더 큰 값 선택
- 리프노드부터 루트노드(1)로 올라오며 각 경우의 주민수를 구한 후 루트노드에서 더 큰 경우를 채택하여 출력
⭕️ 1135번 : 뉴스 전하기 (골드2)
- 문제 유형 : greedy, sort, dp, tree
- 시간 복잡도 : O(nlogn)
- 풀이 방식 :
- 트리 정보를 인접리스트를 이용하여 저장
- 재귀를 이용해서 리프 노드부터 자신의 아래 위치에 뉴스가 전해지는 데 가장 오래 걸리는 시간을 구하여 리턴
- 자식 노드(직속 부하 직원)들의 직속 부하 직원 수를 배열에 저장하고 내림차순 정렬한 뒤 한 번에 한 사람에게만 전달 할 수 있기 때문에 배열의 앞에서부터 1씩 늘려가며 소요시간을 더함 (+1, +2, +3, ... , +n) (많은 부하 직원을 가진 부하 직원부터 가장 먼저 전달해야 시간 소요가 최소화)
- 배열을 오름차순 재정렬한 뒤에 가장 앞에 있는 시간(가장 오래 걸리는 시간)을 리턴
- 루트 노드(매니저)까지 진행 후 구해진 시간이 최소 시간
⭕️ 9252번 : LCS3 (골드3)
- 문제 유형 : dp, String
- 시간 복잡도 : O(nmk)
- 풀이 방식 :
- 9251번과 같은 방식이지만 비교 문장이 3개이기 때문에 dp배열을 3차원 배열로 이용(dp[n][m][k])
- 다를 경우 dp[i][j] = Math.max(Math.max(dp[i-1][j][k], dp[i][j-1][k]), dp[i][j][k-1]) -> 현재까지 구한 LCS의 길이를 뜻함
⭕️ 11054번 : 가장 긴 바이토닉 부분 수열 (골드3)
- 문제 유형 : dp
- 시간 복잡도 : O(n^2)
- 풀이 방식 :
- 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 저장하는 일차원 dp배열 두 개를 이용
- 수열의 현재 값 보다 앞선 작은 값 중 dp에 저장되어있는 부분 수열의 크기가 가장 큰 수열의 크기 택해 1 증가된 값을 dp의 현재 값에 저장
- 수열의 현재 값 보다 앞선 큰 값 중 dp에 저장되어있는 부분 수열의 크기가 가장 큰 수열의 크기 택해 1 증가된 값을 dp의 현재 값에 저장
- 두 dp배열의 값을 각 인덱스마다 더한 후 가장 큰 값이 가장 긴 바이토닉 부분 수열
⭕️ 1516번 : 게임 개발 (골드3)
- 문제 유형 : dp
- 시간 복잡도 : O(V+E)
- 풀이 방식 :
- 기존의 위상 정렬은 동시간대에 선택되는 정점까지 따질 필요는 없었지만, 각 건물(노드)들의 최소 완성 시간을 구해야하기 때문에 선행 건물의 건설 시간 중 가장 오래 걸리는 시간을 알아야한다
- 따라서 queue를 사용하던 위상 정렬과 달리 건설 시간을 오름차순 기준으로 정렬하는 우선순위 큐를 이용하여 위상 정렬
- 선행 노드의 개수가 0이 되면 먼저 앞선 건물들의 건설 시간을 현재 건물의 건설 시간에 더한 후 우선순위 큐에 넣어야 정확한 각 건물별 최소 완성 시간을 구할 수 있음
⭕️ 1509번 : 펠린드롬 분할 (골드1)
- 문제 유형 : dp
- 시간 복잡도 : O(n^2)
- 풀이 방식 :
- 10942번 펠림드롬?의 방법으로 각 범위에서 펠린드롬인지 판정하는 2차원 dp배열 생성
- 각 문자에서의 최소 펠린드롬 분할 개수를 저장하는 1차원 dp배열을 이용
- dp[0]은 문자가 존재하지 않기 때문에 0으로 초기화
- 각 문자에서 직전 문자까지의 dp값에 1을 더한 값을 현재 dp에 넣음 (우선 현재 문자를 붙였을 때의 문자열이 펠린드롬이 아님을 가정해 분할 개수가 1 늘어난 값을 넣음)
- 현재 문자를 직전 문자열에 붙여 앞에서부터 하나씩 잘라가며 펠린드롬인지 확인하고 펠린드롬이라면 펠린드롬 문자열을 제외한 앞 문자열의 dp값에 1을 더하여 현재 dp값과 비교해 작은 값을 dp에 넣음 (11054번 가장 긴 증가하는 부분 수열의 방식과 비슷)
- 마지막 문자에서의 dp값이 전체 문자열에서의 최소 펠린드롬 분할 개수
⭕️ 1516번 : ACM Craft (골드3)
- 문제 유형 : dp, graph
- 시간 복잡도 : O(V+E)
- 풀이 방식 :
- 우선순위 큐와 위상정렬을 이용하는 풀이법(1516번 게임 개발)을 각 case별로 적용
❌ 1520번 : 내리막 길 (골드3)
- 문제 유형 : dp, graph, dfs
- 시간 복잡도 : O(n^2)
- 풀이 방식 :
- 해당 위치에서 목적지까지 이동할 수 있는 경로 수를 의미하는 2차원 dp배열, 재귀를 활용한 dfs 탐색 사용
- 맨 왼쪽 위 노드에서부터 dfs 탐색 시작
- 현재 노드가 목적지일 경우 1 리턴
- dp[i][j]에서 4방향 탐색을 하여 이미 방문할 노드일 경우 이미 해당 노드를 거쳐 목적지까지 갈 수 있는 경로의 개수를 알고 있는 것이기 때문에 dp[i][j]에 더하고, 방문하지 않은 노드일 경우 dfs탐색(재귀 이용)을 하여 dp[i][j]에 더함
- 최종적으로 시작점인 dp[0][0]의 값이 목적지까지 갈 수 있는 경로의 수이다
⭕️ 1937번 : 욕심쟁이 판다 (골드3)
- 문제 유형 : dp, graph, dfs
- 시간 복잡도 : O(n^2)
- 풀이 방식 :
- 해당 위치에서 이동할 수 있는 칸 수를 의미하는 2차원 dp배열, 재귀를 활용한 dfs 탐색 사용
- 모든 노드를 탐색하여 방문하지 않은 노드는 dfs 탐색
- dp[i][j]에서 4방향 탐색하여 이미 방문한 노드의 경우 이동 가능 칸 수를 알고 있는 것이기 때문에 1을 더한 값이 dp[i][j]의 값보다 크면 값을 바꾸고, 방문하지 않은 노드의 경우 dfs 탐색(재귀 이용)을 한 후 1을 더한 값이 dp[i][j]의 값보다 크면 값을 바꿈
- 4방향 탐색 후 정해진 dp[i][j]값이 이동 가능 최대 칸 수를 의미하는 max보다 크면 값을 변경
⭕️ 1103번 : 게임 (골드2)
- 문제 유형 : dp, graph, dfs
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 일반적인 bfs, dfs 탐색으로 최대 동전 이동 횟수를 구할려고 하면 이미 탐색한 위치를 중복 탐색하기 때문에 각 위치마다 4방향 탐색을 하게 되어 시간 복잡도가 O(4^(nm))이 됨
- 따라서 재귀를 이용한 dfs와 2차원 dp배열을 이용해서 최대 동전 이동 횟수를 구함
- 4방향 탐색에서 방문하지 않은 위치라면 dfs 탐색을 하고, 이미 탐색한 위치라면 미리 구한 동전 이동 횟수를 가져와 4방향 중 가장 큰 값에 +1 한 값을 dp배열에 저장
- 현재 위치에서 동전을 이동했는데 해당 위치가 구멍 혹은 보드 밖 위치라 게임이 종료되면 해당 방향으로는 무조건 1번만 이동시킬 수 있기 때문에 1을 가져와 나머지 방향의 값과 비교`