알고리즘 공부방

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 유형: DFS, DP 문제 풀이 이 문제는 dfs로 돌리면서, 오른쪽 끝점까지 갔던 경로를 dp로 저장하면서 푸는 문제이다. 예를 들어 (3,3)에서 (10,10)으로 가는 경로가 3이라 했었을 때 (1,1)에서 출발하여 (3,3)에 도착하면, (10,10)까지 가지 않아도 경로를 알 수 있게 되는 것이다. 전체 코드 import java.io.*; import java.util.*; public..

https://www.acmicpc.net/problem/26598 26598번: 색종이와 공예 첫째 줄에 색종이 공예품의 세로 길이 $N$, 가로 길이 $M$이 공백을 두고 주어진다. $(1 \leq N,M \leq 1\,000)$ 다음 $N$개의 줄에 걸쳐 알파벳 대문자로 이루어진 길이가 $M$인 문자열이 주어진다. 상하좌 www.acmicpc.net 문제 유형: 그래프 이론, 에드 훅 문제 풀이 간단한 그래프 탐색 문제이다. 탐색을 시작한 좌표와 같은 문자만 탐색을 하며, 탐색이 끝났을 때, 탐색했던 가장 작은 x좌표와 y좌표, 가장 큰 x좌표와 y좌표를 구하고, 이것을 이용해 사각형의 넓이를 구해, 탐색하며 알파벳을 개수 카운트 한 것과 같은지 판별해주면 되는 문제이다. 전체 코드 import j..

https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 문제 유형: 그리디, 우선순위 큐 문제 풀이 입력이 최대 1000000이기에 O(nlogn)풀이로 풀 수 있다. 그렇기에 우선순위 큐를 써 그리디하게 가장 작은 것 두개를 곱하고 다시 넣고, 큐 사이즈가 1이 될때까지 반복한다. (오버플로우 조심하자..) import java.io.*; import java.util.*; public class Main {..

https://www.acmicpc.net/problem/16456 16456번: 하와와 대학생쨩 하와이로 가는 거시와요~ 첫째 줄에 하와이 열도의 섬의 개수 n(1 ≤ n ≤ 50,000)이 주어지는 거시와요 하와와. 하와와! 답이 커질 수 있으니 1,000,000,009로 나눈 나머지를 출력해 주시는 거시와요! www.acmicpc.net 문제 유형: DP 문제 풀이 이렇게 노가다로 dp[i] = dp[i - 3] + dp[i - 1]의 점화식을 발견해 풀었다. 전체 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws NumberFormatException, IO..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 분류: 그리디 알고리즘, 자료구조, 우선순위 큐, 정렬 문제 설명 첫번째 방법(틀린 방법) 보석의 우선순위 큐와 가방의 우선순위 큐를 만들고, 보석의 우선순위 큐의 경우는 가격이 높은 순으로, 가격이 같다면 무게가 가벼운 순으로 정렬을 하고, 가방의 경우는 내림차순으로 정렬. 그리고 두개의 큐 중 하나라도 빌때까지 while 문을 ..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 유형: 정렬, 그리디 알고리즘 문제 풀이 먼저 서류전형이든 면전전형으로 오르차순 정렬을 하고, 첫 번째 면접(서류) 전형의 순위를 min 값으로 정의한 다음 두 번째부터 min을 비교하며 더 작으면 min를 재정의, 결과값을 1증가 시켜주면 된다 전체 코드 import java.io.*; import java.util.*; public class Main { static..

https://www.acmicpc.net/problem/26153 26153번: 로하의 농사 로하가 사는 마을에는 정사각형 땅들이 $N \times M$행렬로 이루어져 있다. 로하는 그중 한 개의 땅에 살고 있으며 그 땅에 농사를 지으려 한다. 하지만 자신의 땅에서 나오는 물로는 농사짓기에 턱 www.acmicpc.net 알고리즘 분류: 그래프 이론, DFS 문제 설명 저번 한양대 오픈 콘테스트에 참여했었을 때 눈여겨 보고있었던 문제였는데, 오늘 종강기념으로 풀고자 했다. 먼저 문제를 봤을 때 처음 갔던 곳을 또 가야하는 문제였고, 한번 탐색 후 visited 변수를 다시 원래대로 복구하는 DFS가 맞는 답이라 생각했다. 구현자체는 어렵지 않았다. DFS를 진행하면서 방향이 다르면 파이프 개수를 2를 ..

https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 알고리즘 분류: 그래프 이론, BFS 문제 설명 현재 진행하고있는 방향과 다음으로 가야하는 방향을 비교하여, 만약 방향이 다르면 cnt값을 1을 추가하고 방향을 바꿔주고, queue가 아닌 PriorityQueue를 사용하여 cnt가 작은 순으로 queue에 집어 넣어 가장 먼저 C에 도달하는 것이 가장 적은 cnt임의 방법을 생각했다. 여기서 문제가 있었던 것이 분명 visited를 안..