본문 바로가기

알고리즘 (Python)

 (259)
[최단 경로 알고리즘] 가장 빠른 길 찾기 최단 경로 알고리즘 - 말 그대로 가장 짧은 경로를 찾는 알고리즘 - '한 지점에서 다른 특정 지점까지의 최단 경로', '모든 지점에서 다른 모든 지점까지의 최단 경로' 등의 사례가 존재 - 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많음 - 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용됨 음의 간선 - 0보다 작은 값을 가지는 간선 - 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택됨 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 ..
[다이나믹 프로그래밍] 효율적인 화폐 구성 - 파이썬(python) 효율적인 화폐 구성 난이도 : 中 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) array = [] for i in range(n): array.append(int(input())) d = [99999] * (m+1) d[0] = 0 for i in range(n): for j in range(array[i], m+1): d[j] = min(d[j], d[j-array[i]] + 1) if d[m] == 99999: print(-1) else: print(d[m]) 예시 # 정수 N, M을 입력 받기 n, m = map(int, input().split()) # N개의 화폐 단위 정보를 입력 받기 array = [] ..
[다이나믹 프로그래밍] 바닥 공사 - 파이썬(python) 바닥 공사 난이도 : 中下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) d = [0] * 1001 d[0] = 0 d[1] = 1 d[2] = 3 for i in range(3, n+1): d[i] = (d[i-1] + d[i-2]*2) % 796796 print(d[n]) 예시 # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796 ..
[다이나믹 프로그래밍] 개미 전사 - 파이썬(python) 개미 전사 난이도 : 中 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) array = list(map(int, input().split())) d = [0] * 100 d[0] = array[0] d[1] = max(d[0], array[1]) for i in range(2, n): d[i] = max(d[i-1], d[i-2] + array[i]) print(d[n-1]) 예시 # 정수 N을 입력 받기 n = int(input()) # 모든 식량 정보 입력 받기 array = list(map(int, input().split())) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # 다이나믹 프로그래밍(Dyna..
[다이나믹 프로그래밍] 1로 만들기 - 파이썬(python) 1로 만들기 난이도 : 中下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 x = int(input()) dp = [0] * 30001 for i in range(2 , x+1): dp[i] = dp[i-1] + 1 if i % 2 == 0: dp[i] = dp[i//2] + 1 if i % 3 == 0: dp[i] = dp[i//3] + 1 if i % 5 == 0: dp[i] = dp[i//5] + 1 print(d[x]) 예시 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1000001 # 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) for i in range(..
[다이나믹 프로그래밍] 다이나믹 프로그래밍 다이나믹 프로그래밍 - 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 - 탑다운과 바텀업 2가지 방식, 메모이제이션 기법이 있음 - 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식 - 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 문제들의 중복 여부를 확인 - 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤 (탑다운 방식) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션 기법을 적용할 수 있으면 코드를 개선 다이나믹 프로그래밍을 사용 가능한 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 ..
[이진 탐색 알고리즘] 떡볶이 떡 만들기 - 파이썬(python) 떡볶이 떡 만들기 난이도 : 中 풀이 시간 : 40분 시간 제한 : 2초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) array = list(map(int, input().split())) start, end = 0, max(array) while(start mid: total = total + (i - mid) if total < m: end = mid - 1 else: result = mid start = mid + 1 print(result) 예시 # 떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n, m = list(map(int, input().split(' '))) # 각 떡의 개별 높이 정보를 입력 array = list(map(int, in..
[이진 탐색 알고리즘] 부품 찾기 - 파이썬(python) 부품 찾기 난이도 : 中下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 def binary_search(array, target, start, end): while start target: end = mid - 1 else: start = mid + 1 return None n = int(input()) array = list(map(int, input().split())) m = int(input()) x = list(map(int, input().split())) for i in x: result = binary_search(array, i, 0, n-1) if result == None: print('no', end=' ') else: print('yes', end='..
[이진 탐색 알고리즘] 범위를 반씩 좁혀가는 탐색 순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위하여 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음 - 이름처럼 순차로 데이터를 탐색한다는 의미 - 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단 - 리스트에 특정 값의 원소가 있는지 체크할 때 사용 - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N) 이진 탐색 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 - 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데..
[정렬 알고리즘] 두 배열의 원소 교체 - 파이썬(python) 두 배열의 원소 교체 난이도 : 下 풀이 시간 : 20분 시간 제한 : 2초 메모리 제한 : 128 MB 해답 n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() b.sort(reverse=True) for i in range(k): if a[i] > b[i]: a[i], b[i] = b[i], a[i] else: break print(sum(a)) 예시 n, k = map(int, input().split()) # N과 K를 입력 받기 a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기 b = list(m..

티스토리툴바