'🍀 Knowledge/알고리즘' 카테고리의 글 목록

[알고리즘] 동적 계획 알고리즘(DP) 유형 별 문제 모음

2023.12.06

분할 정복 알고리즘은 반으로 나누는 것이 핵심이었다. 정확히는 분할할 수 없을 때까지 분할하여 간단한 문제부터 접근하였다. 굉장히 자주 사용하며, 좋은 알고리즘이다. 하지만, 분할하며 생기는 부분 문제들이 중복되어도 다시 사용하지 않는다. 이미 구한 문제를 또 푸는 것은 지루하고 시간이 드는 일이다. 유형마다 다르겠지만, 분할정복도 마찬가지일 것이다. 따라서 중복된 문제를 굳이 다시 풀지 않는 테크닉이 필요하다. 그리고 그 방법이 바로 "DP 알고리즘", Dynamic Programming 인 것이다. DP 알고리즘은 미리 최소 부분 문제들의 해를 구한다. 이는 논리적으로 생각했을 때 매우 당연하다고 여겨지는 것들이다. 또한 이 해를 이용하여 최소 부분 문제보다 더 큰 부분 문제를 풀어야 한다. 즉, 부..

🍀 Knowledge/알고리즘

[알고리즘] 분할 정복 - Selection, Closest Pair 문제 해결

2023.12.04

* 공부를 하며 정리한 글입니다. 수정할 점이 있다면 댓글 남겨주세요. 선택(Selection) 문제 주어진 수들 중 k 번째로 작은 수를 찾아야 하는 문제는 꽤나 자주 등장한다. 실제로 이러한 문제를 해결하는 알고리즘도 간단한 것이 많다. 예를 들어 최소 숫자를 k번 찾는 방법, 숫자를 정렬하고 k번째 숫자를 찾는 방법 등이 있다. 하지만, 앞서 말한 알고리즘의 시간 복잡도를 고려해보자. 각각 최악의 경우 O(kn)과 O(nlogn)이 소요된다. 그렇다면 이보다 더 효율적인 시간으로 k 번째 작은 수를 찾을 수 있을까? 여기에 있어 우리는 "Selection" 알고리즘을 사용할 수 있다. 미리 말하자면 선택(Selection) 알고리즘은 이진 탐색 알고리즘과 매우 유사하다. 이진 탐색은 원하는 수를 찾..

🍀 Knowledge/알고리즘

[알고리즘] 작업 스케줄링 알고리즘(JobScheduling) & 허프만 압축(Huffman)

2023.12.03

* 공부를 하며 정리한 글입니다. 수정할 점이 있다면 댓글 남겨주세요. 작업 스케줄링이란? 알고리즘 문제를 풀다보면 시작 시간과 종료 시간이 지정된 어떠한 작업들을 수행하는 문제에 마주칠 때가 있다. 이때 문제를 해결하기 위해서 정렬이나 맵 같은 자료구조를 쓰면 될 것 같은데.. 막상 구현해보면 쉽지 않을 것이다. 따라서 이러한 문제 유형에 대해서는 어느정도 틀을 가지고 푸는 것이 좋다. 지금까지 내가 본 바로는 결국 그 틀 내에서 크게 벗어나지 않기 때문이다. 그래서 작업 스케줄링이 무엇인가 하면, 모든 작업을 수행하는 문제이다. 물론 그냥 수행하는 것이 아니라 해당 작업들의 수행 시간이 뒤죽박죽 섞이지 않고 최소한으로 기계를 사용해야 한다. 기계가 아니어도 강의실 배치, 컴퓨터 등 작업을 수행할 수 ..

🍀 Knowledge/알고리즘

[알고리즘] 최단 경로 알고리즘 - Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘

2023.10.15

Dijkstra 알고리즘 최단 경로(Shortest Path) 찾기는 주어진 가중치 그래프에서 출발점에서 도착점까지의 최단 경로를 찾는 알고리즘이다. 이 최단 경로를 찾는 알고리즘 중 많이 사용하는 것이 바로 Dijkstra 알고리즘이다. Dijkstra 알고리즘은 출발점에서 각 정점까지의 최단 거리 및 경로를 구하는 알고리즘으로 이전에 배웠던 Prim의 MST 알고리즘과 유사하다. 어떤 점이 차이가 있냐하면, Prim 알고리즘은 임의의 점에서부터 시작을 하지만, Dijkstra 알고리즘은 출발 지점이 있다. 또한 Prim 알고리즘에서는 배열 D에 간선의 가중치를 저장했지만, Dijkstra 알고리즘은 배열 D에 출발점에서 각 정점까지의 거리를 저장한다. Prim 알고리즘에 관해 궁금하다면, 아래 포스팅..

🍀 Knowledge/알고리즘

[알고리즘] 최소 신장 트리(MST) - Kruskal, Prim, Sollin 알고리즘

2023.10.14

최소 신장 트리(Minimum Spanning Tree, MST)이란? 최소 신장 트리를 배우기 앞서, 신장 트리란 무엇인지 알아야 한다. 이는 연결 그래프의 부분 그래프로, 모든 정점과 간선의 부분집합으로 구성된다. 신장 트리의 중요한 특징 중 하나는 모든 노드가 적어도 하나의 간선과 정점에 연결되어야 하며, 사이클을 만들면 안된다. 최소 신장 트리를 이해하기 위해서는 이러한 신정트리의 개념을 정확히 파악하고 있어야 한다. 아래와 같은 그래프가 신장 트리의 예시 중 하나이다. 최소 신장 트리는 하나의 연결 성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치의 합이 최소인 신장트리를 말한다. 이러한 최소 신장 트리 알고리즘은 대표적으로 Kruskal, Prim, Sollin 알고리즘이 있다. 이는 ..

