로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!== 자료구조 == 데이터를 저장하는 방식을 말한다. 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 반드시 필수적이다. === 선형 자료구조 === 한 종류의 데이터가 선처럼 길게 나열된 자료구조이다. ==== 랜덤 접근 가능 ==== 모든 자료에 O(1)으로 접근이 보장되는 자료구조들이다. ===== 배열 ===== 가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. [[C (프로그래밍 언어)|C언어]]에서는 대괄호를 사용한다. <syntaxhighlight lang="C"> int array1[]; //int *array1과 비슷함. int array2[10]; //크기를 가지는 배열 int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열 </syntaxhighlight> C에서 배열에 포인터를 사용하여 접근하는 것을 보면, 배열의 각 원소의 주소가 연속적으로 배치되어 있다는 것을 알 수 있다. [[파이썬]]에서는 그냥 리스트 자료구조를 사용한다. <syntaxhighlight lang="Python"> array1 = [] # 빈 리스트. array2 = [0, 1, 2, 3, 4] # 길이가 5인 리스트. C언어나 파이썬은 숫자를 0부터 센다. array3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 리스트 안에 리스트가 중첩되어 있다. # 리스트 안에는 리스트를 포함하여 어떤 객체도 넣을 수 있다. </syntaxhighlight> [[자바]]에서는 대괄호의 위치가 변수명보다 앞에 있다. <syntaxhighlight lang="Java"> int[] array1; int[] array2 = new int[10]; //heap 메모리에 할당하여 사용 int[] array3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //C언어와 동일한 초기화 </syntaxhighlight> ===== 해시 ===== 해시는 해시 함수로 구현한다. 해시 함수는 마치 배열처럼, 어떤 자료를 찾을 때 <math>O(1)</math>의 시간만을 소요한다. 해시함수에 키 값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다. 하지만, 언제나 <math>O(1)</math>이 보장되는 것은 아니다. 자세한 것은 [[해시 테이블]] 참고. [[파이썬]]의 해시는 “딕셔너리”(Dictionary)라고 부른다. <syntaxhighlight lang="Python"> dict1 = {1:"하나", "apple":"사과", "리스트":[1, 2, 3]} </syntaxhighlight> ==== 랜덤 접근 불가능 ==== 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다. ===== 스택 ===== [[파일:Data stack.svg|섬네일|스택 자료구조]] 먼저 들어간 자료가 나중에 나오는 자료구조. 유식한 말로 후입선출(後入先出) 구조라고 한다. 자료를 넣는 push 함수와 자료를 빼는 pop 함수를 갖는 게 정석이다. empty, full 등 다른 함수들을 가질 수 있다. [[C++]]의 [[STL]] (Standard Template Library의 약자이다. 간단하게 설명하자면 여러 자료 구조, 함수, 알고리즘 등을 쓰기 쉽게 정형화해서 라이브러리화 해둔 것)에서 지원한다. 아래는 가장 기본적인 스택의 구현이다. <syntaxhighlight lang="C"> #define STACK_SIZE 500 int arr[STACK_SIZE]; //스택의 최대 크기는 500 int top = 0; //스택의 현재 크기는 0 int push(int n) { if (top>=STACK_SIZE) return -1; arr[top++] = n; return 0; } int pop() { if (top<=0) return -1; return arr[--top]; } </syntaxhighlight> 스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다. <syntaxhighlight lang="c"> push(1), push(2), push(3); printf("%d %d %d", pop(), pop(), pop()); </syntaxhighlight> 출력 결과는 3 2 1과 같을 것이다. [[파이썬]]의 리스트 자료구조로 스택 클래스를 만들면 다음과 같을 것이다. <syntaxhighlight lang="Python"> class stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def peek(self): return self.items[-1] def size(self): return len(self.items) def pop(self): return self.items.pop() </syntaxhighlight> 이렇게 작성한 스택 클래스로 문자열을 뒤집는 함수를 만들면 다음과 같다. <syntaxhighlight lang="Python"> def reverseString(str): s = stack() result = "" for i in str: s.push(i) while s.isEmpty() != True: result += s.pop() return result </syntaxhighlight> 함수의 실행 결과는 다음과 같다. <syntaxhighlight lang="Python"> >>> print(reverseString("apple")) elppa >>> </syntaxhighlight> [[자바]]의 배열 자료구조로 스택 클래스를 만들면 다음과 같을 것이다. C언어와 동일한 기능을 수행하도록 구현하였다. <syntaxhighlight lang="Java"> public class Stack{ int size = 500; int[] arr = new int[size]; int top = 0; int push(int n){ if(top > size){ return -1; } arr[top++]=n; return 0; } int pop(){ if(top <= 0){ return -1; } return arr[--top]; } public static void main(String[] args){ Stack stack = new Stack(); stack.push(1); stack.push(2); stack.push(3); System.out.printf("%d %d %d", stack.pop(), stack.pop(), stack.pop()); } } </syntaxhighlight> ===== 큐 ===== [[파일:Data Queue.svg|섬네일|큐 자료구조]] 먼저 들어간 자료가 먼저 나오는 자료구조. 선입선출(先入先出) 구조라고도 한다. 자료를 넣는 Enqueue 함수와 자료를 빼내는 Dequeue 함수를 가진다. 밑의 큐는 [[연결 리스트]]로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다. <syntaxhighlight lang="C"> void enqueue(int); int dequeue(); struct linkedList { int value; struct linkedList *next; }; struct linkedList *front; //큐의 맨 앞을 가리킨다. struct linkedList *back; //큐의 맨 뒤를 가리킨다. void enqueue(int n) //큐에 자료를 넣는 함수 { if(front == NULL) //큐가 비어 있을 경우 { *front = {n, NULL}; //맨 앞에 자료를 넣고 back = front; //맨 뒤와 맨 앞을 같게 한다. } else { back -> *next = {n, NULL}; //맨 뒤 다음에 자료를 넣는다. back = back -> next; //넣은 자료를 맨 뒤로 한다. } } int dequeue() //큐에서 자료를 빼는 함수 { int res = front -> value; front = front -> next; return res; } </syntaxhighlight> C++의 [[STL]]에서도 Queue의 구현체를 제공하고 있다. [[파이썬]]에서 리스트 자료구조로 큐를 구현하는 클래스를 작성 하자면 다음과 같을 것이다. <syntaxhighlight lang="Python"> class queue: def __init__(self): self.items = [] def enqueue(self, item): self.items.insert(0, item) def dequeue(self): return self.items.pop() def isEmpty(self): return self.items == [] def size(self): return len(self.items) </syntaxhighlight> [[자바]]에서 [[연결 리스트]] 자료구조로 큐를 구현하는 클래스를 작성 하자면 다음과 같을 것이다. <syntaxhighlight lang="Java"> import java.util.Queue; public class Queue { Queue<Integer> queue = new LinkedList<>(); void enQueue(int n){ queue.add(n); } int deQueue(){ return queue.poll(); } } </syntaxhighlight> ===== 데크 ===== 간단하게 말하자면 스택과 큐의 [[융합]]형태. 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 보통 입력이나 출력 중 하나를 한 쪽 입구만 가능하게 제한하는 형태가 많이 쓰인다. ===== 링크드 리스트 ===== 연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다. 옵션으로 이전 노드를 가지게 할 수도 있으며, 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다. 또한, 중간에서 삽입과 삭제를 할 수 있다. 가장 간단하게 구현한 것은 위의 [[큐]]. 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다. 다만, 링크드 리스트는 원소들이 이곳저곳에 흩어져있어서 구현체의 속도가 느리기 때문에, 잘 사용되지는 않는 편이다. ==== 선형구조 자료 탐색법 ==== 말 그대로 선형구조로 된 자료를 탐색하는 방법이다. 보통 어떤 값이 어디에 있는지 알아내는 게 목적이다. ===== 순차 탐색 ===== 말 그대로 시작점부터 순차적으로 탐색하는 것이다. 전부 탐색한다고 생각할 때,연산량은 O(n)이다.<br /> 솔직히 이건 해당 언어만 알면 누구나 코드를 만들어낼 수 있을 수준이기에,소스 코드 부분은 생략한다. ===== 이분 탐색 ===== 특수한 상황에서 순차 탐색보다 좀 더 빠른 속도를 기대할 수 있는 알고리즘으로,연산량은 O(log<sub>2</sub> N)이다. 이분 탐색이란,순차 탐색과 달리 가운데에서 시작해서 매번 일정한 조건에 따라 어떤 방향의 가운데 값으로 탐색할 지 결정하는 알고리즘이다.이 때 가운데 값이란 평균이 아니고 중간값이다. 이를 좀 더 자세히 설명하자면 이렇다. 배열 1 3 4 7 8 13 17에서 '8'이 있는 위치를 찾는다고 가정하자. 배열: 1 3 4 7 8 13 17<br /> 1st:총 배열의 가운데인 7을 선택.<br /> 7<8 이므로 더 큰 숫자가 있는 오른쪽으로 진행. <br /> 2nd:7~17의 배열중 가운데인 13을 선택.<br /> 13>8 이므로 더 작은 숫자가 있는 왼쪽으로 진행.<br /> 3rd:7과 13의 가운데에 있는 8을 선택.<br /> 8=8 이고 배열은 5번째이므로 답은 5이다. 단,이를 위해서는 특수한 기준으로 '''정렬'''되어 있어야 한다. 정렬법에 대해서는 아래쪽 확인. 아래의 소스에서는 모든 입력코드가 오름차순으로 정렬되어 있다고 가정한다. <syntaxhighlight lang="c"> //헤더 부분 int solve(int,int); //소스 부분 int A[500]; //총 500개까지 담을 수 있는 배열에서 탐색. int k; //탐색할 값. int solve(int s, int e); { int m; while(e-s>=0) { m=(s+e)/2; //값이 있을 가능성이 있는 값의 가운데 값. if(A[m]==k) return m+1; //그 값이 만약 탐색할 값이면 그 위치를 리턴. if(A[m]<k) s=m+1; //만약 A[m]이 작으면 좀 더 큰 값들이 있는 오른쪽이 탐색되도록 변경. else e=m-1; //아까와 정반대. } return -1; //찾는 값이 없을 경우 -1을 준다. } </syntaxhighlight> 이것을 변형하면,배열의 어디부터가 어떤 숫자 이상인지 혹은 초과인지 알 수 있다.<br /> 전자가 Lower bound,후자가 Upper bound이다. 이들은 아예 <algorithm>에 포함된 함수가 있으니 한번 봐두자. <syntaxhighlight lang="cpp"> //헤더 #include<algorithm> //.h는 붙이지 않는다. //소스,A가 배열이고 배열의 데이터 개수는 n개,찾는 데이터는 k. std::lower_bound(A,A+n,k,[compare]) std::upper_bound(A,A+n,k,[compare]) //[compare]은 비교 기준이며,이게 생략된 경우 오름차순이라고 간주한다. </syntaxhighlight> === 비선형 자료구조 === 선형 자료구조가 아닌 모든 자료구조이다. 다만,사전적인 정의를 하자면 '''i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조'''를 의미한다. ==== 그래프 ==== [[파일:6n-graf.svg|섬네일|이런 거.]] 함수의 그래프와는 전혀 다르다. 알고리즘을 배우다 보면 자주 나오는 구조로, 점들, 그리고 점들을 연결하는 선들만으로 이루어진 [[지도]] 비스무리한 걸 연상하면 편하다. 이때의 점을 '''정점(vertex)''', 선을 '''간선(edge)'''이라고 부른다.<ref>사실 우리가 수학에서 잘만 써먹던 대로 ‘꼭짓점’과 ‘변’이라고 하면 된다. 그거랑 정확히 똑같은 개념이다. 그런데 이상하게 이 동네에서는 ‘정점’과 ‘간선’이라는 새로운 용어를 쓴다. 이래 놓고 “수학에서 말하는 그래프랑 다르다”는 식으로 생각하는 바보도 있으니 기가 막힐 노릇이다. 그래프 이론은 엄연히 수학의 일부이다.</ref> 간단한 구조체를 하나 살펴보자. <syntaxhighlight lang="C"> struct Edge //정점보다는 간선으로 나타내는 편이 대부분의 경우에 더 좋다. { int snode; //시작 정점 int enode; //종료 정점 //int cost; //가중치를 가지는 간선에 사용된다. }; </syntaxhighlight> 위의 struct Edge가 하나 이상 있는 것이 바로 그래프이다. 그래프를 다르게 구현하는 경우도 있는데,바로 인접 행렬로 구현하는 방법과 인접 리스트로 구현하는 방법이다. 다음은 데이터를 받아서 저장하는 가중치 그래프라고 가정하자. 이 경우는 인접 행렬로 구성하는 방법이다. <syntaxhighlight lang="C"> #include<stdio.h> int m,g[101][101]; //정점은 최대 100개 int main() { scanf("%d",&m); //간선의 개수 for(int i=0;i<m;i++) { int a,b,w //a와 b는 간선이 연결된 곳,w는 가중치 scanf("%d %d %d",&a,&b,&w); g[a][b]=g[b][a]=w; } } </syntaxhighlight> 인접 리스트로 구성이 가능하긴 하지만 너무 복잡해서 구현하기 까다롭다. 그래서 그래프도 함수로 정의되어 있다. <syntaxhighlight lang="cpp"> #include<vector> std::vector<int> G[101]; //소스 부분 G[i].push_back (x); //i와 x는 연결된 그래프이다. </syntaxhighlight> 이 때,탐색시간은 인접 리스트 방식의 구현이 더 짧다.(단,v가 정점이고 e가 간선이라고 가정한다.)<br /> 인접 행렬:O(v*e)<br /> 인접 리스트:O(v+e) ===== 그래프 관련 용어 ===== [[파일:Element of Graph.png|500픽셀||]] * 정점(Vertex) *: 간단하게 말해서, 연결점이다. 좀 더 구체적으로 정의하자면, ''여러 가지 특성을 가질 수 있는 객체''이다. 즉, 어떤 객체도 정점이 될 수 있다. ** 고립 정점 **: 간선이 단 하나도 연결되지 않은 외톨이 정점이다. * 간선(Edge) *: 두 정점을 연결하는 연결선이다. 구체적으로는, ''두 정점간의 관계''이다. ** 단방향 간선 **: [[일방통행|''단방향으로만 이동 가능한'']] 간선이다. 이동이 가능한 방향으로 화살표를 그린다. ** 양방향 간선 **: 양 방향으로 모두 이동이 가능한 간선이다. 양쪽 화살표를 사용해도 되지만, 양방향 그래프에서는 모든 간선이 양방향 간선이므로 화살표 대신 선분으로 표현하기도 한다. ** 자기 간선 **: 자기 자신을 연결하는 간선이다. ** 다중 간선 **: 동일한 다른 접점과 여러 간선이 연결되는 간선이다. * 인접 *: 두 정점이 하나의 간선으로 연결되어 있을 때 두 정점이 인접하다고 한다. * 차수(Degree) *: 정점에 연결된 간선의 수이다. ** 진입 차수 **: 정점으로 들어오는 간선의 수이다. ** 진출 차수 **: 정점에서 나가는 간선의 수이다. * 경로(Path) *: 어떤 한 정점에서 다른 하나의 정점으로 가는 길이다. 두 정점이 반드시 다를 필요는 없다. ** 길이(Length) *: 어떤 경로에서 시작 정점에서 도착 정점까지 거쳐야 하는 정점의 수. ** 단순 경로 **: 경로에서 시작, 끝 정점을 제외한 방문하는 모든 점이 서로 다른 경로. *** 사이클(Cycle) ***: 시작 정점과 끝 정점이 같은 단순 경로 **** 재귀 사이클 ****: 간선 하나만으로 이루어진 사이클 * 부분 그래프(Sub Graph) *: 그래프를 구성하는 정점들을 임의로 선택한 후 그 정점을 연결했던 간선들로 선택한 정점을 연결한 그래프를 말한다. ===== 그래프의 종류 ===== * 그래프 *: 일반적인 정의는 ''객체들 사이의 관계를 점과 선으로 나타낸 그림''이다. 그래프는 크게 두 구성요소 ''정점''과 ''간선''으로 이루어져 있다. ** 단순 그래프 **: 임의의 두 정점 사이에 간선이 최대 하나 있는 그래프 ** 다중 그래프 **: 임의의 두 정점 사이에 여러 개의 간선을 허용하는 그래프 ** 의사 그래프 **: 다중 그래프이면서 사이클을 허용하는 그래프 ** 양방향(무향) 그래프 **: 연결된 두 정점의 순서를 바꾸어도 같은 간선이 되는 그래프, 즉 ''양방향으로 통행이 가능한'' 그래프. ** 단방향(유향) 그래프 **: ''[[일방통행]]만 가능한'' 그래프. ** 연결 그래프 **: 임의의 두 정점 사이에 반드시 경로가 존재하는 그래프. *** 완전 그래프 ***: 모든 정점이 서로 간선으로 양방향 연결되어 있는 그래프 ** 가중치 그래프 **: 간선에 가중치가 부여된 그래프 ===== 그래프 순회 알고리즘 ===== 그래프를 순회하는 방법이다. 각 방법마다 장단점이 있으니 상황에 따라 적절한 알고리즘을 선택하는 것이 중요하다. ====== 깊이 우선 탐색 ====== [[파일:DFS Example.gif|400픽셀||오른쪽]] Depth First Search, DFS라고 불리며, 구현하기 쉬운 알고리즘 중 하나이다. 이름 그대로, 방문한 정점으로부터 깊게 들어가며 쭉 탐색한 후, 되돌아 나오다가 아직 탐색하지 않은 노드를 탐색하는 방식을 사용한다. 알고리즘의 실행과정을 설명하면 다음과 같다. # 첫 정점을 방문한다. # 인접한 정점 중 아직 방문하지 않은 정점을 방문한다(한 길로 쭉 파고 들어간다). # 더 이상 들어갈 길이 없을 때(인접한 모든 정점이 이미 방문한 정점일 때), 방문하지 않은 인접한 정점을 찾을 때까지 들어간 길을 돌아나온다. # 위 과정을 반복한다. 여기서 DFS를 구현하는 함수의 모양은 다음과 같다. 단,그래프는 인접리스트를 활용했다고 가정한다. {{탭| |제목1 = C++ |내용1 = <syntaxhighlight lang="cpp"> bool visited[101]; //방문 여부를 체크하는 배열 void dfs(int k) { for(int i=0; i<G[i].size();i++) //정점 k와 연결된 모든 정점을 방문한다. if(!visited[G[k][i].to]) { visited[G[k][i].to]=true; dfs(G[k][i]); } return; } </syntaxhighlight> |제목2 = Python3 |내용2 = <syntaxhighlight lang="python3"> visited = dict(zip([v for v G], [False for _ in G])) def dfs(v): for i in G[v]: if not visited[i]: visited[i] = True dfs(i) </syntaxhighlight> }} 예제(그림)의 경우 방문 순서는 1, 2, 3, 4, 5, 7, 6, 8, 9 이다. 여기서 DFS는 깊이가 너무 큰 경우, 런타임 에러를 뿜는다는 단점이 있다. ====== 너비 우선 탐색 ====== [[파일:BFS Example.gif|400픽셀||오른쪽]] Breadth First Search, BFS라고 불린다. 이름 그대로, 넓게 퍼져가며 정점을 방문한다. 알고리즘의 실행과정은 다음과 같다. # 첫 정점을 방문한다. # 아직 방문하지 않은 인접한 정점들을 큐에 넣는다. # 큐에 있는 정점들을 순서대로 방문한다. # 큐에 있는 정점에 대해 인접하면서 아직 방문하지 않은 정점들로 새로운 큐를 구성한다. # 위 과정을 반복한다. 예제(그림)의 경우 방문 순서는 1, 2, 5, 6, 3, 4, 7, 8, 9 이다. {{탭| |제목1 = Python 3 |내용1 = <syntaxhighlight lang="python3> visited = dict(zip([v for v in G], [False for _ in G])) # 방문 여부를 체크하는 배열 def bfs(v): # 정점 v부터 탐색 시작 visited[v] = True queue = [v] while queue: now = queue.pop(0) for i in G[now]: # 현재 선택한 정점의 모든 자식 정점을 방문. if not visited[i]: visited[i] = True queue.append(i) </syntaxhighlight> }} ==== 트리 ==== [[파일:Tree Sample.svg|200픽셀||오른쪽]] 그래프의 일종이다. 트리에서의 정점을 특별히 ''노드''라고 하고, 간선을 특별히 ''가지''라고 한다. 코드를 작성해보자. <syntaxhighlight lang=c> struct Node; struct List { struct List *next; struct Node *element; }; struct Node { struct Node *Parent; struct List *Sons; }; </syntaxhighlight> 자식 노드의 수가 몇 개인지 모르기 때문에, 각 노드의 자식노드 리스트를 단방향 링크드 리스트를 이용해 저장하였다. 위의 struct Node가 하나 이상 있는 것이 트리이다. ===== 트리 관련 용어 ===== * 노드(Node) *:그래프의 정점에 해당하는 것이다. ** 루트 노드 **: 트리의 기준이 되는 노드이다. 나무의 뿌리를 생각하면 된다. 루트 노드 위에 가지가 뻗어 있다는 이미지. ** 부모 노드 **: 어떤 노드에서 자신과 인접한 노드들 중 루트 노드로 향하는 노드. ** 자식 노드 **: 어떤 노드에서 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드. ** 단말 노드 **: 자식 노드가 존재하지 않는 노드. 가지의 끝이라고 생각하면 된다. ** 형제 노드 **: 부모 노드가 같은 노드. * 가지(Branch) *:그래프의 간선에 해당하는 것이다. 트리에서는 양방향 간선만 사용한다. * 부트리(Sub Tree) *: 부분 그래프와 비슷하게 정의한다. * 차수(Degree) *: 자식 노드의 개수. * 길이(Length) *: 임의의 두 노드를 시작 노드, 도착 노드로 하는 경로에서 거치게 되는 노드의 수. ** 깊이(Depth) **: 루트 노드에서 해당 노드까지의 길이. *** 레벨(Level)<s>트리도 레벨업을 하나?</s> ***: 깊이가 같은 노드의 집합. *** 높이(Height) ***: 가장 깊이가 깊은 단말 노드까지의 길이. ===== 트리의 종류 ===== * 이진 트리 *: 모든 노드의 차수가 2 이하인 트리. ** 전 이진 트리 **: 모든 노드의 차수가 0 또는 2인 트리. ** 포화 이진 트리 **: 모든 단말 노드의 깊이가 같은 이진 트리. ** 완전 이진 트리 **: 모든 단말 노드의 깊이의 최댓값과 최솟값의 차이가 0 또는 1인 이진 트리. ===== 트리 순회 알고리즘 ===== 트리를 순회하는 방법이다. ====== 전위 순회 ====== 그래프에서의 깊이 우선 탐색과 같다. 설명은 [[쉽게 배우는 프로그래밍 입문/알고리즘#깊이 우선 탐색|해당 항목]]에서! ====== 중위 순회 ====== [[파일:Middle Order.gif|200픽셀]] 이진 트리에서만 할 수 있는 순회 알고리즘이다. ====== 후위 순회 ====== [[파일:Post Order.gif|200픽셀]] ====== 레벨 순서 순회 ====== 그래프에서의 너비 우선 탐색과 같다. 역시 설명은 [[쉽게 배우는 프로그래밍 입문/알고리즘#너비 우선 탐색|해당 항목]]에서! ===== 이진 검색 트리 ===== 이진 검색은 일자로 나열된 '''정렬된''' 데이터에서 원하는 데이터를 빠르게 찾는 방법이다. 최악의 경우에 <math>O \left( \log{n} \right)</math>를 보장하는 매우 유용한 알고리즘이다. 정렬의 중요성은 거의 이 알고리즘을 통한 활용에 있다고 할 수 있다. 이진 검색 트리는 이진 검색에 용이하게 데이터를 다음과 같은 방법으로 이진트리로 구성한 것을 말한다. # 일렬로 나열된 데이터들 중 가장 중앙에 위치한 하나의 데이터를 M이라고 하고, M 왼쪽에 위치한 데이터들을 L, 오른쪽에 위치한 데이터를 R이라 하자. # L과 R이 M을 부모로 가지는 트리를 구성한다. # L과 R에 대해서도 각각 같은 방법으로 트리를 구성한다. ====== 이진 검색 ====== [[파일:BST Example.gif|600픽셀|섬네일|왼쪽은 검색 성공, 오른쪽은 검색 실패]] [[수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초#이분 탐색|이분 탐색]]과 동일한 알고리즘이다. 여기에서는 트리라는 특징을 중점으로 해서 설명한다. 오름차순 정렬된 자료를 기준으로 한다. 이진 검색 트리의 루트 노드부터 방문하며, 다음 순서에 따라 노드를 방문한다. * 방문한 노드가 찾는 값이라면 검색 성공. * 방문한 노드가 단말노드이고 찾는 값이 아니라면 검색 실패. * 방문한 노드가 단말노드가 아니고 찾는 값이 아니라면 *# 방문한 노드의 값을 <math>x</math>, 찾는 값을 <math>v</math>라고 할 때, <math>x < v</math> *#* 방문한 노드의 오른쪽 자식을 방문한다. *# <math>x > v</math> *#* 방문한 노드의 왼쪽 자식을 방문한다. 여기서도 위에서와 같이 노드가 저장된 값에 특정한 규칙이 있어야 함에 주의해야 한다. (정렬이 가능한지는 추가바람) === 문자열 === 문자 여러 개가 나열되어 있는 것으로, 보통 배열로 표현한다. C에서, 문자열의 끝은 특정 문자(NULL, ASCII 0번 문자)로 정해져 있다. Java에서는 아예 기본 자료형으로 제공된다. 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서는 다음의 숨은 분류 1개에 속해 있습니다: 분류:유튜브 영상이 포함된 문서