코르시카's Blog

Greedy -> D and C -> 다이나믹 프로그래밍 참조 https://syh39.github.io/algorithm/algorithm_DandC_DP/ Divide-and-conquer 와 Dynamic Programming 비교 Divide-and-conquer syh39.github.io

■ 비트마스킹 1) 정의 : 어떠한 데이터를 bit형태로 나타내고, 비트 연산을 통해 문제를 해결하는 방법 2) 장점 : 비트연산을 통한 삽입, 삭제, 조회(multiple indexing처럼 동작 가능)가 간단 간결한 코드 빠른 연산 비트마스크 정수표현으로 다이내믹 프로그래밍 가능 ■ 자료형의 변환 > 사용하고자 하는 형식을 표현하는 이진법으로 구현 switch_states = [True, False, False, True, True, False, False, False, True, True] switch_states = 0b1001100011 # prefix '0b'를 붙여 이진수 표현 다른 자료형에서 binary로 바꾸는 법 1) 일반적 int bin( ) 함수를 사용, binary string을 ..

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

■ 일반적 알고리즘의 시간복잡도 시간 복잡도 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) - 잔재미코딩 프로그래밍 연습 숫자가 들어 있는 리스트가 주어졌을 때,..