Algorithm

벨만-포드 (Bellman-Ford) 알고리즘이란? 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색하는 알고리즘이다. 단순히 최단 경로를 탐색하지 않고 아래와 같은 특징이 있다. 음수 가중치 에지가 있어도 수행할 수 있다. 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다. 벨만-포드 동작 원리 예시 그래프 아래와 같은 그래프에서 출발 노드를 1로 가정한다. 1. 에지 리스트로 그래프를 구현하고 최단 경로 배열을 초기화 한다. 최단 경로 배열의 출발 노드는 0, 나머지 노드는 ∞로 초기화한다. 2. 모든 에지를 확인해 정답 배열을 업데이트 한다. 노드 개수가 N이고 음수 사이클이 없을 때, 특정 두 노드의 최단거리를 구성할 수 있는 에지의 최대 개수는 N-1이다. 따라서, 최단 거리 ..

다익스트라 알고리즘이란 그래프에서 최단 거리를 구하는 알고리즘이다. 특정 노드에서 다른 노드들의 최단 거리를 구할 수 있다. 다익스트라의 동작 원리 아래와 같은 그래프에서 출발 노드를 1로 가정한다. 1. 최단 거리 배열 초기화 최단 거리 배열을 만들고 출발 노드는 0, 이외의 노드는 무한으로 초기화 한다. 2. 값이 가장 작은 노드 선택 최단 거리 배열에서 현재 값이 가장 작은 노드를 선택한다. 현재 1번 노드의 값이 0으로 가장 작기 때문에, 1번 노드를 선택한다. 3. 최단 거리 배열 업데이트 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 연결 노드의 최단 거리는 아래와 같은 방법으로 업데이트한다. Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 ..

위상 정렬 알고리즘이란 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 사이클이 존재하면 위상 정렬을 적용할 수 없다. 진입 차수 (in-degree): 자기 자신을 가리키는 에지의 개수 위 특징들은 위상 정렬의 원리 부분에서 설명할 것이다. 그리고, 진입 차수는 위상 정렬에서 중요한 개념이다. 위상 정렬의 원리 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 해당 과정을 모든 노드가 정렬될 때까지 반복한다. 정렬하는 과정에서 진입 차수가 0인 노드를 선택하게 되는데, 어떤 노드를 먼저 선택하냐에 따라 정렬의 결과가 항시 같을 수 없다. 해당 과정을 그림으로..

유니온 파인드란 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. union 연산: 각 노드가 속한 집합을 1개로 합치는 연산 find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 유니온 파인드의 원리 1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. ex) union(1,4), union(5,6) ex) union(4,6) find 연산 find 연산..

깊이 우선 탐색 (DFS: depth-first search) 특징 시간 복잡도 (V: 노드의 개수, E: 에지의 개수) 재귀 함수로 구현 Stack 자료구조를 이용 O(V + E) 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 깊이 우선 탐색의 동작 이론 1. DFS를 시작할 노드를 정한 후 자료구조 초기화 하기 DFS를 시작하기 앞서 인접 리스트로 그래프를 표현하고, 방문 배열을 초기화해줘야 한다. 이후 시작 노드를 스택에 삽입하고, 방문 배열에 체크를 한다. 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 po..

백준의 문제 중 "멀티탭 스케줄링"이라는 문제가 있다. 해당 문제에서 미리 멀티탭의 사이즈, 각 전자기기를 사용하는 순서를 입력으로 주어진다. 단순히 구현하려고 하면 고려할 점이 많아 보이지만 OPT 알고리즘을 적용하면 간단하게 풀린다. OPT 알고리즘은 페이지 교체 기법중 하나이며, 최적 페이지 교체 알고리즘으로 불리기도 한다. OPT 알고리즘은 미래를 예측하여 가장 사용되지 않을 페이지를 교체한다. 미래를 예측한다는 것이 불가능하기 때문에 실제로 구현을 할 수는 없다. 하지만, 미래의 값들이 주어지는 그리디 문제의 경우 OPT 알고리즘를 활용하면 어렵지 않게 접근할 수 있다. https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한..

오일러 피 함수 P[N] 1 ~ N까지 범위에서 N과 서로소인 자연수의 개수 오일러 피 함수의 원리 구하고자 하는 오일러 피의 범위만큼 배열을 초기화한다. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = P[i] - P[i] / K연산을 수행한다. (i는 K의 배수) 배열 끝 까지 반복하여, 오일러 피 함수를 완성한다. 해당 과정을 거치면 배열의 위치에 서로수의 개수가 저장되게 된다.

이번 포스팅에서 알아볼 정렬 알고리즘은 총 5가지이다. 버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 퀵 정렬 (Quick Sort) 병합 정렬 (Merge Sort) 버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방법 간단하게 구현할 수 있지만, 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느리다 선택 정렬 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 구현 방식이 복잡하며, 시간 복잡도도 O(n^2)으로 효율적이지 않다 삽입 정렬 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법 구현하기 쉽지만, 시간 복잡도O(n^2)로 느린 편 퀵..

프로그래머스의 문제 중 "캐시"라는 문제가 있다. 해당 문제에서 페이지 교체 알고리즘은 LRU를 사용한다고 하며, Cache Hit와 Miss를 구분하여 실행시간을 조건으로 주었다. 문제를 풀기 위해서 LRU를 알아볼 수밖에 없었고, 아래와 같이 개념을 정리해 보았다. LRU 란 LRU (Least Recentely Used)는 페이지 교체 알고리즘 중 하나이고, 이름을 보면 유추할 수 있다시피 그대로 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다. LRU의 동작원리 빠른 이해를 돕기 위해 [1, 2, 3, 1, 4, 5]의 예시를 아래 그림으로 그려봤다. 동작 과정을 보면 Queue처럼 Cache에 참조 값이 쌓이고, 만일 Cache에 참조 값이 존재하는 경우 가장 최근으로 옮긴다. 그리고..

프로그래머스의 "소수 찾기"라는 문제가 있다. 해당 문제는 입력된 n(정수)까지 소수가 몇 개 존재하는지를 출력하는 알고리즘이다. 처음에는 이중 for문을 사용하여 각 숫자마다 1과 자기자신을 포함하여 나눠떨어지는 숫자의 개수를 세서 소수를 판별했다. 하지만 알고리즘 효율성이 좋지 않아서 런타임 에러가 발생했고, "에라토스테네스의 체"라는 알고리즘을 알게 되었다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 자기 자신을 제외한 2의 배수를 모두 지운다. 다음 수인 3은 소수이기 때문에 3의 배수를 모두 지운다. 다음 수인 5는 소수이기 때문에 5의 배수를 모두 지운다. 계속해서 다음 숫자는 소수이며, 해당 숫자의 배수를 지워나간다. 코드 구현 - JAVA class Solution ..