Algorithm/Theory && Tip
위상정렬
위상정렬
2022.06.24Topological Sort 그래프 자료구조에 대해 정렬을 수행할 때 위상정렬을 사용한다. 위상정렬은 DAG 그래프에 대해서만 수행 할 수 있다. (사이클이 없고 방향성이 있는 그래프) 위상정렬을 통해 DAG에서 간선의 방향성에 따라 정점을 위상에 맞춰 정렬해보자. N에서 K로 가는 간선이 있다면 N은 K보다 먼저 나타나야 한다. 위의 조건을 충족하면서 정점들을 나열하는 것을 위상정렬이라고 한다. 위의 조건 때문에, 사이클이 있는 그래프에 대해서는 위상정렬을 수행할 수 없다. 이제 위상정렬의 과정에 대해 알아보자. 제일 먼저 올 수 있는 정점은 들어오는 간선이 없는 정점이다. 위의 그래프에서 정점 1 9 7은 들어오는 간선이 없기 때문에 정렬을 수행한 결과 중 앞에 위치한다. (1 9 7 간의 순서는 ..
재귀
재귀
2022.05.16절차지향적인 사고를 버려야 재귀 파트를 이해할 수 있다. 재귀함수는 base condition(종료조건)이 있어야 하고, 모든 입력은 base condition으로 수렴해야 한다. 재귀함수를 사용하면 반복문을 사용하는 것 보다 효율적이지 않은 경우가 많고, 적절히 dp를 사용하지 않으면 계산했던 결과를 또 계산하는 경우가 많이 생길 수 있어 조심스럽게 사용해야 한다. 그럼에도 재귀를 이용하면 굉장히 편하게 작성할 수 있는 경우나, 재귀를 사용해야만 작성할 수 있는 코드들이 있으니 재귀를 포기할 수는 없다. a에서 a/2를 호출하고 a가 1에서 return을 만나는 함수가 있다고 해 보자. a가 1000이면 1000 -> 500 -> 250 -> 125 -> 62 -> 31 -> 15 ..... 이런 방식..
그래프
그래프
2022.05.12자료구조에서 그래프는 정점 + 간선 방향의 유무 / 가중치의 유무에 따라 그래프의 종류가 나뉜다. 차수 (deg) : 정점에 연결된 간선의 수 / 모든 정점들의 차수 합 = 간선 수 * 2 (시간복잡도 계산에 사용됨) 그래프 문제를 풀기 위해 컴퓨터에게 그래프 자료구조를 저장하는 방법을 알아야 한다. 1. 인접 행렬 그래프가 연결된 상태를 이차원 배열으로 표현한다. 가중치가 있는 경우는 1이 아니고 가중치로 표현 할 수 있다. 구현하기는 쉽지만, 메모리를 효과적으로 사용하기 힘들다. 2. 인접 리스트 List자료구조를 활용해 연결된 요소들만 저장한다. 주어진 조건에 따라 효과적인 방법으로 그래프를 구현하자. 그래프 문제에서 가장 중요한 요소는 이 문제가 그래프 문제인걸 아는 것이다. 문제를 보고 그래프 ..
매개 변수 탐색
매개 변수 탐색
2022.05.04이분 탐색을 응용한 알고리즘이다. 어떤 배열이 0과 1로만 구성되어있고, 이 배열이 정렬된 상태라고 생각해 보자. 0과 1의 경계를 찾으려면 어떻게 해야 할까? 인덱스 0부터 시작해서 순차적으로 탐색해 경계를 찾는 방법도 있지만, 딱 봐도 효율적이지 않다. 지난번에 배웠던 이분 탐색을 이 문제에 적용해보자. L = 배열의 시작, R = 배열의 끝 으로 설정하고 이분 탐색을 수행하면 순차 탐색보다 훨씬 효율적으로 탐색할 수 있다. 이를 매개 변수 탐색이라고 하는데, 특정 문제에서 유용하게 사용될 수 있다. 1. 정답을 매개 변수로 만들고, 주어진 문제를 예 / 아니오 로 결정할 수 있는 문제로 바꿔 보자. 2. 배열이 정렬된 상태인가? 두 가지 조건이 성립한다면 매개 변수 탐색으로 해결할 수 있는 문제이다..
정렬 기본 - Java
정렬 기본 - Java
2022.05.03자바에서 정렬을 수행할 때는 Integer, char과 같은 Primitive 원소에 대해서는 Dual-Pivot Quick Sort를 사용하고, 객체를 정렬할 때는 Tim Sort를 사용한다. (내부 함수 사용 시) 왜 객체와 객체가 아닌 것에 대해 따로 정렬을 수행할까? 한 가지 방법으로 통일하면 일관성을 유지할 수 있어 이해하기 쉽지 않을까? 이 질문에 대해 답하기 위해서는 In-place와 Stable여부를 알아야 한다. 정렬 알고리즘이 In-place하다면, 정렬 과정에서 정렬을 수행하는 N에 비해 무시할 만한 개수의 메모리만 사용함을 의미한다. 정렬할 요소의 수가 10만개이고, 10만개의 요소를 정렬할 때 추가로 사용해야하는 메모리가 10이라면 무시할 만 하다고 할 수 있다. 다음으로, 정렬 ..
최소 신장 트리 - Kruskal (Union Find)
최소 신장 트리 - Kruskal (Union Find)
2022.04.14신장 트리는 그래프에서 모든 노드가 연결되어 있고, 사이클이 없는 그래프를 의미한다. 최소 신장 트리는 신장 트리에서 가중치를 부여하고, 만들 수 있는 신장 트리 중 가중치의 합이 최소인 그래프를 의미한다. 그래프가 주어졌을 때 최소 신장 트리를 찾을 수 있는 알고리즘으로는 크루스칼과 프림 알고리즘이 있다. 먼저 크루스칼 알고리즘에 대해 알아보자. Kruskal 그리디 알고리즘을 기반으로 해 최소 신장 트리를 구한다. 1. 그래프의 모든 노드들을 연결되지 않은 상태로 놓는다. 2. 존재하는 모든 간선들을 비용을 기준으로 정렬하고, 비용이 적은 간선부터 연결을 시작한다. (같은 비용이면 아무거나 선택해도 괜찮음) 3. 연결된 후 노드들의 최상위 노드를 확인 후 최상위 정점이 같으면 연결하지 않고 (사이클이..
최단 경로 - 다익스트라
최단 경로 - 다익스트라
2022.04.13가중치 그래프에서 가중치의 합이 최소가 되도록 하는 특정 경로를 찾는 알고리즘이다. 다익스트라 (Dijkstra) 그래프의 특정 노드에서 출발해 시작 노드를 제외한 나머지 모든 노드들에 대해 최단 경로를 찾는 알고리즘이다. 그림과 같은 그래프에서 A에서 출발해 B까지 가는 최단 경로를 구한다고 생각해보자. (가중치를 거리라고 생각하자) A에서 B로 바로 가면 거리는 8이지만, C를 거쳐 B를 가면 6의 거리로 갈 수 있으니 여기서 최단 경로는 6이다. A에서 출발해 B로 가는 최단 경로를 구해보자. 1. 시작 노드와 연결된 노드들에 대해 가중치를 저장할 배열을 만들고, 가중치를 저장한다. A : [8(B), 1(C), 2(D)] 2. 저장된 가중치 중에서 최솟값이 가리키는 노드를 기준으로 설정하고 해당 ..
Backtracking
Backtracking
2022.04.11분할정복이나 dp처럼 문제를 풀기 위한 전반적인 전략 같은 알고리즘이다. 문제의 해가 될 수 있는 후보군들 중에서 특정 조건에 부합하는 해의 집합을 찾을 때 사용한다. 처음에 해가 될 수 있는 후보를 하나 선택하고, 처음 선택과 연관해서 다음 해가 될 수 있는 후보를 하나 선택하는 방식으로 진행하고, 만약 연관된 해를 구할 수 없다면 처음으로 돌아가서(backtrack) 다시 후보를 선택한다. 트리 자료구조와 연관해서 이해하면 편하다. 각 후보를 DFS방식으로 확인하며, 조건에 맞지 않으면 해의 후보가 될 수 있는 위치로 돌아가 다시 탐색한다. 조건에 맞지 않아서 연관된 요소를 모두 포기하는 기법을 Pruning이라고 하고, 해당 요소가 조건에 부합하는지 확인하는 기법을 Promising이라고 한다. 백..
Greedy
Greedy
2022.04.06탐욕 알고리즘이라고도 불린다. 재귀, 분할정복과 dp처럼 특정 문제를 해결하기 위한 알고리즘이라기보다는, 문제 해결에서 사용할 수 있는 도구 중 하나라고 생각하면 좋을 것 같다. 여러 가지 경우 중 하나를 결정해야 할 때, 선택의 순간마다 최적이라고 판단되는 케이스를 선택하는 방향으로 진행해 최종 값을 산출하는 알고리즘이다. 그리디 알고리즘을 사용해서 풀 수 있는 대표적인 문제로, 부분 배낭 문제가 있다. 무게 제한이 있는 상황에서, 최대 가치를 담을 수 있도록 배낭에 물건을 넣어야 한다. 물건들에 대한 무게와 가치 정보가 주어진다. 여기서, 물건을 쪼개서 넣을 수 있다면 분할 가능 배낭 문제 (Fractional knapsack problem)이고, 쪼갤 수 없으면 knapsack problem이라고 ..
DFS
DFS
2022.04.06Depth First Search. 깊이 우선 탐색이다. BFS와 마찬가지로 그래프 자료구조를 탐색할 때 사용하는 알고리즘이다. BFS와는 달리 DFS는 정점의 자식을 먼저 탐색한다. BFS에서는 두 개의 큐 자료구조를 사용해서 구현했지만, DFS에서는 BFS에서 탐색해야 하는 부분을 저장하는 큐 (needvisit)를 스택으로 바꿔서 활용한다. BFS의 로직과 DFS의 로직을 비교해서 공부해보자. import java.util.*; import java.io.*; public class Main { public ArrayList dfsFunc(HashMap graph, String startNode) { ArrayList visited = new ArrayList(); Stack needVisit = ..
BFS
BFS
2022.04.06이진 탐색과 순차 탐색처럼 특정 자료구조 내부를 탐색하는 알고리즘이 있듯, BFS는 그래프 자료구조를 탐색하는 알고리즘이다. 풀 네임은 Breadth-First Search으로, 너비 우선 탐색을 의미한다. BFS는 위와 같이 탐색을 진행한다. 그래프에서 레벨에 해당하는 부분을 탐색하고, 하나의 레벨에 대해 탐색을 마치면 다음 레벨에 대해 탐색을 시작하며 마지막 모든 원소를 확인할 때 까지 탐색을 진행한다. BFS를 구현하기 위해 먼저 Java에서 그래프를 구현하는 방법에 대해 알아보자. 자바에서는 HashMap과 ArrayList자료구조를 이용해 그래프를 구현한다. HashMap의 Key부분에는 그래프의 노드에 해당하는 정보가 들어가고, Values부분에는 해당 노드에 인접한 노드에 대한 정보가 들어간..
이분탐색
이분탐색
2022.04.04배열이나 리스트에서 특정 원소를 찾을 때 탐색 알고리즘을 사용한다. 순차탐색은 말 그대로 맨 처음부터 탐색을 시작해 원하는 원소를 찾을 때 까지 탐색을 수행한다. ( O(n) ) 좀 더 효율적으로 탐색하기 위해 이분 탐색 알고리즘이 고안됐다. 일단, 탐색하려는 배열이나 리스트는 정렬된 상태여야 한다. 1. 전체 데이터의 중간을 비교한다. 2. 찾으려는 원소와 중간 원소를 비교해 중간 원소보다 찾으려는 원소의 값이 더 작다면 중간값을 기준으로 좌측을, 그렇지 않으면 우측으로 탐색 구간을 재정의한다. 3. 1 2 를 반복한다. 만약 찾으려는 원소가 배열 안에 없어도 쉽게 파악할 수 있다. 미루어 짐작할 수 있듯, 이분 탐색도 분할정복 기법과 재귀를 사용하는 알고리즘이다. import java.util.*; ..