목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]9934번 완전 이진 트리 풀이: 트리

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 입력 k는 완전 이진 트리의 깊이를 나타내고, 배열은 트리 내 노드를 중위 순회(inorder)한 순서입니다. 먼저 트리 내 노드의 개수를 알아야겠죠? 완전 이진 트리의 깊이 k가 알려졌을 때 총 노드의 수는 다음과 같습니다. 중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 탐색하는 방법입니다. 이제 문제를 해결하기 위한 사전 지식은 갖춰졌으니 ..
알고리즘 문제 풀이/BOJ 2022. 3. 14. 15:09
[백준 BOJ][C++]11057번 오르막 수 풀이: DP

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 이 문제는 Dynamic Programming, DP로 해결할 수 있습니다. dp[i][j] = 숫자 i로 시작하는 j 자리 오르막 수의 개수 (i: 0~9, j: 1~N) 초깃값은 dp[0][1] 부터 dp[9][1]은 전부 1이 되겠죠? dp[0][2] 는 어떻게 될까요 가능한 수가 00, 01, 02, 03, 04, 05, 06, 07, 08, 09 총 1..
알고리즘 문제 풀이/BOJ 2022. 3. 10. 16:42
[백준 BOJ][C++]1149번 RGB 거리 풀이: DP

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp부터 설정합시다. 최소 비용으로 칠해야하기 때문에, dp를 최소비용으로 설정해나가야 합니다. dp[n][0] 은 n번째 집을 빨간색(R)로 칠했을 때의 1번째~n번째 집까지의 최소비용 dp[n][1] 은 n번째 집을 초록색(G)로 칠했을 때의 1번째~n번째 집까지의 최소비용 dp[n][2..
알고리즘 문제 풀이/BOJ 2022. 3. 10. 15:49
[백준 BOJ][C++]3187번 양치기 꿍 풀이: BFS/DFS

https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 이 문제는 BFS/DFS 를 사용하여 해결할 수 있습니다. [풀이 과정] 1. R과 C, 각 영역에 대한 정보 입력 2. 영역이 'k'라면 전체 양의 수를 나타내는 k값 증가, 'v'라면 전체 늑대 수를 나타내는 v값 증가 3. 아직 방문하지 않은 울타리로 둘러쌓인 영역 탐색(bfs) 4. 탐색 과정에서 울타리로 둘러쌓인 영역 내에서의 양의 수(knum), 늑대의 수(vnum) set..
알고리즘 문제 풀이/BOJ 2022. 3. 9. 17:32
[백준 BOJ][C++]2225번 합분해 풀이: DP

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp부터 설정해야겠죠? dp[i][j] 는 i 개의 숫자의 합이 j 가 되는 경우의 수를 나타냅니다. 초깃값으로는 dp[1][j]는 모두 1이 되겠죠? dp[2][j] 부터 보겠습니다. 각 색깔이 다음 단계에서 어떻게 쓰이는지 봐주세요! 모든 경우 경우의 수 dp[2][0] 0+0 1 dp[2][1] 0+1 1+0 2 dp[2][2] 0+2 1+1 0+1 3 dp[3][j] 는 어떻게 될까요? 모든 경우 경우의 수 dp[3][0] 0+0+..
알고리즘 문제 풀이/BOJ 2022. 3. 9. 17:23
[백준 BOJ][C++]1912번 연속 합 풀이: DP

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp[n]은 수열 arr의 n번째 원소까지의 연속합의 최댓값입니다. 문제 예제인 10 -4 3 1 5 6 -35 12 21 -1 을 보겠습니다. arr[0]인 10까지의 최대 합은 당연히 10이겠지요? dp[0]=arr[0]=10으로 초기화 합니다. arr[1]인 -4까지의 최대 합을 보겠습니다. dp[0]+arr[0] 6..
알고리즘 문제 풀이/BOJ 2022. 3. 6. 20:10
이전 Prev 1 ··· 5 6 7 8 9 10 11 ··· 13 Next 다음