각 노드가 최대 두 개의 자식(왼쪽 자식과 오른쪽 자식)을 가질 수 있는 트리 구조 종류 완전 이진 트리(Complete Binary Tree): 모든 레벨이 꽉 차 있는 상태에서, 마지막 레벨을 제외하고 모든 노드가 채워져 있는 이진 트리 마지막 레벨은 왼쪽부터 채워진다. 포화 이진 트리(Perfect Binary Tree): 모든 레벨...

트리의 기본 개념 트리(Tree) 트리는 노드들이 간선(edge)로 연결된 계층적인 데이터 구조이다. 사이클이 없으며, 어떤 두 노드 간에도 유일한 경로가 존재한다. 트리와 그래프의 차이 트리(Tree) 계층적 구조: 트리는 계층적 관계를 표현하는 데 사용됩니다. 예를 들어, 파일 시스템의 디렉토리 구조는 트리로 표현...

최단경로에 대한 개괄적인 설명 간선의 가중치가 양수인 경우 Dijkstra는 정점을 지날수록 가중치가 증가한다는 사실을 전제한다. Dijkstra는 집합(S)에 들어간 노드는 다시 고려하지 않는다. 임의의 단일 시작점에서부터 최단 경로 찾기 Prim 알고리즘과 원...

주어진 가중치 그래프에서 출발점으로부터 도착점까지의 최단경로를 찾는 문제 최단 경로란, 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로로 일반적으로 시작점과 끝점이 존재한다. 유형 one-to-one, single-pair 하나의 정점에서 다른 하나의 정점까지의 최단경로...

배열에 순차적으로 접근해야 할 때, 두 개의 포인터(지점)를 이용하는 알고리즘 배열 [1,2,3,4,5,6,7,8] 에서 2,3,4,5,6,7번 원소를 골라야할 때, 간단하게 ‘2번부터 7번까지의 원소’라고 부를 수 있다. 즉, 투 포인터 알고리즘은 두 개의 포인터가 하나의 ‘범위’를 나타내는 것을 활용한다. 1차원 배열 : 부분 배...

원본 문제 링크 : 양 한 마리… 양 A마리… 양 A제곱마리… 문제 춘배는 오늘도 열심히 활동을 마친 후 자려 하지만 도저히 잠이 안 온다. 춘배는 잠을 자기 위해 자신만의 방법으로 양을 세려는데 한 마리씩 세지 않고 여러 마리를 한꺼번에 세면서 자려 한다. 춘배는 일단 양의 정수 $A$를 정한다. 그 후 양을 셀 때 첫 번째에 센 양의...

원본 문제 링크 : 색종이 만들기 문제 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는...

이분 탐색, 이진 탐색, Binary Search 이분 탐색(이진 탐색)은 결정 문제(Decision Problem)의 답이 이분적(T or F)일 때 사용할 수 있는 탐색 기법이다. 보통 1개의 parameter에 대해 탐색할 때사용한다. 이분 탐색을 사용하면 정렬된 배열에서 특정 값을 효율적으로 찾을 수 있다. 길이가 $N$인 배열에 ...

모듈로(modulo) 연산 한 숫자를 다른 숫자로 나눈 후 나눗셈의 나머지를 반환하는 연산이다. 두 개의 양수 a,n에 대해 모듈로 n(mod n)은 a를 n으로 나눈 나눗셈의 나머지이다. a : 피제수(dividend), 나눠지는 수 n : 제수(divisor), 나누는 수 여담으로, 파이썬의 내장함수 중 pow(a,b) 함수는 기...

전체 문제를 부분 문제로 분할(Divide)한 뒤, 부분 문제를 풀고(Conquer), 이를 전체로 병합(Merge)하는 과정을 거쳐 문제를 해결하는 방식 분할 정복과 동적 계획법의 구분(조건) 공통점 큰 문제를 부분 문제로 나누어 작은 문제를 푼다. 최적 부분 구조를 가져야 사용 가능하다. ...

원본 문제 링크 : 타일링 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를...

원본 문제 링크 : 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은...

일명 탐욕,욕심쟁이 알고리즘 “매 선택에서 현재 당장 최적인 답을 선택하여 적합한 결과를 도출하는” 근시안적 문제 해결 방식이다. 매 순간마다 하는 선택은 지역적(그 순간에서)으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었을 때, 그것이 최적이라는 보장은 없다. 즉 그리디 알고리즘을 통해 최적 값을 구하기 위...

Richard Bellman이 1950년대에 사용한 단어 기본적인 아이디어 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 동적 계획법을 가장 잘 설명하는 단어는 ‘기억하며 풀기’ 특정한 알고리즘이 아닌 하나의 문제해결 방법론으로 바라보는 것이 적절하다 왜 DP를 사용? 일반적인 재귀 방...

목표 배낭의 용량을 넘지 않으면서 가치가 최대가 되는 $S$의 부분집합 $A$ 찾기 Notation n개의 아이템 집합 : $S = {item_1, item_2, \ldots , item_n}$ 아이템의 무게 : $w=[w_1,w_2,\ldots,w_n]$ 아이템의 가치 : $p = [p_1,p_2,\ldots,p_n]$ ...