코르시카's Blog

참조 : debuglog.tistory.com/68 Python으로 알고리즘 공부 03. 계수 정렬 (Counting Sort) 계수 정렬 (Counting Sort) 파이썬으로 구현 계수 정렬은 비교 정렬이 아니다. K가 정수일 때 (즉, K가 어떤 최대값을 가질때), 입력 요소들이 1부터 K까지의 정수라고 가정. 히스토그램과 같이 각 요소 debuglog.tistory.com m.blog.naver.com/PostView.nhn?blogId=dnpc7848&logNo=221439395086&proxyReferer=https:%2F%2Fwww.google.com%2F ■ 계수정렬 정의 : 중복된 값이 많이 분포되어 있는 자연수의 배열 정렬시 효과적 - 일반적으로 양의 정수(자연수)에 대해서만 정렬 가능..

참조 : syujisu.tistory.com/147 동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 알고리즘 1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고 syujisu.tistory.com ■ 동적 계획법(aka. DP) 1) 정의 : 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 > 상향식 접근, 하위 해답에서 출발, 결과값 이용해 상위 문제 해결 > 하위 문제 해결과 상위 문제 해결 방식이..

참고 : debuglog.tistory.com/67 Python으로 알고리즘 공부 02. 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) 파이썬으로 구현 퀵 정렬은 분할 정복 알고리즘의 좋은 예이다. 리스트 중 하나를 pivot으로 정하고, pivot보다 작은 아이템은 왼쪽, pivot보다 큰 아이템은 오른쪽으로 보내면서 pi debuglog.tistory.com ■ 퀵 소트 1) 정의 : 분할정복을 사용하여 piviot 값을 기준으로 하여 좌, 우를 나누어 정렬하는 방식 > (꼭 그래야 하는 것은 아니지만) piviot 보다 작은 아이템은 왼쪽, 큰 아이템은 오른쪽 > pivot은 랜덤 값이 제일 적당 ...OR... 평균에 가까운 수 > 재귀 형식 사용 : 점화식의 형태 2) 복잡도 ..

■ 일반적 알고리즘의 시간복잡도 시간 복잡도 worst 시간 복잡도 least for문 1 / while문 1 당== iteration O(N) python sorting O(N*log(N)) ■ python list Operation Example Big-O Notes Index l[i] O(1) Store l[i] = 0 O(1) Length len(l) O(1) Append l.append(5) O(1) Pop l.pop() O(1) l.pop(-1) 과 동일 Clear l.clear() O(1) l = [] 과 유사 Slice l[a:b] O(b-a) l[:] : O(len(l)-0) = O(N) Extend l.extend(…) O(len(…)) 확장 길이에 따라 Construction list..

■ 동적계획법, (aka. DP) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 문제의 해를 활용해서 큰 부분 문제를 해결 ( bottom to up-towards solution ) - 이 과정에서 Memoization을 이용, 계산 결과가 저장되는 형식을 채택해 전체 실행 속도를 높임 - 최종 해를 구하는 과정에서 greedy 방식이 사용되는 경우도 많음 ■ 예시 1) Fibonacci 예시 1 def fibo_dp(num): cache = [ 0 for index in range(num + 1) ] cache[0] = 0 cache[1] = 1 for index in range(2, num + 1): cache[index] = cache[index - 1] + cache[index - 2] ..

https://www.fun-coding.org/Chapter14-dp_divide.html 파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩 프로그래밍 연습 피보나치 수열: n 을 입력받아서 다음과 같이 계산됨 n 을 입력받았을 때 피보나치 수열로 결과값을 출력하세요 함수를 fibonacci 라고 하면, fibonacci(0):0 fibonacci(1):1 fibonacci(2):1 fibon www.fun-coding.org https://www.fun-coding.org/Chapter13-recursive.html 파이썬과 컴퓨터 사이언스(기본 알고리즘): 재귀 용법 (Recursive Call) - 잔재미코딩 프로그래밍 연습 숫자가 들어 있는 리스트가 주어졌을 때,..