아이테킨의 끄적끄적

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이 마지막으로 DP 정복하는것을 향해서!!! 다이나믹 프로그래밍(Dynamic programming, DP)란? 다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다. 나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷..

가장 기본적이고 DFS/BFS 개념문제라고 생각한다. DFS는 깊이우선탐색이라고 하여 그래프 자료구조를 그려놓고 수직의 방향으로 먼저 탐색하는 방법을 말한다. 재귀 혹은 스택 자료구조를 이용하여서 구현할 수 있다. BFS는 넓이우선탐색이라고 하여 그래프에서 수평방향으로 먼저 탐색하는 방법이라고 이해하면 될것 같다. 큐 자료구조를 이용하여 구현한다. # 1260번 # 입력값을 받는 부분 # 인접행렬로 그래프를 표현하였다. n,m,v = map(int,input().split()) graph = [[0]*(n+1) for _ in range(n+1)] for i in range(n+1): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 # DFS구..

수많은 정렬 알고리즘 중 대표적인 5가지 정렬 알고리즘에 대해서 정리해보려고 한다. 버블 정렬(bubble sorting) 선택 정렬(Selection sorting) 삽입 정렬(insertion sorting) 병합 정렬(Merge sorting) 퀵 정렬(Quick sorting) 셸 정렬(shell sorting) 힙 정렬(heap sorting) 우선 시간복잡도 기준으로 나눠보자 O(N²) 버블 정렬 선택 정렬 삽입 정렬 O(N log₂ N) 병합 정렬 퀵 정렬 셸 정렬 힙 정렬 아래에 있는 정렬들이 일단 시간복잡도가 더 빠르니 성능이 좋은 정렬 알고리즘이라 생각해도 될 것 같다. 그러나 언제나 그렇듯 모든 상황에서 아래의 알고리즘이 더 좋다고 단정지을 수는 없다. 1. 버블 정렬(Bubble s..

ㅂㄷㅂㄷ... ㅂㄷㅂㄷ... ㅂㄷㅂㄷ... 이 문제 푸느라 1시간정도 날린것같다... 삽질을 아주 정성스럽게 열심히 했다...ㅠ.ㅠ 어느정도 삽질을 하다가 생각이라는 것을 좀 했어야 했는데 아무생각없이 삽질만 열심히 해버렸다. 다음부터는 더 생각하면서 문제에 접근해야겠다는 교훈을.. # 7568 덩치 n = int(input()) people = [] for i in range(n): people.append(tuple(map(int,input().split()))) # 각 사람별 딕셔너리를 만들어줌. dictpeople = {} for v in people: dictpeople[v] = 1 people.sort(reverse=True) # 몸무게로 내림차순 정렬 rank = 1 for i in rang..

# 2231 분해합 n = int(input()) cons_num = {} for i in range(1,n+1): num = list(map(int,list(str(i)))) num.append(i) cons_num[sum(num)] = [] for i in range(1,n+1): num = list(map(int,list(str(i)))) num.append(i) cons_num[sum(num)].append(i) if n not in cons_num.keys(): print(0) else: print(cons_num[n][0]) 생성자를 역으로 도출하는 방법이 도저히 생각이 안나서 임의의 숫자가 주어지면 그 숫자까지의 생성자를 모두 생성해낸 다음에 딕셔너리와 리스트를 이용해서 답을 구했다. bru..

brute force란? 암호해독에서 사용되는 방법으로 무차별적으로 넣을 수 있는 숫자는 다 시도해보면서 해독하는 방법이다. 시간과 조건만 된다면 가장 단순하면서도 언젠가는 무조건 풀 수 있는 방법이다. 2798번 내 코드 # 2798 블랙잭 n,m = map(int,input().split()) dack = list(map(int,input().split())) target = m for i in range(len(dack)-2): for j in range(i+1,len(dack)-1): for k in range(j+1,len(dack)): sum = dack[i]+dack[j]+dack[k] if sum > m: continue elif target >= m-sum: target = m-sum a..

# 주유소 n = int(input()) dis = list(map(int,input().split())) oil = list(map(int,input().split())) res = 0 i = 0 j = 0 tot_dis = sum(dis) while tot_dis != 0: if oil[i] >= oil[i+1]: res += oil[i]*dis[j] tot_dis -= dis[i] i += 1 j += 1 else: res += oil[i]*dis[j] tot_dis -= dis[j] j += 1 print(res) 일단 입력조건들을 만족시킨 후 기름값을 비교하여 문제를 풀었다. 지금 도시에서의 기름값과 다음 도시에서의 기름값중 지금이 기름이 더 비싸면 다음 도시에 갈 만큼만 기름을 넣어주고 그렇지..

# 잃어버린 괄호 n = input().split('-') first = sum(list(map(int,n[0].split('+')))) for i in range(1,len(n)): first -= sum(list(map(int,n[i].split('+')))) print(first) 최소의 값을 만들기 위해서는 처음에 나오는 수 이외에는 모두 빼기로 연산될 수 있도록 괄호를 넣어줘야 한다. - 기호가 나올때마다 괄호를 시작하고 닫아주면 된다. 예를 들어 55-40+30+80이면 55-(40+30+80) 55+40-30-50-60+50 이면 55+40-(30)-(50)-(60)+50 - 기호가 처음 나올땐 괄호를 열어주고 그 다음 - 기호가 나오면 괄호를 닫아주면 모두 빼는 연산이 된다. *그리디(gr..

백준1931 파이썬 맨 처음 풀었던 내 코드 전체 시간을 집합(set)으로 만들어주고 거기에서 차집합으로 하나하나 빼가면서 검사를 했다. 시간초과가 떠서 새로운 방법을 생각해보아야 했다. 아마도 for문이 중복되는 부분이 있어서 입력값이 커질경우 연산량이 많아지기 때문일 것이다. O(n^2) # 회의실 - 시간초과 # big o 표기법에서 어떻게 되는건지 n = int(input()) conf = [] time = set() for i in range(n): start, end = map(int,input().split()) conf.append([start,end,abs(start-end)]) for j in range(start,end+1): time.add(j) conf.sort(key=lambda..

객체지향프로그램(Object-Oriented Programming, OOP)이란? 먼저 세계에서 가장 유명한 사전인 위키백과에서 말하는 정의를 살펴보자. 객체 지향 프로그래밍(영어: Object-Oriented Programming, OOP)은 컴퓨터 프로그래밍의 패러다임 중 하나이다. 객체 지향 프로그래밍은 컴퓨터 프로그램을 명령어의 목록으로 보는 시각에서 벗어나 여러 개의 독립된 단위, 즉 "객체"들의 모임으로 파악하고자 하는 것이다. 각각의 객체는 메시지를 주고받고, 데이터를 처리할 수 있다. 객체 지향 프로그래밍은 프로그램을 유연하고 변경이 용이하게 만들기 때문에 대규모 소프트웨어 개발에 많이 사용된다. 또한 프로그래밍을 더 배우기 쉽게 하고 소프트웨어 개발과 보수를 간편하게 하며, 보다 직관적인..