해킹왕 양선규

# 끝나는시간으로 정렬하지 않으면 일찍 시작하고 아주 늦게 끝나는 회의에 말릴 수 있다 # 시작시간으로 정렬해야 회의목록을 순차적으로 돌면서 진행 가능하다 import sys input = sys.stdin.readline N = int(input()) # 회의 개수 talkList = [] # 회의 리스트 (시작시간, 종료시간) for _ in range(N): talkList.append(list(map(int, input().split()))) talkList.sort(key = lambda x: (x[1], x[0])) # 회의 리스트 정렬 ( 끝나는시간으로 정렬 후 시작시간으로 정렬 ) cnt = 1 # 회의개수 셀 변수 end = talkList[0][1] # 첫 회의 끝나는시간을 미리 초기화..

import sys input = sys.stdin.readline T = int(input()) # 테스트 케이스 개수 for _ in range(T): # 테스트 케이스 개수만큼 진행한다 N = int(input()) # 동전 종류 개수 coinBox = list(map(int, input().split())) # 동전 입력받기 coinBox.insert(0, 0) # 0번 인덱스에 0넣기. 첫번째 동전부터 점화식을 적용하기 위함. money = int(input()) dp = [[0] * (money + 1) for i in range(N + 1)] # 목표금액만큼 한 행을 길게, 동전갯수만큼 한 열을 길게 for i in range(N + 1): dp[i][0] = 1 # 동전이 뭐든 간에 0을 ..

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 2 for i in range(3, x + 1): d[i] = (d[i-1] + d[i-2]) % 15746 print(d[x]) 다이나믹 프로그래밍 문제이다. 점화식만 찾으면 아주 간단하게 해결할 수 있다. 계산값을 저장해둘 DP테이블(리스트 d)를 생성하고, 초기값을 넣어준다. d[1]엔 1길이의 수열에서 나올 수 있는 경우의 수의 개수, d[2]엔 2길이, d[x]엔 x길이의 수열에서 나올 수 있는 경우의 수의 개수가 들어간다. 타일 경우의 수를 구하는 것은 언뜻 답이 없어 보이지만, 규칙이 있다. 현재 값들에 1을 붙이고, 이전 값들에 00을 붙이면 그게 다음 값이 된다. 즉 N=4 일 때의 경우의 수를 구..

string = input().split('-') result = 0 for i in string[0].split('+'): result += int(i) for i in string[1:]: for j in i.split('+'): result -= int(j) print(result) 그리디 알고리즘 문제이다. 문제 원리는 매우 간단하다. 숫자, '+', '-' 세 가지로만 구성된 문자열이 주어진다. 숫자로 시작해서 숫자로 끝나고, 연산자는 숫자 사이사이에 온다. 여기서 괄호를 원하는 곳에 추가해, 가장 작은 값을 만들어내면 된다. 근데 조금 생각해보면 알 수 있겠지만, 첫번째로 등장하는 '-' 이후의 값들은 전부 뺄 수 있다. 그리고 '-' 이전의 값들은 전부 더하면 된다. 문제의 원리는 쉽다. 하..

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 1 for i in range(3, x + 1): d[i] = d[i-1] + d[i-2] print(d[x]) 간단한 DP 문제이다. 재귀함수로 구현하면 입력값이 90까지이기 때문에 메모리가 터져버린다. x가 1, 2일 경우만 리스트에 등록해 둔 후 간단한 반복문을 돌리면 된다. 재귀 구현했을 경우 90이면 정말 컴퓨터가 터지기 직전까지 가는데 상향식 DP방식인 반복문으로 구현하면 대략 90번정도만 연산하면 되기 때문에 문제를 해결할 수 있다.

N, money = map(int, input().split()) # 동전 종류, 돈 coinBox = [] for _ in range(N): coinBox.append(int(input())) coinBox.reverse() cnt = 0 for coin in coinBox: # 큰 동전부터 차례로 대입된다 if money >= coin: cnt += money // coin money = money % coin print(cnt) 그리디 알고리즘으로 해결할 수 있는 문제이다. 매 순간 최적의 선택을 하면 되기 때문에, 구현이 그리 어렵진 않다. 동전을 입력받은 후, 반복문을 돌리면 큰 동전부터 나오도록 reverse()메소드로 뒤집는다. 이후 큰 동전부터 반복문을 돌며, 남은 돈이 동전 가치보다 같거..

import sys input = sys.stdin.readline x = int(input()) d = [0] * (x + 1) path = ['' for _ in range(x + 1)] path[1] = '1' for i in range(2, x + 1): d[i] = d[i - 1] + 1 prev = i - 1 if i % 3 == 0 and d[i // 3] + 1

x = int(input()) d = [0] * ((10 ** 6) + 1) for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) print(d[x]) 다이나믹 프로그래밍 문제이다. d는 메모이제이션(값을 저장해 놓을)할 리스트. i는 현재 계산중인 숫자 d[i] 는 i에 대한 최소연산횟수이다. 숫자 2부터 바텀 업 방식으로 d리스트를 채워나가 최종적으로 x의 최소연산횟수를 구하는 것이다. 이 문제는 3가지 연산을 할 수 있다. 1을 빼기, 2로 나누기, 3으로 나누기 하지만 2나 3으로 나눠진다고 해서 무조건..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..

매일매일 엄청난 양의 지식을 머리에 꾸역꾸역 넣고 있다. 공부가 잘 안 되는 것 같고, 집중도 안 되는 것 같고. 남들은 더 열심히 하는 것 같고, 나는 부족한 것 같고 하는 생각이 계속계속 들어도, 멈춰서 차근히 돌아보면 지금의 나는 입소날인 3월18일보다 몇 배로, 말도 안되게 빠른 속도로 성장했다. 실질적인 웹 개발이나 프로젝트 경험이 전무하던 내가 입소 4일만에 어엿한 웹사이트를 하나 만들어 냈고, 프로젝트 경험이 생겼다. 알고리즘의 ㅇ자도 모르던 내가 2주만에 DFS, BFS, 백트래킹, 최소스패닝트리, 위상정렬, 여러가지 그래프 이론, 스택, 큐, 힙, 정렬, 재귀함수, CS지식 등등 이것보다 훨씬 많은 말도 안되게 많은 지식을 습득했으며, 백준 티어도 어느새 골드5가 되었다. 하루하루가 정말..