Category 자료구조&알고리즘

트리(Tree) 개념 트리는 비선형 자료구조로, 계층적 관계를 표현하는데 최적화된 구조이다. 마치 나무가 뿌리에서 시작해 가지를 뻗어나가는 모습과 유사하여 ‘트리’라는 이름이 붙었다. 실생활에서는 회사의 조직도, 운영체제의 파일 시스템 등에서 트리 구조를 쉽게 찾아볼 수 있다 트리의 기본 용어 트리의 레벨과 높이…

알고리즘의 성능을 평가할 때 우리는 Big-O 표기법을 사용한다. 어떤 문제를 해결하는 방법, 즉 알고리즘은 여러 가지가 있을 수 있으며, 이 알고리즘의 성능을 비교하고 평가할 때 Big-O 표기법이 쓰인다. 반면 P-NP 문제는 조금 다른 관점에서 문제를 바라본다. 어떤 문제가 주어졌을 때…

메모이제이션(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)가 흥미로운 퍼즐 하나를 세상에 공개했다. 세 개의 기둥과 크기가 서로 다른 원반들로 이루어진 이 게임은, 가장 큰 원반이 맨 아래 있고 위로 갈수록 작은 원반이 쌓여있는 구조이다. 게임의 규칙 하나의 기둥에 있는…

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