Algorithm22

• 

  [알고리즘] 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘이란? Greedy를 해석해보면 "탐욕스러운"이다. 이 때문에 그리디 알고리즘을 다른 말로 탐욕 알고리즘이라고도 한다. 이 알고리즘은 선택을 할 때마다 최적의 상황만을 선택해 최종적으로 최적의 결과에 도달하게 된다. 여러 선택이 있을 때, 모든 경우의 수에서 최적의 선택을 했다고 하자. 이때 최적의 선택만을 골랐다 해서 최적의 결과만 나오는 것은 아니다. 최적의 선택이 모여 조금 덜 한 결과가 나오는 경우의 수가 있을 수도 있다. 그리디 알고리즘은 위와 같은 경우가 있어서는 안되며, 항상 최적의 선택만을 하여 최적의 결과가 나와야 하는 알고리즘이다. 정당성 증명 탐욕적 선택 속성(Greedy Choice Property): 현재의 선택이 이후의 선택에 영향을 주지 않으면서, .. Algorithm 2023. 11. 14.

• 

  [알고리즘] 이진탐색 알고리즘(Binary Search) 이진 탐색(Binary Search)의 개념 이진 탐색은 정렬되어 있는 리스트 혹은 배열에서 탐색 범위를 절반씩 줄여나가며 특정 값을 찾는 알고리즘이다. 특정 범위의 숫자에서 상대가 생각한 값을 맞추는 업다운 게임을 예시로 들 수 있다. 만약 1~100이라는 범위에서 70이라는 값을 상대가 생각하고 있다고 할 때, 처음엔 50을 말하고, up이라는 반응이 나오면 50과 100의 반인 75를 말한다. 다음으로는 down이라는 반응이 나오고, 50과 75의 중간값인 62를 말한다. 이 과정을 반복해나가다보면 70이라는 값에 도달할 수 있게 된다. 위에서 예시로 들었던 업다운 게임은 결국 이진 탐색의 원리를 이용했다는 것을 알 수 있다. 이진 탐색의 동작 과정은 다음과 같다. 이진 탐색의 동작 과정 리스트의 .. Algorithm 2023. 11. 6.

