728x90 반응형 백준 알고리즘55 [백준 11066][파이썬] 파일 합치기 (dp 알고리즘) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net dp를 활용하여 삼중 반복문을 사용하여 푸는 문제이다. dp[x][y]는 다음과 같이 정의한다. 인덱스 x 파일부터 인덱스 y 파일까지 하나의 파일로 합치는데 필요한 최소비용 이를 이용하여 dp 알고리즘을 적용하면 된다. 가장 먼저 x와 y가 동일한 경우를 보자. 다음과 같이 파일들의 크기를 나열할 때 15 1 21 3 4 5 35 5 4 3 5 98 21 14 17 32 dp[0][0].. 2023. 3. 15. [백준 1927][파이썬] 최소 힙. 파이썬 heapq 모듈 사용법 (우선순위 큐) https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐를 사용하여 푸는 문제이다. 우선순위 큐의 삽입, 삭제 시간 복잡도는 O(log N)이다. 파이썬에서 우선순위큐인 heapq 모듈을 제공한다. heapq의 경우 사용방법이 특이한데 따로 리스트를 만들고 이 리스트를 heapq 메소드의 인자로 사용해야 한다. 1. 삽입 : heapq.heappush( list, value ) import heapq li=[] heapq.. 2023. 3. 13. [백준 1654 랜선 자르기][파이썬] Parametric Search (이분 탐색) 접근 방법 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 백준 1654번 문제는 이분 탐색을 이용하는 Parametric Search의 기본적인 문제이다. Parametric Search를 사용하기 위해서는 문제를 결정 문제로 바꿀 수 있어야 한다. 위 문제의 경우 자를 랜선의 길이를 임의로 x라고 했을 때 랜선 N개를 만들 수 있다면 True를, 없다면 False를 반환하는 문제로 바뀌게 된다. 그러면 이제 x의 최대 길이.. 2023. 3. 11. [백준 1300][파이썬] K번째 수 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 이진 탐색으로 해결할 수 있다. 1. 배열의 가장 작은 값(low)과 가장 큰 값(high)의 중간 값(mid)부터 탐색을 시작한다. 2. 해당 값보다 작은 값의 개수와 같은 값의 개수를 구한다. 3. k가 mid 값보다 작은 값의 개수와 해당 값과 같은 값의 개수 사이에 존재한다면 mid를 출력하고 끝낸다. 4. k가 mid 값보다 작은 값의 개수보다 작거나 같다면.. 2023. 3. 3. 이전 1 ··· 3 4 5 6 7 8 9 ··· 14 다음 728x90 반응형
