깊이 있는 개발

1. MST(Minimum Spanning Tree) 1.1. Spanning Tree(신장 트리) 개념 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이 때 모든 그래프가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 1.2. MST(Minimum Spanning Tree, 최소 신장 트리) 개념 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간..

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 1. Dijkstra(다익스트라) 1.1 개념 다익스트라는 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작한다. 다익스트라는 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. DP를 활용한 최단 경로 탐색 알고리즘이라고 할 수도 있다. 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를..

1. DP(동적 계획법) 1.1. 개념 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 DP이다. DP는 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 큰 문제를 작게 나누는 방법은 분할 정복 방식이 있다. 하지만 DP와의 차이점은 DP는 문제들이 서로 영향을 미치고 있다는 점이다. 퀵 정렬을 예로 들면, 한 번 pivot이 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 반면에 DP는 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. DP는 아래 조건을 만족할 때 사용할 수 있다. ..

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다. 경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 된다. 1. DFS 1.1 개념 깊이 우선 탐색이며 DFS(Depth-First Search)라고 부른다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 재귀함수를 통해 구현한다.(스택 자료구조를 이용하는 알고리즘이기 때문) 모든 경로를 방문해야 할 경우 사용에 적합하다. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다. 1.2. 시간 복잡도 인접 행렬 : O(V^2) 인접 리스트 : O(V+E) V는 접점, E는 간선을 뜻한다 1.3. C..

정렬 알고리즘에 대해 본격적으로 살피기 전에, 제자리 정렬과 안정 정렬의 개념에 대해 알아보자. 제자리 정렬(in-place sorting) 제자리 정렬은 추가적인 공간이 필요하지 않은 정렬이다. merge sort처럼 요소를 분할하면서 추가적인 공간을 필요로 하지 않은 정렬이다. 현재 배열 안에서 정렬이 다 이뤄지는 것이다. 이러한 정렬에는 버블, 삽입, 선택 정렬 등이 있다. 제자리 정렬 장점은 공간 복잡도와 공간 지역성이다. 공간 지역성이란 특정 데이터와 가까운 주소가 순서대로 접근되는 경우를 말한다. 공간 지역성의 이점은 메모리를 계속 할당 받지 않아도 되는 데 있다. 병합 정렬 같은 경우에는 새로운 메모리를 계속 할당 받는데 이러한 메모리들은 연속적이지 않아 지역성이 좋지 않다. 하지만 선택, ..

1. 알고리즘 1.1. 알고리즘 정의 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것이다. 즉, 알고리즘은 어떤 일을 해결하기 위한 방법과 절차라고 할 수 있다. 1.2. 알고리즘의 조건 입력 외부에서 제공되는 자료가 0개 이상 존재해야 한다. 출력 적어도 2개 이상의 서로 다른 결과를 내야 한다. 명확성 수행과정은 무엇을 하기 위한 것인 지 명확하게 정의되어야 한다. 유한성 알고리즘의 명령어대로 수행했을 때 처리된 후 종료되어야 한다. 효율성 모든 과정은 명백하게 실행가능한 것이어야 하며, 시간적 공간적 효율성을 가져야 한다. 2. 복잡도 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간..