브루트 포스(Brute Force Search) 완전 탐색 알고리즘 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 구조에 따른 브루트포스 종류 선형 구조 : 순차 탐색 비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 순차 탐색 ① 구조화 : 문제에서 주어진 자료를 선형 구조로 구조화한다. ② 탐색 : 구조화된 자료들을 구조에 맞는 방법으로 해를 구할때까지 탐색한다. ③ 정리 : 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리한다. 장점 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 한다. 해가 존재하지 않는다면 유한(finite) 그래프의 경우에는..
그리디 알고리즘(Greedy Algorithm) 최적해를 구하는 데에 사용되는 근사적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것 최적 부분 구조 조건(optimal substructure) : 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것 주요 단계 선택 과정(Selection Pro..
이진 트리(Binary tree) 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 관련 용어 왼쪽 자식 노드(left child node) 오른쪽 자식 노드(right child node) 부모 노드(parent node) 형제 노드(sibling node) : 부모가 같은 두 노드 노드의 차수(degree) : 자식의 수 잎 노드(external/leaf node) : 차수가 0인 노드 내부 노드(internal/branch node) : 차수가 0이 아닌 노드 (즉, 자식이 있는 노드) 방향 간선(directed edge) 경로(path) 경로의 길이(length) : 경로가 포함하는 방향 간선의 수 (시작점과 출발점이..
그래프(Graph) vertex(정점)와 edge(정점과 정점을 연결하는 간선)로 구성된 한정된 자료구조 컴퓨터 시스템에 그래프를 저장하는 방법은 여러가지가 있다. 이론적으로 그래프는 리스트와 행렬구조 중의 하나로 구별 가능하다. 리스트 구조는 종종 희소 그래프(간선이 얼마 없는 그래프, sparse graphs)에 적합하며 적은 메모리 공간을 요구한다. 행렬 구조는 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공한다. 리스트 자료 구조 발생 리스트(Incidence list) 인접 리스트(Adjacency list) 행렬 자료 구조 발생 행렬(Incidence matrix) 인접 행렬(Adjacency matrix) References ko.wikipedia.org/wiki/%EA%B7%B8%E..
트리(Tree) 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조 (간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.) 관련 용어 루트 노드(root node) : 트리에서 최상위 노드 부모 노드(parent node) : 노드 A가 노드 B를 가리킬때 A를 B의 부모 노드 자식 노드(childe node) : 노드 A가 노드 B를 가리킬깨 B를 A의 자식 노드 잎 노드(leaf node) : 자식 노드가 없는 노드 내부 노드(internal node) : 잎 노드가 아닌 노드 References ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0 트리 구조 - 위키백과, 우리 모두의 백과사전..
너비 우선 탐색(Breadth First Search, BFS) 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. 재귀적으로 동작하지 않는다. 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. (즉, 선입선출(FIFO) 원칙으로 탐색) 시간복잡도 인접 리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) 구현 방법 자료 구조 큐(Queue)를 이용 활용 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을..
