겜돌이의 개발일지

문제 백준 11404 플로이드 C++ 풀이 전형적인 플로이드-와샬 알고리즘 문제이다. 3중 포문을 통해 모든 정점에서부터 모든 정점까지의 최소 거리를 구한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace std; const int INF = 987654321; int n, m; int dist[101][101]; int main(..

개요 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면, 플로이드-와샬 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 이차원 배열을 사용해 최소값을 계속 저장해두기 때문에, 다이나믹 프로그래밍 기법의 일부로도 볼 수 있다. 설명 A에서 B로 가는 최소 비용과 A에서 C를 거쳐 B로 가는 최소 비용을 비교한다. 다음과 같은 비용을 가지는 양방향 그래프가 있다고 가정하다. 초기값을 먼저 표시하면 다음 표와 같다. 1을 지날 때 다음 영역을 갱신 해줘야 한다. 4 -> 1-> 5 (반대도 같음)의 비용이 14이므로 INF에서 갱신해준다. 2를 지날 때 3 -> 2 -> 4 (반대도 같음)의 비용이 7로, 기존의 비용 8보다 더 저렴하..

문제 백준 11725 트리의 부모 찾기 C++ 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1이 루트기 때문에, 1에서 DFS나 BFS를 실행하면 된다. 해당 노드에 처음 방문했을 때, 그 전 노드가 부모가 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include #include #inc..

문제 백준 1647 도시 분할 계획 C++ 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 스패닝 트리를 이용한다. 1. 엣지들을 가중치에 대해 오름차순으로 정렬해주고 2. 최소 스패닝 트리를 만족하도록 가중치가 낮은 n - 2개의 엣지를 연결하면 두 그룹으로 나뉘게 된다. 3. 지금까지의 가중치의 합(ans)가 정답이 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

문제 백준 13459 구슬 탈출 C++ 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 BFS를 사용한다. 방문 체크를 [빨간색 공 x좌표][빨간색 공 y좌표][파란색 공 x좌표][파란색 공 y좌표]로 4차원 배열을 이용한다. 공을 4방향(위, 아래, 왼쪽, 오른쪽)으로 굴려주면서, 방문하지 않았을 때에만 큐에 넣어주고 도착지점에 도달할 수 있을 때까지 반복한다. 그전에 이미 10번 이상 시도했다면 조건에 부합하지 않으므로 0을 출력한다. 소스 코드 1 2 3..

문제 백준 2665 미로만들기 C++ 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 두가지 방법으로 풀었다. 첫 번째 방법 1. cnt만큼 벽을 뚫을 수 있게 설정해준다. 2. BFS() 함수를 실행하여 최대 cnt만큼 벽을 뚫으면서 도착지점에 도달할 수 있는지 없는지 확인한다. 3-1. 도착할 수 있다면 true를 return 하고 현재 cnt를 출력한다. 3-2. 도착할 수 없다면 cnt를 1증가시키고 다시 BFS() 함수를 실행한다. 방문 체크를 3차원 배열로 했는데 (y좌표, x좌표, cnt :..

문제 백준 20055 컨베이어 벨트 위의 로봇 C++ 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 구현 / 시뮬레이션 문제입니다. 생각보다 코드 구현과정이 어려웠는데, 문제 난이도인 골드 5보다는 어려웠습니다. (골드 4~3급은 된다고 생각) 문제에서 주어진 조건에 따라 1. 벨트가 한 칸 회전한다. 2. 벨트 위의 로봇이 움직일 수 있으면 움직인다. 3. 올리는 칸의 내구도가 0이 아니면 로봇을 올린다. 4. 내구도가 0인 칸이 K개 이상이면 종료한다. 의 4가지 과정을 순서대로..

문제 백준 14890 경사로 C++ 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이해 자체는 어렵지 않은 문제였다. 1. 이차원 배열에 값을 넣어주고 2. 행 / 열을 검사하면서 경사로를 놓을 수 있는지 확인한다. 경사로를 놓을 수 있는지 확인하는 과정은 다음과 같다. 1. 현재 값과 다음 값의 차를 구한다. 2-1) 차가 0인 경우 : 평지이므로 다음 구역으로 넘어간다. 2-2) 차가 1인 경우 : 현재가 더 높다. 따라서 내리막길이 필요하므로 다음 구역부터 그 다음 구역으로 가면서 내리막길을 설치할 수 있는 지 확인한다...

문제 백준 2343 기타 레슨 C++ 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 조건을 보고, 이분 탐색으로 해결할 수 있음을 유추해야 합니다. 순서를 변경하면 안 되고, 모든 동영상을 포함해야 하므로 mid 값에 대해 이분 탐색을 실행합니다. 조건을 만족하면 더 작을 mid 값을, 조건을 만족하지 못한다면 더 큰 mid값을 찾습니다. 길이의 합이 int 범위를 넘어설 수 있으므로 long long으로 선언해주고, mid 값의 최대는 100,000 * 10,000 = 10억이므로 범위에 유의합니다. 58%..

문제 백준 2805 나무 자르기 C++ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 전형적인 이분 탐색 문제입니다. low = 0, high는 나무의 최대 높이로 설정한 뒤, mid 값을 바꿔가며 이분 탐색을 시행합니다. low > high 조건을 만족하기 전의 result 값이 최종결과가 됩니다. sum은 int 범위를 초과할 수 있으므로 long long 타입으로 설정합니다. 한편, N의 최대 개수가 백만이라 시간초과가 나지 않을까 걱정했지만, C++은 N ..