yoongrammer

목차 최단 경로(Shortest path) 문제 알아보기최단 경로 문제(shortest-paths proble)란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다.여기서 가장 짧은 경로란 간선의 가중치 합이 가장 작은 경로를 말합니다. 경로 p = 의 가중치(w) 합이 다음과 같다면$$ w(p) = \sum_{i=1}^k w(v_{i-1},v_{i}) $$정점 u에서 v까지의 최단경로 값은 다음과 같이 표시합니다.$$ \delta(u,v) = \begin{cases} min\{w(p) : u \overset{p}\rightsquigarrow v \}, & \mbox{if u에서 v로 가는 경로가 있다면} \\ \infty, & \mbox{if u에서 v로 가는 경로가 없다면} \end{cases}$$ ..

목차 위상 정렬(Topological sort) 개념 및 구현비순환 방향 그래프 (DAG: Directed Acyclic Graph)Directed Acyclic Graph (DAG)는 사이클이 없는 방향 그래프입니다. DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용됩니다. 위상 정렬(Topological sort)위상 정렬(Topological sort)은 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것입니다.모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 됩니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다.그래프에 사이클이 있으면서 두 정점 u,v가 사이클 속에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v가 u보다..

목차우선순위 큐 (Priority Queue) 개념 및 구현일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다.하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다. 우선순위 큐는 다음과 같은 속성을 가지고 있습니다.모든 항목에는 우선순위가 있습니다.우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다.두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됩니다.4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같습니다.(여기서 높은 값이 높은 우선순위를 갖는다고 가..

목차시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다.시간 복잡도: 알고리즘의 수행시간을 평가공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다.이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.시간 복잡도(Time Complexity)알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다. 기본 연산은 다음과 같습니다.데이터 입출력 - copy, move...산술 연산 - add,..

목차점근 표기법 (asymptotic notation) 알아보기점근 표기법(asymptotic notation)을 이해하고 대표적인 세 가지 유형의 점근 표기법인 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation)에 대해 알아보도록 하겠습니다.점근 표기법 (asymptotic notation) 컴퓨터 알고리즘의 실행시간은 실행환경에 따라 다르게 측정됩니다. ex) 하드웨어, 운영체제, 언어 등 실행환경을 동일하게 하는 것은 어렵기 때문에 기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다.연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다. ex) \(f(n) = n^2+3n+1..

목차보간 탐색 (Interpolation Search) 개념 및 구현보간 탐색 (Interpolation Search)은 정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘입니다. 보간 검색은 전화부에서 이름 (책의 항목이 정렬되는 키 값)을 검색하는 방법과 유사합니다.  동작 방식은 이진 탐색과 비슷하지만 탐색 위치를 정하는 방식이 다릅니다. 이진 탐색과 보간 탐색의 탐색 위치를 결정하는 공식은 다음과 같습니다.arr [] : 데이터가 들어있는 배열low : arr [] 배열에 시작 indexhigh : arr[] 배열에 마지막 indexx : 검색 값pos : 탐색 위치 index이진 탐색\( pos = (low + high) / 2 \) 보간 탐색\( pos = low + (x - arr [low]..

목차점프 탐색(Jump search) 개념 및 구현Jump search는 순차적으로 탐색하는 선형 탐색과 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다.정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색하게 됩니다. 이 알고리즘은 선형 탐색보다 빠르지만 이진 탐색보다는 느립니다.동작 방식배열을 블록단위로 나누기 위해 블록 사이즈 m을 구합니다.m의 최적 값은 다음과 같습니다. 여기서 n은 요소의 수입니다.m = √n한 블록에서 값을 탐색하고 없으면 다음 블록으로 이동합니다.값을 가진 블록을 찾으면 선형 탐색을 사용하여 정확한 인덱스를 찾습니다.블록 최적 사이즈 구하는 과정m에 최적 값을 구하는 공식은 다음과 같습니다.블록 크기가 m이고 n..

목차이진 탐색 (Binary search) 개념 및 구현이진 탐색은 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 동작 방식이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다.중간 값을 찾아야 하기 때문에  반드시 정렬된 배열에서만 사용할 수 있습니다. 이진 탐색의 동작 방식은 다음과 같습니다. 배열의 중간 값을 가져옵니다.중간 값과 검색 값을 비교합니다.중간 값이 검색 값과 같다면 종료합니다. (mid = key)중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid..

목차 순차 검색(Sequential Search) 개념 및 구현순차 검색(Sequential Search)은 선형 검색(Linear Search)으로도 불리며 리스트에서 순차적으로 탐색하면서 원하는 값을 찾아내는 알고리즘입니다. 순차 검색은 구현이 쉽고 리스트의 정렬 여부와 상관없이 동작하는 장점이 있지만, 리스트의 모든 요소를 확인해야 하기 때문에 검색할 리스트의 길이가 길면 비효율적이라는 단점이 있습니다. 시간 복잡도(Time complexity)OperationBestAverageWorstSearchO(1)Θ(n)O(n)*n = 데이터 수 종료 조건순차 검색의 종료 조건은 두 가지가 있습니다. 다음 조건중 하나라도 성립하면 검색을 종료합니다. 1. 검색을 실패할 경우검색할 값을 발견하지 못하고 리스..