본문 바로가기

알고리즘 (Python)/이것이 코딩 테스트다 with 파이썬 (실습)

 (41)
[다이나믹 프로그래밍 알고리즘] 효율적인 화폐 구성 - 파이썬(python) 효율적인 화폐 구성 난이도 : 中 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n, m = map(int, input().split()) coins = [] for i in range(n): coins.append(int(input())) dp_table = [10001] * (m + 1) dp_table[0] = 0 for i in range(n): for j in range(coins[i], m+1): if dp_table[j - coins[i]] != 10001: dp_table[j] = min(dp_table[j], dp_table[j - coins[i]] + 1) if dp_table[m] == 10001: print(-1) else: print(dp_table[m..
[다이나믹 프로그래밍 알고리즘] 바닥 공사 - 파이썬(python) 바닥 공사 난이도 : 中下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) dp_table = [0] * 1001 dp_table[1] = 1 dp_table[2] = 3 for i in range(3, n+1): dp_table[i] = (dp_table[i-1] + (dp_table[i-2] * 2)) % 796796 print(dp_table[n]) 예시 # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1)..
[다이나믹 프로그래밍 알고리즘] 개미 전사 - 파이썬(python) 개미 전사 난이도 : 中 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) foods = list(map(int, input().split())) dp_table = [0] * 100 dp_table[0] = foods[0] dp_table[1] = max(foods[0], foods[1]) for i in range(2, n): dp_table[i] = max(dp_table[i-1], dp_table[i-2] + foods[i]) print(dp_table[n-1]) 예시 # 정수 N을 입력 받기 n = int(input()) # 모든 식량 정보 입력 받기 array = list(map(int, input().split())) # 앞서 계산된 결..
[다이나믹 프로그래밍 알고리즘] 1로 만들기 - 파이썬(python) 1로 만들기 난이도 : 中下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 x = int(input()) dp_table = [0] * 30001 for i in range(2, x+1): dp_table[i] = dp_table[i-1] + 1 if i % 2 == 0: dp_table[i] = min(dp_table[i], dp_table[i // 2] + 1) if i % 3 == 0: dp_table[i] = min(dp_table[i], dp_table[i // 3] + 1) if i % 5 == 0: dp_table[i] = min(dp_table[i], dp_table[i // 5] + 1) print(dp_table[x]) 예시 # 정수 X를 입력 받기 x = ..
[이진 탐색 알고리즘] 떡볶이 떡 만들기 - 파이썬(python) 떡볶이 떡 만들기 난이도 : 中 풀이 시간 : 40분 시간 제한 : 2초 메모리 제한 : 128 MB 해답 n, m = list(map(int, input().split(' '))) ddeoks = list(map(int, input().split())) start, end = 0, max(ddeoks) result = 0 while start mid: 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 = lis..
[이진 탐색 알고리즘] 부품 찾기 - 파이썬(python) 부품 찾기 난이도 : 中下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) goods = list(map(int, input().split())) m = int(input()) wants = list(map(int, input().split())) goods.sort() def binary_search(array, target, start, end): while start target: end = mid - 1 elif array[mid] < target: start = mid + 1 return None result = 0 for i in wants: result = binary_search(goods, i, 0, n-1) if result ==..
[정렬 알고리즘] 두 배열의 원소 교체 - 파이썬(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()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort()..
[정렬 알고리즘] 성적이 낮은 순서로 학생 출력하기 - 파이썬(python) 성적이 낮은 순서로 학생 출력하기 난이도 : 下 풀이 시간 : 20분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) array = [] for i in range(n): input_list = input().split() array.append((input_list[0], int(input_list[1]))) array = sorted(array, key=lambda x: x[1]) for x in array: print(x[0], end=' ') 예시 n = int(input()) array = [] for i in range(n): input_data = input().split() array.append((input_data[0], int(input_data[1..
[정렬 알고리즘] 위에서 아래로 - 파이썬(python) 위에서 아래로 난이도 : 下 풀이 시간 : 15분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 n = int(input()) array = [] for i in range(n): array.append(int(input())) array.sort(reverse=True) for i in array: print(i, end=' ') 예시 n = int(input()) array = [] for i in range(n): array.append(int(input())) array = sorted(array, reverse=True) for i in array: print(i, end=' ') 해설 n과 array에 각각 입력받은 후, 파이썬의 sort() 함수를 사용하여 내림차순으로 정렬하였습니다...
[BFS 알고리즘] 미로 탈출 - 파이썬(python) 미로 탈출 난이도 : 中下 풀이 시간 : 30분 시간 제한 : 1초 메모리 제한 : 128 MB 해답 from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if (nx = n or ..

티스토리툴바