참고한 책 ; 나동빈 (2020). . 서울시: 한빛미디어. [그리디 알고리즘] 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 다시 말해서, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 정렬, 최단 경로, 폴로이드 워셜, 다익스트라 알고리즘 처럼 특정 알고리즘을 미리 외우고 있어야문제를 풀 수 있는 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라는 특징이 있다고 한다. (참고로 다익스트라 알고리즘은 엄밀히 말해 그리디로 분류된다고 하니 특이 케이스라 알아두자.) 그리디 알고리즘 유형의 문제는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 한다. " 단순히 현재 상황에서 가장 좋아 보이는 것만 선..
알고리즘
[퀵정렬] 기준보다 작은 값과 큰 값을 분리한 후 다시 합친다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 병합 정렬과 더불어 정렬 라이브러리의 근간이 되는 알고리즘이다. 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)로 설정한다. 이상적인 경우, 분할이 절반씩 일어난다면 전체 연산 횟수로 \( O(N*logN) \)을 기대할 수 있다. 평균적으로 퀵 정렬은 \( O(N*logN) \)의 시간 복잡도를 갖는다. 그러나 최악의 경우, 분할이 일어나지 않아 \( O(N^2) \)의 시간 복잡도를 가질 수 있다. ( 기본 라이브러리를 통한 정렬은 최악의 경우를 고려한 설계가 되어있기 때문에 항상 늘 \(O(N*logN)\)을 보장해니 안심하도록 하자. ) 삽입정렬과 달..
[병합 정렬] 자료 구조를 분할하고 각각의 분할된 자료구조를 정렬한 후, 다시 병합하여 정렬한다. 병합 정렬은 정확히 반절씩 나눈다는 점에서 늘 항상 \( O(N*logN) \) 의 시간 복잡도를 가집니다. 퀵 정렬의 경우 피벗 값에 따라 편향되었을 때, 최악의 경우 \( O(N^2) \) 를 갖는다는 점에서 병합 정렬은 이보다 나은 장점을 갖는다. 하지만 그렇다고 해서 평균적으로 병합 정렬이 더 빠르다는건 아니다. 분할 단계 가로의 길이는 \(N\), 높이는 \( log_2N \) 이 됩니다. 처리하는 데이터의 갯수는 한번 쪼갤 때 마다, 2의 지수로 증가하기 때문에 N이 아니라 훨씬 적은 \( log_2N\) 만으로 처리 할 수 있게 된 것 입니다. 병합 단계 정렬하며 병합해갑니다. 이미 정렬이 되어..
[재귀] 나 자신을 다시 호출하는걸 재귀라고 한다. 바로 실습으로 가보자. [실습 1] 유클리드 호제법 # 유클리드 호제 def gcd(a,b): c = a % b if c == 0 : return b return gcd(b,c) # return을 빠트려서는 안된다. a, b = map(int,input('최대 공약수를 구하고픈 두 수 ? : ').split()) print(f'{a}, {b}의 최대공약수는 {gcd(a,b)}') return gcd(b,c)에서 return을 빼먹을 경우, b의 값과 관련 없이 함수 gcd(a,b)는 None을 return하게 된다. 왜냐면 자기 자신을 불러오기 전 함수 gcd(a,b)는 무엇을 return할껀지가 안정해지기 때문. 백준 문제 풀이를 통해 재귀 알고리즘의..