🍀 Knowledge/알고리즘

[알고리즘] 강 연결 성분(SCC) - Kosaraju, Tarjan 알고리즘

2023.10.14

강 연결 성분(Strongly Connected Component)이란? 강 연결 성분이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해서 u에서 v로 가는 경로가 있는 동시에, v에서 u로 돌아오는 경로가 있는 연결 성분이다. 강 연결 성분은 그 정의의 특징 상 단절 정점이나, 다리 간선을 포함하지 않는데, 생각해보면 당연하다. 강 연결 성분 내의 특정 정점을 제거함으로써, 두 개 이상의 연결 성분으로 나뉘지도 않고 그러한 간선도 존재하지 않는다. 아래 그림을 살펴보면, 그 의미를 더욱 쉽게 파악할 수 있을 것이다. 색이 같은 정점들을 한번 살펴보면, 임의의 두 정점에 대해서 오고 가는 길이 있다는 것을 확인할 수 있다. 반대로, 색이 다른 정점끼리 오고 가려면, 어느 한 방향은 막히..

🍀 Knowledge/알고리즘

[알고리즘] Biconnect Component : 이중 연결 성분

2023.10.12

이중 연결 성분(Biconnect Component)란? 이중 연결 성분이란, 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 뜻한다. 이때, 연결 성분이란 그래프에서 서로 연결되어 있는 정점들을 말한다. 예를 들어, [1, 2, 3, 4, 5], [6, 7], [8, 9, 10]는 3개의 연결 성분으로 구성되었다고 볼 수 있다. 또한 단순 경로란, 경로 상의 정점이 모두 다른 경로를 말한다. 즉, 이중 연결 성분이란, 무방향 그래프의 연결되어 있는 정점 리스트인데, 이 리스트의 임의의 두 점 간의 경로 상에 있어서 정점이 중복되지 않는 경로가 두 개이상 존재하다는 것을 의미한다. 아래 예시와 함께 그 의미를 한 번 더 살펴보자. 위 그래프는 지금까지..

🍀 Knowledge/알고리즘

[알고리즘] 위상 정렬을 이해해보자.

2023.10.12

* 이 글은 알고리즘에 관해 학습하며 정리한 글입니다. 틀린 점이나, 고쳐야 할 부분이 있으면 알려주세요..! 위상 정렬이란? 위상 정렬이란(Topological Sort) : 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서 정점을 선형순서로 나열하는 것이다. 이때 DAG, 즉 사이클이 없는 방향 그래프란 주로 노드들 간에 우선순위를 나타내기 위해서 사용한다. 만약 노드들간에 사이클이 존재한다면, DAG라고 볼 수 없다. 즉, 우선 순위가 존재하는 노드들 간에 순서를 나타낸 것인데, 만약 우선순위가 동일하다면 그 중 임의의 하나를 선택한다. 그래서 위상 정렬은 여러 값이 나올 수 있다. 일반적으로 위상 정렬을 사용하는 때는 의존 관계가 존재할 때, 수행 가능한 작업 순서..

🍀 Knowledge/알고리즘

[알고리즘] 유니온과 파인드 알고리즘(union, find)

2023.09.07

Union과 find는 집합과 관련된 연산이다. - Union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산 - find : 두 노드가 같은 집합에 속해 있는 지를 확인하는 연산 코드 상에서의 구현 방법도 어렵지 않다. 일반적으로 유니온과 파인드를 구현하기 위해 1차원 배열을 사용한다. 초기에는 아무 노드도 연결되어 있지 않기 때문에 각 노드가 대표노드가 되며 자신의 인덱스 값으로 초기화 된다. union은 두 노드의 대표노드를 일치시키는 연산이다. 이 과정에서 재귀적으로 대표노드를 찾는 과정이 포함될 수 있다. find는 자신이 속한 집합의 대표노드를 찾는 연산이다. 이 과정이 중요한 이유는 단순히 노드를 찾을 뿐만 아니라, 그래프를 정돈하고 시간 복잡도를 향상시키기 때..

🍀 Knowledge/알고리즘

[알고리즘] 다양한 유형의 그래프 문제들

2023.09.04

그래프를 구현하는 방법에는 다양한 접근 방식이 있다. 1. 에지 리스트 : 에지를 중심으로 그래프를 표현 : 열의 갯수를 2개를 두냐, 3개를 두냐에 따라서 가중치가 유무를 표현할 수 있다. : 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다. 2. 인접 행렬 : 행과 열에 그래프 정보를 저장한다.(가령, 1행 2열에 표시하는 것은 1에서 2를 향하는 에지를 나타냄) : 가중치가 없는 경우 1을 저장하지만, 가중치가 있다면 그 값을 저장한다. 3. 인접 리스트 : ArrayList로 그래프를 표현한다. : 가중치가 없다면, ArrayList[5]와 같은 식으로 표현한다. : 가중치가 있다면 각 ArrayList의 값에 노드를 두어 가중치 값을 저장할 수 있다. : 노..

티스토리툴바