알고리즘
-
Dynamic Programming(동적 계획법)알고리즘/동적 계획법 2022. 9. 6. 22:45
도입 오늘은 동적계획법(DP)에 대해 소개 해보겠다. 먼저 필자는 아직도 동적 계획법을 잘 못한다. Dynamic Programming이라는 어려운 이름에 ㅎㄷㄷ 할 수 있지만, 당시 연구실에서 연구비 많이 받을려고, 이런 이름으로 지었다고 한다. 1. 동적계획법 정의 먼저 동적계획법은 어떠한 문제를 다른 부분 문제로 나누는 것을 의미한다. 예를 들어 대표적인 예는 피보나치 수열이다. Fibo n = Fibo n-1 + Fibo n-2 로 나타낼 수 있다. Fibo n이라는 문제를 부분적으로 나눈 것이다. 이 경우에 n부터 시작해 함수 호출이 약 2배씩 증가함으로 총 O(2^N)에 근사하는 시간복잡도를 가지지만, 메모이제이션이라는 기법을 사용하면 간단해진다. 2. 메모이제이션 우리는 4번째 항의 피보나치..
-
Greedy(욕심쟁이)알고리즘/그리디 2022. 7. 31. 10:08
흔히 풀 수 있고, 어려운 것은 어려운 그리디에 대해 말해보겠다. 그리디는 단편적인 큰 코스트를 취하는 방법이다. 1.그리디의 예시 빠르게 본론으로 넘어가겠다. 백문이 불아일견이라 했다. 우리가 1원 5원 10원의 동전들이 무수히 많다고 하자. 자연수인 N이 주어질때 동전들의 합으로 N을 만들어야하는 상황에 사용되는 동전들의 개수를 최소화 시킬려면 어떻게 해야할까? 2.해답 어짜피 1원 5개를 쓰일 상황에선 5원을 하나 쓰는게 이득이고 5원 2개 쓰일빠엔 10원 하나를 쓰는게 이득이다. 고로 10원을 N에서 계속 빼다가 5원을 빼고 1원을 빼는 것. 가장 큰 액수부터 빼는게 이 문제의 답이다. 이러한 것 처럼 그리디는 단순히 그 순간만을 위한 최선의 선택을 하는 알고리즘이다. 정당성에 관한 부분은 그 문..
-
시간복잡도알고리즘/기법,기초 2022. 7. 31. 09:52
시간복잡도는 프로그램의 수행시간을 다항식으로 나타내는 것이다. 시간복잡도는 시간제한이 있는 OJ사이트나 코딩 테스트,대회 등에서 중요한 요소이다. 하지만 대부분의 사람들은 시간복잡도를 그냥 대충 계산하는 경향이 있다.(사실 그래도 된다.) 그러나 필자는 깊이 있는 문제 풀이를 위해 시간복잡도가 굉장히 중요한 요소라 생각하기에 이에 대해 말해 보겠다. 1.시간복잡도 계산 그 프로그램에 있는 반복문의 반복 횟수라 봐도 문제가 없다. arr[1]과 같은 한 번에 접근 가능한 것을 O(1)의 시간복잡도를 가졌다 하고, 이는 그 프로그램의 시간복잡도에서 보통 생략된다. 예를 들어보자. n=int(input()) for i in range(n): print(i) 다음의 코드는 i가 0부터 n까지 1씩 증가하는 코드..