C++ 코딩 문제 풀이151 [Baekjoon] 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 해결 과정 착안 처음 착안에서 크기 $N$의 정수 삼각형을 구성하는 수들을 모두 입력받은 다음, 삼각형의 가장 아래 층부터 인접한 숫자끼리 비교하여 큰 숫자를 위 층의 숫자에 더하는 방식으로 구현하고자 하였다(동적계획법, dynamic programming). 문제를 해결한 뒤, 계산하고 난 다음에는 사용되지 않는 숫자 층들을 모두 저장하지 않고 메모리 공간을 절약해보고자, 숫자를 입력받는 순서대로 계산을 수행(위층에서부터 아래층으로 순차적 계산)하는 코드도 작성.. 2023. 6. 5. [Baekjoon] 1018번: 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 $M \times N$ 크기의 보드 내에서 $8 \times 8$ 크기 단위의 격자를 이동해가며 체스판을 다시 칠하는 횟수를 모두 구해본 다음(브루트 포스(brute force) 알고리즘), 작은 값이 구해졌을 때마다 갱신하고자 하였다. 한편, 체스판을 다시 칠하는 과정에서 가장 위의 왼쪽 칸이 $B$인 경우 다시 칠하는 횟수를 $c_b$와 $W$인 경우 다시.. 2023. 6. 4. [Baekjoon] 25192번: 인사성 밝은 곰곰이 https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 문제 해결 과정 착안 동일한 값을 가지는 요소를 중복하여 저장하지 않고 한 번만 저장하는 STL의 컨테이너를 사용하여 닉네임 문자열을 저장한 다음, ENTER 문자열이 입력되기 직전 또는 프로그램 종료 직전까지 컨테이너에 들어온 요소 수를 출력하고자 했다. ENTER 문자열이 입력된 뒤에는 컨테이너를 초기화하여 처음부터 다시 요소 수를 계산하고자 하였다. 구현 처음엔 별 생각.. 2023. 6. 4. [Baekjoon] 1149번: RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해결 과정 착안 $N$ 번째 단계에서 $N$ 번째 집을 색칠할 때, 빨강, 초록, 파랑 중 $i$ 번째 색깔로 칠하려면 $(N-1)$ 번째 집이 $i$ 번째 색깔이 아니어야 한다. 한편 $N$ 번째 집을 색칠하는 비용이 최소가 되기 위해서는 $(N-1)$ 번째 단계의 집까지도 역시 최소 비용으로 색칠을 해야한다. 즉, $N$ 번째 집을 $i$ 번째 색깔로 칠하는 비용을 .. 2023. 6. 2. [Baekjoon] 1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 과정 착안 최소 (비용) 신장 트리(minimum spanning tree, MST)를 구하는 문제이므로, 이를 구하는 대표적인 알고리즘을 이용하여 문제를 해결하고자 하였다. 문제에서 한 줄씩 간선 데이터를 입력으로 제공하기 때문에, 간선 데이터를 하나씩 저장하면서 정렬하는 것이 문제 해결에 편리할 것 같아서 크루스칼 알고리즘(Kruskal.. 2023. 5. 31. [Baekjoon] 11659번: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 해결 과정 착안 문제를 해결하기 위한 착안 과정에 실수가 많아서 이상한 생각의 흐름을 거쳐 답에 도달했는데 결국에는 올바른 방향으로 문제를 해결했지만 나중에 같은 실수를 반복하지 않기 위해 실수 과정을 기록해두려고 한다. 이상한 방법으로 문제를 풀기 전, 우선 문제를 해결하기 위해 올바르게 생각했던 부분은 크기 $N$의 배열에 각 인덱스 $i$마다 $1$부터 $i$번째.. 2023. 5. 30. 이전 1 ··· 15 16 17 18 19 20 21 ··· 26 다음
