![]()
문제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/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 문제 풀이 출발지부터 도착지점까지 옮길 수 있는 중량의 최댓값을 구하는 문제이다. 해당 문제를 풀 수 있는 방법은 여러가지가 있다. 프림과 크루스칼을 통해서 start -> end까지의 최소 비용을 계산하는 방법도 있고, 이분탐색을 통해서 중량을 설정하고, 옮길 수 있는지에 대한 여부를 통해 mid 값을 조절하는 방법이 있다. 나는 ..
![]()
문제 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개의 줄에는 비용 행렬이 주어진다. 각 행렬의..
