Divide and Conquer vs. Dynamic Programming “Divide and Conquer"와 “Dynamic Programming"은 모두 복잡한 문제를 더 작은 부분으로 나누어 해결하는 전략이지만, 접근 방식과 적용 상황에서 중요한 차이가 있다. 분할 정복은 문제를 독립적인 하위 문제로 나누어 효율성을 높이는 반면, 동적 계획법은 중복되는 하위 문제의 결과를 저장하여 재계산을 방지한다. 알고리즘 선택은 문제의 성격에 따라 달라져야 한다. 하위 문제 간 중복이 있는지, 최적 부분 구조가 있는지를 파악하여 적절한 알고리즘을 선택하는 것이 중요하다. Divide and Conquer(분할 정복) 알고리즘 분할 정복은 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 방법이다. 이 알고리즘은 다음과 같은 세 단계로 구성된다: ...
Collision Resolutions 해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)에 적용하여 특정 인덱스(Index)에 데이터를 저장하는 자료구조이다. 그러나 서로 다른 키가 같은 해시 인덱스로 매핑되는 경우가 발생할 수 있으며, 이를 충돌(Collision) 이라고 한다. 해시 함수는 임의 크기의 데이터를 고정된 크기의 값으로 매핑한다. 해시 테이블의 크기가 제한되어 있기 때문에, 서로 다른 키들이 같은 해시 값(버킷 인덱스)을 가지는 ‘충돌’이 불가피하게 발생한다. 이는 ‘비둘기집 원리(Pigeonhole Principle)‘에 의해 증명된다 - 가능한 키의 수가 해시 테이블의 크기보다 크면 충돌은 반드시 발생한다. ...
메모이제이션 (Memoization) 메모이제이션은 “기억하다"라는 뜻의 라틴어 ‘memorandum’에서 유래했다. 이 기법은 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해두고 필요할 때 다시 계산하지 않고 저장된 값을 사용하는 방식이다. 실생활에 비유해보면, 책을 보다가 모르는 단어를 사전에서 찾았을 때 메모이제이션 미사용: 같은 단어가 나올 때마다 매번 사전을 찾음 메모이제이션 사용: 찾은 단어의 의미를 메모장에 적어두고, 다시 나오면 메모장을 참고 로 이해 가능하다. 메모이제이션의 작동 원리 함수가 호출될 때 입력값을 확인한다. 해당 입력값에 대한 결과가 이미 저장되어 있다면, 저장된 결과를 즉시 반환한다. 저장된 결과가 없다면, 함수를 실행하고 그 결과를 저장한 후 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 def memoized_function(n, memo={}): # 1. 이미 계산된 값인지 확인 if n in memo: return memo[n] # 2. 새로운 값 계산 result = ... # 계산 로직 # 3. 계산된 값을 저장 memo[n] = result # 4. 결과 반환 return result 메모이제이션의 장점 실행 속도 향상: 중복 계산을 피함으로써 프로그램의 실행 속도를 크게 높일 수 있다. 자원 효율성: 계산 비용이 높은 작업의 결과를 재사용함으로써 컴퓨터 자원을 효율적으로 사용할 수 있다. 메모이제이션의 사용 예시 가장 대표적인 예시로 피보나치 수열 계산을 들 수 있다. 일반적인 재귀 함수로 구현하면 중복 계산이 많이 발생하지만, 메모이제이션을 적용하면 성능을 크게 개선할 수 있다. ...
테이블레이션(Tabulation) Tabulation은 프로그래밍에서 동적 프로그래밍(Dynamic Programming)의 한 기법으로, 복잡한 문제를 해결하기 위해 사용되는 방법이다. Tabulation은 ‘표를 만든다’는 의미로, 문제의 해결 과정을 표 형태로 정리하는 기법이다. 이 방법은 작은 부분 문제(subproblem)부터 시작하여 점진적으로 더 큰 문제를 해결해 나가는 상향식(bottom-up) 접근 방식을 사용합니다. Tabulation의 작동 원리 문제 정의: 해결하고자 하는 문제와 그 부분 문제들을 명확히 정의한다. 표 초기화: 부분 문제의 결과를 저장할 표(보통 배열이나 리스트)를 만든다. 기본 케이스 설정: 가장 작은 부분 문제에 대한 해답을 표에 채운다. 반복적 계산: 작은 부분 문제부터 시작하여 큰 문제로 나아가며 표를 채운다. 최종 결과 도출: 표의 마지막 항목이 전체 문제의 해답이 된다. Tabulation의 예시: 피보나치 수열 피보나치 수열을 계산하는 예시 ...