메모이제이션(Memoization)과 타뷸레이션(Tabulation) 재귀의 문제점 재귀를 이용한 분할 정복으로 많은 문제를 해결했다. 하지만 재귀는 콜스택을 차지하는 것 외에도 성능에 크게 영향을 미치는 치명적인 단점이 있다. 바로 중복 계산이다. 피보나치 수열로 보는 재귀의 비효율성 피보나치 수열이란 다음과 같은 규칙으로 만들어진다 재귀로 구현하기…

퀵 정렬이란 병합 정렬과 같이 분할 정복 (Divide and Conquer) 알고리즘에 속하며, 재귀를 사용한다. 하지만 병합 정렬과는 다른 방식으로 동작한다 핵심 원리 병합 정렬과의 차이점 동작 과정 상세 분석 배열 [5, 3, 7, 2, 6, 4, 9, 1, 8]을 오름차순으로…

분할 정복 (Divide and Conquer) 해결하기 힘든 문제가 있다면 한 번에 해결하려 하지 말고, 해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결하라 이것이 바로 분할 정복(Divide and Conquer) 전략이다. 병합 정렬은 이 전략을 완벽하게 구현한 알고리즘으로 지금까지 알아본 O(n²) 정렬들과는…

삽입 정렬은 배열을 정렬된 영역과 정렬되지 않은 영역으로 나누고, 정렬되지 않은 영역에서 원소를 하나씩 꺼내어 정렬된 영역의 적절한 위치에 삽입하는 알고리즘이다. 마치 카드 게임에서 손에 든 카드를 정렬하는 방식과 유사하다. 구현이 직관적이지만 성능은 O(n²)으로 비효율적이다. 핵심 원리 동작 과정 상세…

선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 정렬된 영역의 맨 뒤로 보내는 알고리즘이다. 매 단계마다 최솟값을 선택(Selection)한다고 해서 선택 정렬이라는 이름이 붙었다. 구현이 직관적이지만 성능은 O(n²)으로 비효율적이다 핵심 원리 선택 정렬은 다음 과정을 반복한다 동작 과정 상세 분석…

버블 정렬은 가장 직관적이고 이해하기 쉬운 정렬 알고리즘 중 하나이다. 인접한 두 원소를 비교하여 순서가 잘못되어 있으면 위치를 교환하는 방식으로 동작한다. 구현이 간단하지만 성능은 O(n²)으로 효율적이지 않다. 동작 원리 배열 [4, 2, 3, 1]을 오름차순으로 정렬하는 과정을 살펴보자 1단계: 첫…

하노이탑의 탄생 1883년, 프랑스 수학자 에두아르 뤼카(Édouard Lucas)가 흥미로운 퍼즐 하나를 세상에 공개했다. 세 개의 기둥과 크기가 서로 다른 원반들로 이루어진 이 게임은, 가장 큰 원반이 맨 아래 있고 위로 갈수록 작은 원반이 쌓여있는 구조이다. 게임의 규칙 하나의 기둥에 있는…

재귀를 배우고 나면 그 개념 자체는 이해할 수 있지만, 실제로 문제를 재귀적으로 풀어내는 것은 쉽지 않은 일이다. 이는 우리가 일상생활에서 재귀적으로 사고할 일이 거의 없기 때문이다. 하지만 재귀에도 몇 가지 주요 패턴이 존재하며, 이를 이해하고 연습한다면 어떤 문제가 재귀에 적합한지…

프로그래밍의 핵심 개념 중 하나인 재귀 함수(Recursive Function)에 파고들어보자. 재귀는 단순히 어려운 개념이 아니라, 특정 유형의 문제를 우아하고 효율적으로 해결해준다. 재귀의 기본 개념: 자기 참조 재귀는 어떤 것을 정의할 때 자기 자신을 참조하는 것을 의미한다. 프로그래밍에서는 함수를 정의할 때 자기…