• 

  [알고리즘] 삽입 정렬(Insertion Sort) 삽입 정렬 정의 삽입 정렬은 정렬 알고리즘 중 가장 간단한 정렬 방식이다. 앞에서부터 차례대로 비교해가며, 자신의 위치를 찾아 삽입함으로써 정렬이 완성된다. 삽입 정렬은 두 번째 데이터부터 시작하여 그 앞에 있는 데이터와 비교하여 삽입할 위치를 지정한 후 데이터를 뒤로 옮기며, 이후 지정한 위치에 데이터를 삽입한다. 구현 fun main() { val list = mutableListOf(5, 8, 6, 2, 4) insertionSort(list) } private fun insertionSort(list: MutableList) { for(i in 1 until list.size) { val key = list[i] var j = i-1 while(j >= 0 && key < list[j]) { li.. Algorithm 2023. 10. 23.

• 

  [알고리즘] 버블 정렬(Bubble Sort) 버블 정렬 정의 버블 정렬은 주어진 배열에서 인접한 두 개의 위치에 있는 데이터의 값을 비교하여 위치를 서로 교환하는 정렬 방식이다. 구현 package datastructure fun main() { val list = mutableListOf(5, 8, 6, 2, 4) bubbleSort(list) } private fun bubbleSort(list: MutableList) { for(i in 0 until list.size - 1) { for(j in 0 until list.size - 1) { if(list[j] > list[j+1]) { swap(list, j, j+1) } } println("${i+1}회전: $list") } } private fun swap(list: MutableList.. Algorithm 2023. 10. 22.

• 

  [알고리즘] 선택 정렬(Selection Sort) 선택 정렬 정의 선택 정렬은 n개의 데이터 중에서 최소값을 찾아 첫 번째 데이터 위치에 놓고, 나머지 (n-1)개 중 다시 최소값을 찾아 두 번째 데이터 위치에 놓는 방식을 반복하여 정렬하는 방식이다. 즉, 한 번의 회전에 모든 데이터를 확인해봐야 한다. 구현 package datastructure fun main() { val list = mutableListOf(5, 8, 6, 2, 4) selectionSort(list) } private fun selectionSort(list: MutableList) { for(i in 0 until list.size) { for(j in i+1 until list.size) { if(list[i] > list[j]) { swap(list, i, j) } } p.. Algorithm 2023. 10. 22.

• 

  [알고리즘] 위상 정렬(Topological Sort) 위상 정렬(Topological Sort) 순서가 정해져 있는 작업을 어떠한 차례로 수행해야 하는지 결정해주는 알고리즘이다. 즉, 방향 그래프에 존재하는 정점들의 선행 순서를 위반하지 않고 모든 정점을 나열하는 것이다. 위상 정렬은 한 방향 그래프에서 여러 위상 정렬이 가능하다. 즉, 답이 여러가지일 수 있다는 것이다. 위 방향그래프에서 위상 정렬을 한 결과를 생각해보면 다음과 같다. 1 → 6 → 2 → 5 → 4 → 3 6 → 2 → 1 → 5 → 4 → 3 6 → 1 → 2 → 5 → 4 → 3 과정 진입 차수가 0인 정점을 큐에 저장한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 이후 진입 차수가 0인 정점을 큐에 저장한다. 큐가 빌 때까지 반복한다. 이때, 모든 원소를 방문하.. Algorithm 2022. 9. 10.

• 

  [알고리즘] 이분 그래프(Bipartite Graph) 이분 그래프란? 정점을 두 그룹으로 나눌 수 있으면서, 같은 그룹끼리는 간선으로 이어지지 않은 그래프이다. 트리가 아닌 그래프이므로, 사이클이 있어도 상관없으나, 같은 색상의 정점끼리 연결은 있어서는 안된다. 간선이 단 한도 없고 정점만 있는 상태도 이분 그래프이다. 여기에서 알 수 있듯이, 모든 정점이 꼭 연결되있어야 하는 것이 아니다. 이분 그래프 구현 이분 그래프는 DFS 또는 BFS를 사용하여 구현할 수 있다. 나는 BFS가 더 익숙하여 BFS를 사용할 것이다. 백준의 1707번 이분 그래프 문제를 예시로 들어보자. import java.util.* import kotlin.collections.ArrayList private lateinit var color: IntArray private la.. Algorithm 2022. 8. 16.

• 

  [알고리즘] 플로이드 와샬(Floyd Warshall) 플로이드 와샬(Floyd Warshall) 알고리즘이란? 이전에 공부했던 다익스트라 알고리즘은 특정 정점에서 시작하여 다른 특정 정점 또는 모든 정점으로의 최단 경로를 구하는 알고리즘이었다. 플로이드 와샬 알고리즘 또한 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 다만 다익스트라 알고리즘과의 차이점은 "모든 정점에서 모든 정점으로의 최단 거리"를 구하는 알고리즘이라는 것이다. 또한 다익스트라 알고리즘에서는 가장 적은 비용을 하나씩 선택하며 알고리즘을 수행했지만, 플루이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 또한 다이나믹 프로그래밍 알고리즘에 의거한다. 동작 단계 위의 그래프를 예시로 들어보겠다. 이 때, 각 정점이 다른 정점으로 가는 비용을 배열의 형태로 보면 .. Algorithm 2022. 8. 8.

• 

  [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm)은 다이나믹 프로그래밍을 활용하는 대표적인 최단 경로를 찾는 알고리즘이다. 다만 다익스트라 알고리즘은 음의 간선을 포함할 수 없다. 즉, 음의 간선이 하나라도 포함되어 있다면, 다익스트라 알고리즘을 사용할 수 없다. 원래 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다. 하지만, 일반적으로 한 꼭짓점을 루트(root) 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만든다. 동작 단계 출발 노드를 설정한다. 최단 거리를 저장할 테이블을 초기화해준다.(보통 무한대(아주 큰 값)로 초기화한다.) 현재 위치하고 있는 노드의 인접 노드 중 비용이 가장 적은 노드를 선택한다. 해당 .. Algorithm 2022. 8. 3.

• 

  [알고리즘] 동적 프로그래밍(Dynamic Programming): 메모이제이션(Memoization), 테뷸레이션(Tabulation) 동적 프로그래밍(Dynamic Programming) 전에 분할 정복에 대해 다뤘던 적이 있 분할 정복은 큰 문제를 여러 개의 소문제로 나눠 해결해나가는 알고리즘이다. 이 작은 문제들을 매번 재계산하지 않고, 기억해두었다가 재사용하는 알고리즘이 동적 알고리즘이다. 동적 프로그래밍의 핵심은 소문제를 정의하는 것이다. 소문제를 정의하고, 이 소문제를 이용하여 다음 크기의 무제를 해결하는 방법을 제시할 수 있어야 한다. 또한 부분 문제들의 답이 중복되지 않게 최적의 방법으로 구해야 한다. 최적 부분 구조(Optimal Substructure) 어떤 문제가 최적 부분 구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해 기존 문제의 최적의 답을 구할 수 있다. 동적 프로그래밍의 기본 기법으로는 메모이제이션.. Algorithm 2022. 7. 26.

• 

  [알고리즘] 프림 알고리즘(Prim Algorithm) 프림 알고리즘 무방향 연결 그래프가 주어졌을 때, 최소 신장 트리를 찾기 위한 알고리즘이다. 크루스칼 알고리즘과의 목적은 같지만, 언제 어떻게 사용하느냐에 따라 효율성이 달라질 수 있다. 크루스칼 알고리즘에 관해서는 크루스칼 알고리즘을 참고하면 된다. 크루스칼 알고리즘과 마찬가지로 프림 알고리즘도 그리디 알고리즘(Greedy Algorithm)의 일종이다. 크루스칼 알고리즘은 간선의 가중치를 오름차순으로 정렬해서 가장 작은 가중치를 가진 간선부터 선택해나갔다. 프림 알고리즘은 임의의 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장시키는 기법이다. 프림 알고리즘의 동작 위에서도 말했듯이, 프림 알고리즘은 그리디 알고리즘의 일종이다.' 즉, 탐색 정점과 연결된 인접 정접들 중 가중치가 가장 적은 간선.. Algorithm 2022. 7. 24.

• 

  [알고리즘] 크루스칼 알고리즘(Kruscal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 그리디 알고리즘(Greedy Algorithm)의 일종이다. 크루스칼 알고리즘은 가중치가 가장 작은 간선으로부터 시작한다. 위에서 보았던 연결 그래프를 예시로 크루스칼 알고리즘의 과정을 보자. 우선 간선을 가중치 오름차순 순으로 정렬시킨다. 1-2 간선부터 선택을 한다. 다음으로 2-4 간선을 선택한다. 다음으로는 1-4 간선이다. 하지만 1-4 간선을 연결하게 되면 사이클이 이루어진다. 따라서 이 간선은 건너뛴다. 다음으로는 1-3 간선을 선택한다. 3-4를 선택하면 사이클이 되므로 종료한다. 사이클 판단하기: Union-Find 위의 과정을 보면, 사이클이 발생해 패스했던 부분이 있다. 이를 구현할 때 사용하는 거이 Union-F.. Algorithm 2022. 7. 21.