본문 바로가기

전체 글

 (97)
[알고리즘] BFS(넓이 우선 탐색) - 코딩밥상 넓이 우선 탐색(Breadth First Search)이란? '꼼꼼히 좌우를 살피며 다니자'는 원칙으로 그래프를 순회하는 알고리즘입니다. 넓이 우선 탐색에서는 시작 정점을 지난 후 깊이가 1인 모든 정점을 방문하고 그 다음에는 깊이가 2인 모든 정점을 방문합니다. 이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점을 방문하다가 더 이상 방문할 정점이 없을 때 탐색을 종료합니다. 대표적인 이용 방법은 그래프의 최단경로에 사용됩니다. 알고리즘의 동작 방식을 구체적으로 정리하자면, 시작 정점을 '방문했음'으로 표시하고 큐에 삽입합니다. 큐로부터 정점을 제거합니다. 제거한 정점의 인접 정점 중에서 아직 방문하지 않은 곳을 '방문했음'으로 표시하고 큐에 삽입합니다. 최종적으로 큐가 비면 탐색이 끝..
[알고리즘] DFS(깊이 우선 탐색) - 코딩 밥상 깊이 우선 탐색(Depth First Search)이란? '더 나아갈 길이 보이지 않을 때까지 깊이 들어간다'는 원칙으로 그래프 내의 정점을 방문하는 알고리즘입니다. 이 알고리즘은 길이 나오지 않을 때까지 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식으로 동작합니다. 대표적인 이용 방법은 그래프 정렬이나 미로 찾기 문제에서 사용됩니다. 알고리즘의 동작 방식을 구체적으로 설명하자면, 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시합니다. 이 정점과 이웃 정점(인접 정점) 중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼고 다시 깊이 우선 탐색을 사직합니다..
[자료구조] 그래프(Graph) - 코딩밥상 그래프(Graph) 란? 그래프는 '정점의 모음'과 정점을 잇는 '간선의 모음'이 결합한 것입니다. 즉 "정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G = (V,E)이다." 라고 정의할 수 있습니다. 정점 자체는 아무의미가 없지만 이들이 간선을 통해 서로 연결되면 '관계'가 형성되고 그로 인해 그래프가 만들어집니다. 용어 정리 간선으로 연결된 두 정점을 서로 '인접(Adjacent)' 또는 '이웃 관계'에 있다고 말합니다. 정점 끼리 간선으로 연결 되어 있을 때 이 정점들은 '경로(Path)'를 이루고 경로의 '길이'는 정점과 정점 사이에 있는 간선의 수로 정의됩니다. 어느 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 그 경로를 일컬어 '사이클(Cycle)'이라고 합니다. ..
[자료구조] 해시 테이블 충돌 해결 기법 - 코딩밥상 해시 충돌 해결 기법 해시 테이블의 충돌을 해결하는 방법에는 크게 두 가지가 있습니다. 하나는 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 것이고, 또 다른 하나는 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결하는 것입니다. 전자는 개방 해싱(Open Hashing)이라고 하고, 후자는 폐쇄 해싱(Closed Hashing)이라고 합니다. 체이닝(Chaining) 이란? 체이닝이란 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법입니다. 체이닝이라는 이름은 충돌이 일어날 때마다 데이터를 링크드 리스트에 사슬처럼 엮는다는 의미에서 붙여진 것입니다. 체이닝 기반 해시 테이블은 데이터 대신 링크드 리스트에 대한 포인터를 관리하고 데이터는 ..
[자료구조] 해시 테이블(Hash Table)과 해시 함수(Hash Function) - 코딩밥상 해시 테이블(Hash Table)이란? 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘입니다. 데이터를 매개 변수로 하여 해시 함수를 거치면 해당하는 주소가 할당되고 그 주소가 인덱스로 사용되는 것입니다. 즉 데이터가 해시 함수를 거치면 테이블 내의 주소(인덱스)로 변환합니다. 다시 한번 정리하자면 데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소에 데이터를 담는 것이 해시 테이블의 기본 개념인 것입니다. 특이하게도 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있습니다. 해시 테이블의 성능은 공간을 팔아 얻어낸다고 생각하면 되겠네요. 해시가 어떻게 데이터로부터 테이블 내의 주소값을 뽑아내는지 다음 ..
[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue) - 코딩밥상 힙(Heap)이란? 힙은 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리입니다. 완전 이진 트리를 복습하자면, 최고 깊이를 제외한 모든 깊이의 노드가 완전히 채워져있는 트리입니다. '힙 순서 속성'이란 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙입니다. (본 정리 글에서는 정수 데이터 값을 priority기준으로 하겠습니다.) 힙은 이진 탐색이 불가능하기에 모든 노드를 순회하며 탐색해야 합니다. 하지만 "힙에서 가장 작은 데이터를 갖는 노드는 뿌리 노드이다" 라는 규칙을 가집니다. 따라서 힙에 사용되는 연산은 두 가지뿐입니다 노드 삽입 연산 힙의 최고 깊이 가장 우측에 새 노드를 추가(완전 이진 트리 유지) 삽입한 노드를 부모 노드와 비교 - 부모 노드보다 크면 종료..
[자료구조] 레드 블랙 트리(Red Black Tree) - 코딩밥상 레드 블렉 트리란? 앞서 공부한 것처럼 순수한 이진 탐색 트리는 가지들이 불균형하게 자라는 경우가 많고 이는 이진 탐색 트리의 높이를 높여서 검색 효율을 심각하게 저하시키기 때문에 문제가 됩니다. 데이터가 아무리 많이 입력되어도 이진 탐색 트리가 균형 있게 성장해서 그 높이가 최소한으로 유지되도록 하는 특별한 이진 탐색 트리가 바로 레드 블렉 트리입니다. 그 방법으로 노드를 빨간색과 검은색으로 구분하여 이러한 이름이 붙여진 것입니다. 이 특별한 트리의 구조체 먼저 알아보자면, typedef struct tagRBTNode{ struct tagRBTNode* Parent; struct tagRBTNode* Left; struct tagRBTNode* Right; enum {RED, BlACK} Color;..
[자료구조] 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리란? '이진 탐색'을 위한 트리이자 탐색을 위한 '이진 트리'입니다. 다시 말해 이진 탐색 트리는 '이진 탐색'을 위한 '이진 트리'입니다. 앞 서 배운 이진 탐색으로는 배열에만 사용 가능한 알고리즘입니다. 데이터의 처음과 끝을 알아야 하고 순식간에 데이터의 중앙 요소를 계산할 수 있어야 하며 중앙 요소에 접근 할 수 있어야 합니다. 하지만 링크드 리스트는 위와 같은 작업들이 불가능한 자료구조입니다. 헤드와 테일 사이의 '중앙 요소'는 알 수 없기 때문입니다. 이러한 문제를 해결하여 링크드 리스트처럼 동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘도 사용할 수 있도록 하는 자료구조가 바로 '이진 탐색 트리' 입니다. 이진 탐색 트리의 표현은 생각보다 간단합니다. 이진 트리..

티스토리툴바