Jerry의 기록저장소

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬문제. solved.ac 문제 목록 보다가 위상정렬 알고리즘 문제가 있길래 공부하고 풀어보았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 링크드리스트로 풀었다가 시간초과나서 덱2개 사용한풀이로 통과했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.List; import java.util.StringTokenizer; public c..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 시뮬레이션 문제, 재밌는 문제인데 한방에 맞춰서 더 좋았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import j..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 벨만포드 알고리즘 문제 계속 틀려서 소중한 직장인 주말 2시간을 썼다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 그냥 bfs, dfs 문제이겠거니 해서 풀었는데 시간초과가 떠서 당황했다. 처음 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util...

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 다른 숨바꼭질 시리즈를 풀어봐서 그런지 풀만했다. 다익스트라 처럼 해당위치에 최소시간을 갱신하며 bfs를 하는 것을 떠올리는게 중요한 관건이었다. 우선순위 큐이기 때문에 목적지에 도달하는 시간보다 더 느린시간을 만난경우 break로 빠져나오도록 해서 시간을 좀 더 단축할 수 있었다. import java.io.BufferedReader; import java...

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net dfs문제. 엄청 쉽게 생각해서 그냥 풀었더니 시간 초과가 나서 dp 이용해서 풀었다. 역시 그냥풀리면 골드3이 아니지.. 판다는 주변에 나무가 더 많은 곳으로 이동, 며칠 갈 수 있는가? 를 묻는 문제 dfs로 탐색 -> 시간초과 이미 지나온 곳은 어디서 접근하든 결과가 같으므로 테이블에 현재 위치 = 다음 위치 + 1 개만큼 더 갔다는 걸 떠올려서 dp테이블 만들기 (안지나 간 곳?-..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 플로이드 와샬 연습용문제. 400 x 400 이므로 인접행렬로 풀었음 (생각해보니 플로이드문제중에 인접리스트로 푸는게 있던가?..) 배열 INF값으로 초기화 edge 넣어줌 edges[a][b] = dist; // a -> b는 거리가 dist 플로이드와샬 경출도 (경유지, 출발지, 도착지) edges[a][b] > edges[a][k] + edges[k][a] ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 문제 bfs pq 이용해 최소비용으로 하면 다익스트라라고 하신 민O형의 말씀. 덕분에 다익스트라 방법을 까먹더라도 bfs에 pq 이용해서 푼다는 것을 기억하고 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문자열 문제를 풀어보려했으나? dfs였던 문제; 비트마스킹 연습도 되어서 좋았다. (근데 그래도 코테에서는 배열 visit체크로 풀 것 같다. 더 구현이 편함..) 비트마스킹이 손에 덜 익어서 좀 어려웠던 문제. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ..