사랑의 개발일지

1. 문제 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 2. 풀이 최소 스패닝 트리(MST)는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소인 트리이다. MST는 크루스칼, 프림 알고리즘 두 가지로 구할 수 있다. 간선이 적을 때는 크루스칼, 간선이 많을 때는 프림 알고리즘이 효율적이라고 한다. 이 문제에서는 Union Find를 사용하는 크루스칼 알고리즘으로 문..

1. 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 풀이 방향그래프가 주어질 때 한 시작점에서 다른 모든 정점으로의 최댄 경로를 구하는 문제이다. 다익스트라 알고리즘으로 문제를 풀 수 있다. 다익스트라 알고리즘은 PriorityQueue를 사용한다 ! 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..

1. 문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 2. 풀이 `DP`로 문제를 풀었습니다. dp배열은 해당 칸까지 가는데 걸리는 최소 점프 횟수입니다. 만약에 data[3]=3이고 dp[3]=2라면 3번째 칸 까지 가는 최소 점프 횟수는 2번인데 3번째 칸에서 4, 5, 6칸을 갈 수 있는데 점프를 하니까 3번(dp[3]+1)만에 갈 수 있습니다. 최소면 갱신하고 아니라면 무시하면 됩니다. 이렇게 최솟값을 갱신하면서 dp[0..

1. 문제 https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 2. 풀이 볼이 모여있는 뭉탱이(?)의 갯수가 홀수일 때/짝수일 때 경우의 수를 나눠서 문제를 풀었습니다. 볼 뭉탱이 갯수가 `홀수`일 때 R / BBB / R / B / RRR 이면 뭉탱이가 홀수개 입니다. `하나(R)`은 왼쪽 끝, 오른쪽 끝에 감싸고 있고 `하나는(B)`는 사이에 껴 있습니다. R은 왼쪽 끝(1개), 오른쪽 끝(3개) 중에서 많은 쪽으로..

1. 문제 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 2. 풀이 제가 짠 코드의 알고리즘은 `isVIP`라는 boolean 배열을 두어서 VIP좌석 표시하였습니다. `isVIP`를 탐색하다가 VIP좌석이 아닐때 count를 세고 VIP좌석을 발견했을 때 `dp[count]`를 결과값에 곱해주는 것입니다. 그래서 구현 편리성을 위해서 배열의 마지막 좌석 뒤(N+1)에 임의로 true로 하였습니다. `dp[n]`은 (VIP아닌)연속된 좌석이 n개 있을 때..

1. 문제 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 2. 풀이 브루트포스 알고리즘을 사용해서 문제를 풀었다. 먼저 사탕을 교환하는 모든 경우의 수를 구현하였다. 여기서 중요한 점은 만약 (i, j)와 (i+1, j) 사탕을 교환했다면 즉, 위아래 사탕을 교환했다면 `i행, i+1행, j열`을 검사해서 얻을 수 있는 최대 사탕 갯수를 구해주었다. (i, j)와 (i, j+1) 사탕을 교환했다면 즉, 좌우 사탕을 교환했다면 `j열, j+1열, i행`을 검사해서 얻을 수 있는 최대 사탕 갯수를 구해주었다. 행과 열에서 최대 사탕 갯수를 구해주는 함수는 각각 c..

1. 문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 풀이 이 문제를 풀 때 첫 번째로 문제를 이해하는데 어려움이 있었고 두 번째로 컨베이어 벨트와 로봇 위치를 어떻게 저장할 것인가 였다. 나는 문제를 이렇게 풀었다. `컨베이어 벨트 각각의 칸`을 Space라는 클래스를 만들어서 객체로 만들었다. `컨베이어 벨트`를 Space 클래스를 자료형?으로 가진 ArrayList로 만들었다. 1~4 동작을 각각 4개의 메..