Hello, Freakin world!

www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 문제 풀이 검사 대상 문자열 : S, 폭발 문자열 : C 1. S의 문자열을 차례대로 순회하면서 Stack에 추가한다. 2. 만약 추가한 문자가 C의 마지막 문자열과 같다면 C의 길이만큼 스택을 역탐색해 폭발 문자열인지 검사한다. - 폭발 문자열인 경우, 폭발 문자열의 길이만큼 pop한다. 다시 1번으로 - 아닌 경우 pass. 다시 1번으로 라이브러리에서 주어지는 Stack에는 배열처럼 순회하..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 풀이 방법 문자열을 정렬한 뒤, 앞의 문자가 뒤의 문자에 포함되는지 살펴가면서 전체 순회하면 답을 얻어낼 수 있는 문제였습니다.(저는 결국 풀이를 보고 나서야 알았지만..) import java.io.*; import java.util.ArrayList; import java.util.Comparator; import java.util.List; /* 전화번호 목록 https://w..

www.acmicpc.net/problem/16521652번: 누울 자리를 찾아라첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다.www.acmicpc.net 정규표현식 반복자를 활용할 수 있다면 간단하게 풀 수 있는 문제입니다. 그리고 문제 이해시 주의할 점은 단순하게 한 줄에 2개 이상의 자리가 있는지 판별하는게 아니라는 사실입니다.예를 들어 한 줄이 ......X.. 일 경우 자리는 2개가 됩니다. 정규표현식 반복자에 대해 다른 분이 잘 정리한 글을 첨부합니다. 정규표현식 반복찾기정규표현식 — 반복찾기정규표현식의 가장 핵심 기능이라고 생각되는 부분이다.med..

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 먼저 다익스트라 알고리즘으로 최단 거리를 구하면서 최단거리를 갱신할 때 노드의 부모들을 저장해줍니다. 그리고 최단 거리 노드들의 부모들을 순회하면서 간선을 없애고 다시 최단 거리를 구해 반환합니다. 구현 상의 팁 부모 정점들을 저장할 때 최단 거리가 갱신될 경우, 이전의 부모 정점 리스트를 버리고 새로운 리스트를 할당해 저장해야 합니다. 그리고 저장해놓은 최단 거리와 큐에 저장..

www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net 왜 스택구조인가? 먼저 아래의 상황을 관찰해보자. 먼저 i번째 건물에서 신호 보내는 상황을 살펴보면, i 건물에서 보낸 신호가 i-2에 닿고 있다. 다음 i+1에서 신호를 보낼 때는 i 건물에 신호가 닿는다. 여기서 i-1 건물에 살짝 주목해보자. 이 건물의 정보는 저장할 필요가 없다. i+1 위치에서 보면 i 건물에 가려 보이지 않기 때문이다. 그렇기 때문에 i번째 단계에서 i 건물보다 낮은 건물의 정..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 다익스트라 알고리즘으로 풀기 전에 DP로 풀 수 있지 않을까? 라고 생각했지만 어렵겠다고 결론을 내렸습니다. 이유는 수빈이가 x-1로도 움직일 수 있기 때문입니다. 점화식은 구해지지만 이 경우 재귀로 풀어야 하는데 시간복잡도가 O(3^n)이 되므로 불가능합니다. 전형적인 다익스트라 알고리즘에 약간 추가로 생각해줘야 할 점이 있습니다. 그래프 노드의 범위를 정해주는 겁니다...

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 이 문제의 핵심은 1의 상황을 2로 바꿔서 풀 수 있다는 걸 이해하는 겁니다. 다익스트라는 단일 시작점을 기준으로 모든 정점 간의 최단 거리를 계산하기 때문에 1번과 경우에 1,2 정점에서 X까지의 최단 거리를 구하려면 1,2 정점 각각에서 최단 거리를 구해야합니다. 이 경우는 비효율적이기 때문에 2번처럼 간선을 역전시켜 1번의 상황을 한번의 다익스트라 알고리즘을 통해서 해결할 ..

www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 적용하기 전에 그래프 모델링이 필요합니다. 하나의 칸을 하나의 노드라고 할 때 이전의 칸에 상관없이 목적지 칸의 값이 1(벽)이면 1의 가중치를 적용하고 0인 경우 0의 가중치를 적용합니다. 그리고 A -> B, B -> A 와 같이 양방향으로 간선을 정해줘야 합니다. 하지만 다행히 직접 구현할 필요는 없습니다. 가중치가 이전 칸의 종류에 상관없이 목적지 칸..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 주의할 점은 출발지와 도착지가 같지만 가중치가 다른 간선이 주어질 수 있다는 점입니다. 이 점 때문에 인접 행렬이 아니라 인접 리스트로 간선을 표현해야 합니다. ... /* 최소 비용 구하기 https://www.acmicpc.net/problem/1916 */ public class Main { static int n,m; static long INF = Long.MAX_VA..

www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 문제 풀이 이 문제의 핵심은 임의로 붙여진 부분은 신경쓸 필요가 없다는 사실을 간파하는 겁니다. 문제에서 초기의 문자열 A가 주어지고 이 문자에 앞,뒤에 임의의 문자를 붙여 B와 길이를 맞춘다고 했습니다. 문자열 간의 다른 부분을 최소화하기로 했으므로 임의로 붙인 문자열은 B에 대응하여 같은 부분이여야 합니다. 이 상황을 이해하면 문제가 간단해집니다. 초기 문자열 A가..