짧은코딩

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이(맞음) n, m = map(int, input().split()) dic = {} for i in range(n): site, password = map(str, input().split()) dic[site] = password answer = [] for i in range(m): x = input() answer.append(dic[x]) for i in ..

해결법 이 문제도 보텀업 방식으로 푸는 문제이다. 리스트 d에 작은 수부터 체크하면서 푼다. 이 문제의 핵심 풀이 방식은 지금의 숫자와 비교했을 때, 동전의 숫자만큼 뺀 숫자가 존재하면 당연히 동전 수만큼 더한 수도 존재한다는 것이다. 풀이 n, m = map(int, input().split()) ary = [] for i in range(n): ary.append(int(input())) d = [10001] * (m+1) d[0] = 0 # 동전 수만큼 반복 for i in range(n): # 가장 작은 동전 수부터 구하려는 목표 수까지 반복 for j in range(ary[i], m+1): # (i-k)원을 만들 수 있으면 if d[j - ary[i]] != 10001: d[j] = min(d..

다이나믹 프로그래밍은 종종 결과가 너무 클 수 있어서 어떤 수로 나눠서 출력하라고 한다. 풀이법 -N이 3일 때의 예시 1. N이 3이고, i-1번째 즉, 2번 칸까지 채워져 있으면 경우에 수는 1개이다. 2. i-2번째 즉, 1번 칸까지 채워져 있으면 경우의 수는 2가지이다. -점화식 따라서 점화식은 이렇게 구할 수 있다. 풀이 n = int(input()) d = [0] * 1001 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]) 점화식에 맞게 코딩을 했다. 이 문제의 풀이도 처음엔 생각하지 못했다. 다이나믹 프로그램을 코딩하면 쉽지만 점화식 같은 풀이를 생각하는 것이 어렵다. 앞으..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 내 풀이(문제를 잘 읽자) n = int(input()) d = [0] * (10**6 + 1) for i in range(2, n+1): d[i] = d[i-1] + 1 if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) if i % 2 == 0: d[i] = min(d[i], d[i//2] + 1) print(d[n]) 이 문제도 어제 "이것이 취업을 위한 코딩테스트다"에서 푼 문제와 굉장히 유사하다. 사실 처음엔 풀지 못해서 어제 공부한 것을 다시 봤다. 그리고 나중에 풀었는데..

교재 풀이 이렇게 바로 옆을 털면 지금 창고를 털지 못한다. 그리고 2번 떨어진 창고를 털면 지금 창고를 털 수 있다. 따라서 바로 옆 창고 vs (옆옆 창고 + 현재 창고) 이렇게 비교해서 더 큰 값을 찾아야 한다. n = int(input()) ary = list(map(int, input().split())) d = [0] * 100 d[0] = ary[0] d[1] = max(ary[0], ary[1]) for i in range(2, n): d[i] = max(d[i-1], d[i - 2] + ary[i]) print(d[n-1]) 이런 풀이가 나온다. 위에서 설명했듯이 옆 창고 vs (옆옆 창고 + 현재 창고)를 비교하면서 푸는 문제이다. 이 문제를 다시 풀면서 for문 안에 max에서 (옆옆..

비효율적으로 푼 내 풀이 #내가 풀어본 비효율적인 방식 from collections import deque x = int(input()) answer = 0 q = deque([(x, 0), (x-1, 1)]) while True: t = q.popleft() nx = t[0] count = t[1] if nx == 1: answer = count break if (nx % 5) == 0: q.append((nx // 5, count+1)) q.append(((nx // 5) - 1, count+2)) if (nx % 3) == 0: q.append(((nx // 3) - 1, count+2)) if (nx % 2) == 0: q.append(((nx // 2) - 1, count+2)) print(a..

최적의 해를 구하기 위해 시간 소요가 많거나 메모리를 많이 차지하는 문제는 컴퓨터로도 해결하기 어렵다. 그래서 연산 속도, 메모리를 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 어떤 문제는 메모리 공간을 약간만 더 사용하면 속도를 비약적으로 증가시킬 수 있다. 이런 것을 동적 계획법이라고 한다. 다이나믹 프로그래밍 방식은 탑다운, 보텀업 2가지 방식이 있다. 특히 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법도 있다. 프로그래밍에서 다이나믹은 '프로그램 실행되는 도중에'라는 의미이다. 하지만 다이나믹 프로그램에서 '다이나믹'은 이런 의미가 아니다. -피보나치 수열 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시는 피보나치 수열이 있다. 피보나치 수열의 점화식(인접한 항..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 내 풀이(반례 보고 맞춤) n, m = map(int, input().split()) ary = [] for i in range(n): ary.append(int(input())) start = 1 end = max(ary) answer = 0 while (start = mid: total += ary[i] // mid #너무 짧게 짤랐다. if total >= m: ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 내 풀이(맞음) n, m = map(int, input().split()) ary = list(map(int, input().split())) start = 0 end = max(ary) answer = 0 while (start mid: total += ary[i] - mid if m > total: end = mid - 1 else: start = mid..

이 문제는 전형적인 이진 탐색 문제이자 파라메트릭 서치 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 예/아니요로 답하는 문제인 결정 문제로 바꾸어 해결하는 기법이다. 이 문제 풀이는 절단기 높이를 반복해서 조정하는 것이다. 당연한 말이지만 절단기 높이는 0부터 가장 긴 떡의 길이 안에 있어야 한다. 따라서 절단기의 범위인 0~가장 긴 떡의 길이를 고려하면 된다. start는 0이고 end는 가장 긴 떡의 길이로 두면 된다. 내 풀이 n, m = map(int, input().split()) ary = list(map(int, input().split())) ary.sort() def search(ary, target, start, end): mid = (start + end) // 2 sum = 0..