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

1. 문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 2. 풀이 과정 StringBuilder객체인 sb에 결과 문자열을 담았다. 실행 과정은 아래 2단계로 정리할 수 있다. 1) (sb길이 >= 폭발시킬 문자열 길이) & (방금 읽은 문자 == 폭발시킬 문자열의 마지막 문자)이면, 검사 시작 2) sb의 뒤에서 폭발시킬 문자열 길이만큼 잘라서 비교 => 같으면 자르기 폭발시킬 문자열 내에 반복되는 구간이 있다면 KMP를 쓰..

1. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이 과정 재귀 + 2차원 배열 DP문제라고 할 수 있다. 처음엔 순열을 돌려서 전체 탐색을 했는데 경우의 수가 16!으로 결국 시간 초과가 발생했다. 해결 방안이 떠오르지 않아, 질문을 보고 힌트를 얻어 풀 수 있었다. 이 문제의 key point는 2가지다. 1) 루프는 시작점이 어디든, 더해지는 값이 같기 때문에 값의 총합은 같다. => ..

1. 문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 2. 풀이과정 문제 자체를 바로 이해하기 어려웠다. 2단계에서 "파이어볼이 여러 개 있으면, 그 자리에서 나눠지고 이동은 다음 단계에 한다."는 식으로 수정했으면 좋겠다. 실행 과정 1) Node라는 클래스를 만들어 한 곳에 파이어볼이 여러 개오면, 값을 누적시킨다. 2) 다음 이동에서 cnt>1이면, 방향에 따라 이동시킨다. *남은 파이어볼의 질..

1. 문제 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 2. 풀이과정 요약하면 '그래프 Minimum Spanning Tree + 연결 있는 곳만 보기' 문제이다. 1) 입력을 받으면서 전체 선의 길이를 구해놓는다. 2) 자기 자신으로 가는 선, 연결 없는 선을 거르기 & i => j와 j => i 중 더 작은 값만 넣기 3) n개의 컴퓨터가 연결될 때까지 Kruskal 실행 import java.io.*; import java.uti..

1. 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 2. 풀이 과정 100x100까지는 단순한 DFS로 풀어도 빠르지만, 이 문제는 최대 map의 크기가 500x500이다. 따라서 간 곳은 또 갈 필요가 있을지 생각해봐야 한다. 여기서는 미래를 이미 알고 있는 건 다시 가지 않아도 되므로 이를 cnt[][]에 기록하였다. 자세한 동작 과정은 아래와 같다. 1. cnt[][]의 값을 -1로 초기화 (안 간 곳은 -1, 간 곳은 0이상으로 표시하..

1. 문제 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 2. 풀이과정 기본적으로, 주어진 소수들을 계속 곱하면서, PriorityQueue에 넣는다. 여기서 중복 값을 제외시키는 방식으로 N번째 수를 찾았다. 중복된 값을 제외시키는 방식을 처음엔 contain으로 검사해서 시간초과가 발생했다. 질문 검색으로 힌트를 보고, 2*5*7 = 2*7*5 = 5*2*7 = 5*7*2 = 7*2*5 = 7*5*2와 같이 같은..

1. 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 2. 풀이과정 1. 출발지부터 시작, 출발지는 방문 체크 2. 편의점, 도착지 전체를 보면서, 갈 수 있는 곳 확인한다. - x좌표의 차이 + y좌표의 차이

1. 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 2. 풀이과정 처음엔 단순하게, 아래 코드처럼 상대방과 상대방과 연결된 노드들에 연결된 노드를 추가시켜주려고 했다. 하지만, 하나의 네크워크의 연결된 정보를 그에 속한 모든 노드들이 중복해서 갖다보니 메모리 초과가 났다.. public static void connect(String p1, String p2) { Set s1 = personNo.get(p1); Set s2 =..

1. 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 2. 풀이과정 '관계 = 나보다 뒤에 있다'라고 정의하고 보았다. i => k 이고 k =>j이면 i=>j인 것을 모든 수에 대해 적용시키면 된다. 여기서 i==j일 때는 시작지와 도착지가 같으면 의미가 없으므로 넘긴다. 또, j를 들어가기 전 i=>k부터 성립이 안 되면 앞에서 걸러주면 시간이 단축된다. import java.io.*; import java.util.*; pub..

1. 문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 2. 풀이과정 입력이 아래와 같이 주어진다고 하면, 6 2 3 1 5 5 2 1 앞에서부터 증가하는 수열을 찾으면서, 그 때마다 마지막에 위치한 수도 같이 저장한다. 감소하는 수열은 뒤에서부터 증가하는 수열과 같은 의미로, 앞의 과정을 인덱스 N-1에서부터 똑같이 해주면 된다. 그리고나서, 두 부분으로 잘라서 앞부분의 제일 긴 증가하는 수열 길이 + 뒷부분의 제일 긴 감소하는 수열의 길이를 더한 값의 최대..