Juni_Dev_log

시간 복잡도 시간 복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다. 알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데, 수행시간에 해당하는 것이 "시간 복잡도(Time Complexity)" / 메모리 사용량에 해당하는 것이 "공간 복잡도(Space Complexity)" 이다. 연산 횟수를 카운팅 할 때 3가지 경우가 있다. 1. 최선의 경우 Best Case 2. 최악의 경우 Worst Case 3. 평균적인 경우 Average Case 평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워진다. 그러므로, 최악의 경우로 알고리즘의 성능을 파악한다. 2-1 Program Step 에서 Elementary Op..

📌 시간복잡도 O(n) : for문을 1번 사용 📌 공간복잡도 O(1) : 변수로 저장하는 것이 없고, 임의로 저장하는 heap memory에 해당하는 dp[i] 값들만 저장공간에 남는다. Problem You are a professional robber planning to rob houses along a street. : 당신은 거리를 따라 집을 강탈하려는 전문 강도이다. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. : 각각의 집에는 일정 금액의 돈이 숨겨져있다. 이 장소의 모든 집은 원으로 배열화되어있다. That means the first house is t..

동적 계획법이란? 동적 계획법(Dynamic Programming)은 일반적으로 문제를 풀기 위해서, 문제를 여러 개의 작은 문제로 쪼개서, 그 값들을 결합하여 최종적인 결과를 얻는 것이다. 그러기 위해서, 각 하위 문제들의 값을 별도의 변수 등에 저장해서 필요할 때마다 꺼내 쓰는 것이다. 이러한 것을 보여주는 예시로 피보나치 수열을 들 수 있다. 1 2 3 4 5 6 7 def fibonacci(n): if n == 0: return 0 if n == 1 or n == 2: return 1 else: return fibonacci(n-1) + fibonacci(n-2) cs 피보나치 수열을 재귀함수를 이용해서 구현하면 정말 쉽게 구현할 수 있다. 하지만, 효율성 측면에서 보면 좋은 코드는 아니다. 위 ..

결과는 같은데, 과정은 다르며, 이에 따른 여러가지 알고리즘이 있다. 이처럼 다양한 알고리즘도 성능이 제 각각이다. 그렇기 때문에 좋은 성능의 알고리즘을 고르는 것이 굉장히 중요하다. 가장 좋은 알고리즘을 고르기 위해서는 알고리즘의 효율성을 따지는 데 이 때 두 가지로 나눌 수 있다. 시간적 효율성 (얼마나 이 알고리즘이 빠른가) / 공간적 효율성(메모리를 얼마나 차지하는가) => 얼마나 빠른 시간으로 처리하는가 ('시간 복잡도') / 얼마나 메모리를 차지하는가 ('공간 복잡도') 알고리즘의 속도에 영향을 주는 요소는 굉장히 많지만, 제일 영향을 많이 주는 것은 '입력이 n일 때 연산 횟수' 이다. 예를 들어, 1~100 까지 순서대로 더하는 프로그램과 1~1000까지 순서대로 더하는 프로그램을 만들었다..