알고리즘

시간복잡도 (Time Complexity)

핵심요소

Big O 표기법 (최악의 경우)

입력 크기 (n)

기본 연산의 횟수

시간복잡도 구하는 법

가장 내부에 있는 기본 연산 파악

반복문이나 재귀의 실행 횟수 계산

전체 수행 시간에 가장 큰 영향을 미치는 항 선택

계수와 낮은 차수의 항 제거

시간복잡도

공간복잡도

Dynamic Programming (동적 계획법)

복잡한 문제를 더 작은 하위 문제로 나누어 해결하고, 각 하위 문제의 결과를 저장하여 재사용함으로써 계산 효율성을 높이는 알고리즘 설계 기법입니다. 이를 통해 중복 계산을 피하고 최적해를 찾을 수 있습니다.

핵심 요소

DP 해결 과정

예시 코드 - 피보나치 수열

이 코드는 피보나치 수열을 DP를 사용하여 구현한 예시입니다. 재귀적 방식 대신 반복문과 배열을 사용하여 효율적으로 계산합니다.

대표적인 DP 문제

피보나치 수열: 이전 두 수의 합으로 현재 수를 구하는 문제

다익스트라