본문 바로가기

Algorithm 💡272

[DP] Dynamic Programming 알고리즘의 개념 및 코드 1) Dynamic Programming 이란 ? Dynamic Programming은 또 다른 자료구조(메모리)에 계산한 정보들을 저장함으로써 중복되는 연산을 줄이고, 이로써 프로그램의 수행 속도를 개선하는 알고리즘이다. DP는 완전 탐색(BFS, DFS)과 같이 수많은 경우의 수를 따져보아야 할 때, 경우의 수가 수없이 많을 때 메모리 공간을 사용하여 수행시간을 단축시키는 알고리즘이다. 여러 개의 작은 문제들을 먼저 푼 후에 그 결과를 바탕으로 더 큰 문제를 해결하는 알고리즘으로, 한번 계산한 문제는 다시 계산하지 않도록 메모리에 저장하고, 필요한 경우 다시 계산하지 않고 저장된 값을 사용한다.(매 순간 최적의 값을 저장함) 쉽게 설명하면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서.. 2023. 2. 27.
[백준 13305번] 주유소 import sys input = sys.stdin.readline # n 입력받기 n = int(input()) # 총 비용 total = 0 # n-1개의 거리를 저장하는 리스트 distance = list(map(int,input().split())) # 주유소의 리터당 가격을 저장하는 리스트 price = list(map(int,input().split())) # 남은 거리 수 remain = sum(distance) # 현재 최소 거리 min_price = price[0] # 현재 누적된 거리 sum_distance = distance[0] for i in range(n-1): if i == n-2: total += (sum_distance * min_price) break if min_price 2023. 2. 24.
[백준 2108번] 통계학 import sys input = sys.stdin.readline # n 입력받기 n = int(input()) # n개의 값을 저장하는 리스트 array = [0]*n # 빈도수를 저장하는 리스트 count_list = [] # 최빈값 mode = 0 # 입력받기 for i in range(n): array[i] = int(input()) # 중간 인덱스 mid_index = n//2 # 오름차순 정렬 array.sort() # 집합 자료형 사용 set_n = set(array) # 사전 자료형 사용 dictionary = dict() # 사전 자료형에 숫자 '값 : 빈도수(카운팅)' 저장 => 시간복잡도 최소화 for i in array: if i not in dictionary: dictionar.. 2023. 2. 24.
[백준 25305번] 커트라인 import sys input = sys.stdin.readline n, k = map(int,input().split()) array = sorted(list(map(int,input().split()))) print(array[n-k]) 2023. 2. 24.
[백준 2587번] 대표값2 import math array = [0] * 5 for i in range(5): array[i] = int(input()) array.sort() print(math.floor(sum(array)/5)) print(array[2]) 2023. 2. 24.
[백준 18870번] 좌표 압축 import sys input = sys.stdin.readline n = int(input()) array = list(map(int,input().split())) set_a = set(array) list_a = sorted(list(set_a)) dictionary = dict() for i in range(len(list_a)): dictionary[list_a[i]]=i for i in array: print(dictionary.get(i),end=" ") 2023. 2. 23.

티스토리툴바