![]()
문제https://www.acmicpc.net/problem/1781 문제 풀이처음 문제를 보고 난이도에 비해 정말 쉽다고 생각했다.회의실 배정과 유사하게 우선순위큐를 사용해서, deadLine이 짧은 순, 가치가 무거운 순으로 정렬한 뒤, 시간에 맞게 빼면 된다고 생각했다. 우선 문제에 대한 테스트케이스는 다음과 같다.해당 작업들을 우리가 목표로 하는 최대의 가치의 순서로 작업할 수 있도록 정렬해줘야 한다.고려해야할 점은 다음과 같다.데드라인이 적은 순서대로 정렬을 한다.가치가 많은 순으로 정렬을 한다.위 조건을 고려해서 정렬을 하면 다음과 같다.그리고 데드라인 별로 작업을 선택해서 답을 구하면 된다.하지만 여기서 함정이 존재한다.내가 풀이했던 방식은 데드라인이 아니라, 그때 풀어야 했던 문제라고 생각..
![]()
문제https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위www.acmicpc.net 문제 풀이동전에 대해 행과 열을 뒤집는 순서가 중요한 문제라고 생각했다.우리가 선택할 수 있는 경우의 수는 뒤집느냐, 뒤집지 않느냐이다.하지만 n의 최대 크기가 20이기에 최대 행에 대해 2^20, 열에 대해 2^20이 발생하기 때문에 최적화가 필요했다.작업의 순서가 중요한 점과 브루트포스로 n을 돌릴 경우 시간초과가 당연한 사실에서 저번에 풀었던 외판원 문제가 떠올랐다.외판원 문제도 도시를 ..
![]()
문제https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수www.acmicpc.net문제 풀이문제에서 요구하는 바를 이해하기 정말 어려웠던 문제였다.구간의 점수의 최댓값의 최솟값이라니,, 입력을 살펴보면 배열의 크기가 1부터 5000이고, 구간의 개수가 M개 이하이다.배열에 대해서 M개 이하의 구간으로 분리하고, 각 구간에서 구간의 점수를 구하고, 구간의 점수중 최댓값이고,그중에서 최솟값을 구해야 한다. 말로만 적어봐도 경우의 수가 굉장히 많..
![]()
문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 문제를 이해하는데 시간을 굉장히 많이 쓴 문제였다. 상어가 이동하는 조건과, 상어가 물고기를 먹는 조건, 그리고 상어를 이동시키는 방법 모두 중요했던 문제였다. 우선 내가 풀이를 위해 구현한 자료구조는 다음과 같다. data class Shark(val x: Int, val y: Int, val size: Int = 2, var eat: Int = 0, var time: I..
![]()
문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 문제의 조건을 고려하면서 어떻게 풀지 고민을 하면 위상정렬과 굉장히 유사하다는 것을 알 수 있다. 위상정렬에 정의는 순서가 있는 작업을 차례로 진행할 때, 순서를 결정하는 알고리즘이다. 문제에서 대놓고 문서를 풀 순서를 정하는 키워드가 있기도하다. 해당 문제에서 문제를 정하는 조건은 다음과 같다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은..
![]()
문제 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제 풀이 백준 문제를 자주 풀면 접해봤을 유형의 문제이다. 해당 문제의 유형은 LIS로 최장 증가 부분 수열의 길이를 구하는 문제이다. 왜냐하면 반도체의 선이 꼬이지 않게 가장 길게 연결하기 위해선 뒤에 등장하는 번호가 앞에 등장했던 번호들보다 커지면 안 되고, 이는 항상 앞에 등장했던 번호들보다 뒤에 등장하는 번호들이 작아짐이 보장되는 가장 긴 구간을 구해야 하기 때문..
![]()
문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 풀이 NXN의 배열을 일차원으로 압축시켜서 k번째 index의 수를 찾는 문제이다. 단순하게 NXN 배열을 만들어서 값을 i*j 값으로 넣어주기엔 N의 최댓값이 10^5승이므로 불가능하다. 따라서 실제 배열을 만들어주지 않고, 우리는 k번째 index의 수를 찾아야 한다. 우선 사용할 수 있는 정보는 배열의 원소들이 i*j의 형태로 계산된다는점과 A의 행렬..
![]()
문제 https://www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 문제 풀이 문제를 보고 감이 안 잡혀서 알고리즘 분류를 보고 풀 수 있었던 문제였다. 비트마스킹이 왜 필요한가에 대해서 생각을 하다가, 저번에 풀었던 외판원 순회 문제가 떠올랐다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의..
![]()
문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 풀이 문제를 읽고 누적합을 구해서 소형차를 배정하는 문제인 것 같았다. 문제에서 주어진 테스트케이스에 대해서 먼저 누적합에 대한 그림을 그려보았다. 처음으로 접근한 방법은 정해진 구간까지의 최대 누적합을 구하는 방법으로 접근했다. 예를 들어 50까지 접근했을때의 최댓값은 40과 50을 태운 90이다. 다음으로 10까지 접근했을때의 최댓값은 40과 50을 태운 90 vs (35+40..
