알고리즘 공부방

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 유형: 이분탐색, Union-Find 문제 설명 먼저 설명하기전에 c++ 입출력 억까를 당했다.. 문제를 설명하면 먼저 입력에 주어진 배열을 저장한다. 그리고 k개의 자연수가 주어졌을 때, 이분탐색의 응용중 하나인 Upper Bound를 사용하여, k다음으로 큰 수를 배열에서 찾고, 출력해준다. 그리고 출력한 수는 다시 쓸 수 없으므로 똑..

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://judge.koreatech.ac.kr/problem.php?id=1274 Judge - 귀신의 집 문제 설명 새로 나온 갤럭시 Z 플립 4를 사고 싶었던 유진이는 돈을 모으기 위해 놀이공원 귀신의 집 알바를 시작했습니다. 귀신의 집에는 한 번에 정확히 3명씩만 들어갈 수 있는데, 무리지어 대 judge.koreatech.ac.kr 문제 유형: Math, dp?(풀이가 있을거라 예상) 문제 풀이 지난번 대회에서 아쉽게 풀지 못했던 문제를 다시 도전해봤다. (대회 중간에 멘탈이 나가서 흑흑..) https://judge.koreatech.ac.kr/contest.php?cid=1087 Judge 대회ID : 1087 - 2022년도 제9회 프로그래밍 경시대회 >> 문제풀이, 소스코드

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를 ..