Python 코딩테스트 (65) 썸네일형 리스트형 다이나믹 프로그래밍(동적 계획법) 다이나믹 프로그래밍: 중복되는 연산을 줄이자 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법이다. 다이나믹 프로그래밍(Dynamic Programming) 기법은 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 살펴보자. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치수열은 다음과 같은 형태로 끝없이 이어진다. 수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게.. 이진 탐색(이분 탐색): 백준 2110 파이썬 문제: https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이: 이 문제는 처음에 이해하기가 다소 어려웠다. 문제에서 집 좌표의 범위가 (0 ≤ x ≤ 1,000,000,000)와 같아서 이진 탐색을 사용해야 하겠다는 생각은 들었지만, 찾아야 하는 수 target을 어떤 것으로 할지 떠오르지 않았다. 구글링을 해서 힌트를 얻어 문제를 풀 수 있었다. 이 문제는 이진 탐색의 방법을 응용해서 해결하.. 이진 탐색(이분 탐색): 백준 2805 파이썬 문제: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답: import sys n, m = map(int, sys.stdin.readline().split()) wood = list(map(int, sys.stdin.readline().split())) # 이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(wood) result = 0 # 이진 탐색 수행 while(start m.. 이진 탐색(이분 탐색): 백준 1654 파이썬 문제: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 정답: import sys k, n = map(int, sys.stdin.readline().split()) array = [int(sys.stdin.readline()) for _ in range(k)] # 이진 탐색을 위한 시작점과 끝점 설정 start = 1 end = max(array) # 이진 탐색 수행(반복적) result = 0 while(start 이진 탐색(이분 탐색): 백준 10816 파이썬 문제: https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답: 1. collections 모듈의 Counter 클래스 사용 import sys from collections import Counter n = int(sys.stdin.readline()) n_arr = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) m_arr .. 이진 탐색: 백준 1920 파이썬 문제: https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) n_arr = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) m_arr = list(map(int, sys.stdin.readline().split())) def binary_.. 이진 탐색: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 이진탐색: 반으로 쪼개면서 탐색하기 이진탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자. step1: 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. 중간점이 실수일 때는 소수점 이하를 버린다. 그림에서 각각의 인덱스는 시작점은 [0].. 정렬: 백준 18870 파이썬 문제: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) # set 자료형으로 중복을 없애준 후 정렬 s_array = sorted(set(array)) # 딕셔너리 자료형을 사용해 시간복잡도를 크게 줄임 dic = {s_a.. 이전 1 2 3 4 5 6 7 8 9 다음
