네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 2. 풀이 과정 흔히 union & find를 구현할 때, find에서 사이클 여부를 판단한다. 이 문제는 find의 로직과 유사하게 구현할 수 있다. 사이클이 되는 모든 값을 결과로 출력하면 되는 문젠데, 처음부터 그래프 유형인걸 파악못해서 시간이 걸렸다. 1. for문으로 첫 번째 줄의 값을 처음부터 끝까지 탐색한다. 2. 각 값마다 cycle이 되는지 확인하고, cyc..

1. 문제 https://www.acmicpc.net/problem/2374 2374번: 같은 수로 만들기 n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한 www.acmicpc.net 2. 풀이과정 문제 유형에 stack이 써있는 걸 보고 풀었다. 안 보고 풀었으면 생각해내기 어려웠을 것 같았다. 입력을 처음부터 끝까지 받으면서, 구간마다 최소값을 찾아서 큰 값에서 뺀 값을 결과에 더해주었다. 마지막에 최대값에서 stack의 top에 있는 값을 빼주는 이유는 값이 감소하면서 끝날 경우 앞서 나온 최댓..

1. 문제 https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 2. 풀이 과정 방법 1. DFS 열어야 하는 문이 왼쪽 열린 문과 오른쪽 열린 문 사이에 있다면, 깊이 우선 탐색으로 둘 다 탐색해본다. 열어야 하는 문이 두 개의 열린 문보다 왼쪽에 있다면, 왼쪽 열린 문을 당겨와서 사용한다. 열어야 하는 문이 두 개의 열린 문보다 오른쪽에 있다면, 오른쪽 열린 문을 당겨와서 사용한다. 이때, 현재까지 구한 결과 값보다 중간 값이 이미 크다면 더..

1. 문제 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 2. 풀이 과정 최단 경로를 구하는데, 지나온 길을 다시 탐색할 수 있기 때문에 플로이드 워샬 알고리즘으로 각 노드마다 갈 수 있는 최단 거리를 구하고 DFS 탐색을 했다. 이때, DFS 탐색의 결과는 어떤 노드를 먼저 방문하냐 즉 방문하는 노드 순서에 따라 달라지므로 순열 탐색으로 볼 수 있다. import java.io.BufferedReader; import java.io.I..

1. 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 2. 풀이 과정 특정 상태까지의 최소 이동 시간을 구하기 때문에, BFS로 탐색하였다. 여기서 고민했던 부분은 방문 체크였다. 이미 이전에 고려했던 2차원 배열의 상태는 다시 볼 필요가 없기 때문에, 이 2차원 배열을 int형 숫자하나인 123456780 식으로 변환해서 방문체크를 하고 너비우선탐색을 진행했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; p..

1. 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 풀이 과정 최단 경로를 구하는 데, 경로의 cost가 음수가 될 수 있기 때문에 Bellman-Ford 알고리즘을 사용했다. 평소에 잘 풀어보지 않았던 유형이라서 시간이 걸렸다.. 벨만-포드 알고리즘은 다익스트라와 유사한데, 다익스트라는 현재 연결된 노드에서 갈 수 있는 경로를 살펴보며 값을 업데이트하는 반면 벨만-포드 ..

1. 문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 풀이 과정 처음엔 DFS로 모든 경로를 처음부터 끝까지 탐색하도록 했고, 시간 초과가 났다. 아래 그림과 유사하게, 출발점에서 도달할 수 있는 좌표에 +1을 해나가며 값을 업데이트하고 결과는 (N, N)의 값을 출력해주면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

1. 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 풀이 과정 처음엔 ArrayList로 구현했다가 N의 범위가 100보다 작아서 2차원 배열이 더 빠를 것 같아서 수정했더니 2배 빨라졌다. 배열의 처음과 끝이 이어져있기 때문에 1번 과정에서의 8방향 탐색은 나머지 연산을 활용했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..

1. 문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 2. 풀이 과정 상근이가 이미 지나간 곳은 불이 번져도 상근이를 따라 잡을 수 없기 때문에, 불이 번지는 건 빈칸만 고려해주었다. 빈칸을 누가 먼저 가냐만 보면 된다. 상근이가 현재 갈 수 있는 위치와 불이 방금 번진 위치를 모두 queue에 넣고, 4방향 탐색으로 갈 수 있는 곳에 표시를 해준다. 이때, 상근이는 불이 다 번지고 난 후에 움직이기 때문에 처음 상근이의 위치는 queue의 마지막에 ..

1. 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 2. 풀이 과정 2차원 배열을 탐색하면서 1을 찾으면, DFS를 이용하여 4방향에 이어진 값들을 찾으며 탐색한 값의 개수가 몇 개인지 전역변수인 size를 이용하여 연산했다. 방문 체크는 2차원 배열의 값을 0으로 바꿈으로써 확인해준다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Strin..