목록전체 글 (35)
알고리즘 공부방
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를 ..
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를 안..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 알고리즘 분류: 그리디 알고리즘, 정렬 문제 풀이 먼저 이 문제를 보자마자 생각난 문제가 있었는데, 백준 1461 문제와 비슷하다 생각했다. https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전..