천천히 가는 것을 걱정하지 말고 서있는 것을 걱정하라.

Lower Bound 찾고자 하는 target 이상의 값이 인덱스 0부터 시작했을 때 등장하는 최초의 위치 과정 코드 public static int lowerBound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; // 찾으려고 하는 target 값이 현재 nums[mid] 값보다 작거나 같다면 // nums[mid]는 후보가 될 수 있는 값이다. if (target

네트워크 유량 (Network Flow) ? 도입 네트워크를 이용해 수백 GB에 달하는 아주 큰 파일을 다운로드하는 중이라고 하자. 이렇게 전송받을 자료의 양이 많을 때 우리가 관심을 갖는 부분은 서버가 보낸 패킷이 내 컴퓨터에 몇 밀리초 만에 도착하느냐가 아니라, 1초에 몇 MB의 자료를 전송받을 수 있느냐이다. 네트워크를 구성하는 케이블들에는 일정한 대역폭이 있기 때문에, 단위 시간당 일정량 이상의 자료를 전송할 수 없다. 따라서 이렇게 큰 파일을 다운로드할 경우 최단 경로로만 1초에 1MB를 전송받는 것보다, 패킷을 여러 경로로 나누어 보내 그중 일부가 좀더 먼길을 돌아오더라도 초당 10MB를 전송받는 것이 훨씬 이득이다. 아래 그림 (a) 는 한 컴퓨터 네트워크의 구성을 표현하는 그래프를 보여준다..

스패닝 트리 (Spanning Tree) ? 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 아래와 같은 예시들이 스패닝 트리라고 할 수 있다. 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 또한, 트리 형태여야 한다는 말은 선택된 간선이 사이클을 이루지 않는다는 의미여, 정점들이 부모-자식 관계로 연결될 필요는 없다는 것이다. 최소 스패닝 트리 (MST, Minimum Spanning Tree) ? 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리이다. 최소 스패닝 트리를 구할 수 있는 알고리즘은 두 가지가 있다. 크루스칼 (Kruskal) 알고리즘 : Kruskal Algorithm 프림 (Prim) 알고리즘 프림 (Prim) 알고리즘 크루스..

스패닝 트리 (Spanning Tree) ? 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 아래와 같은 예시들이 스패닝 트리라고 할 수 있다. 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 또한, 트리 형태여야 한다는 말은 선택된 간선이 사이클을 이루지 않는다는 의미여, 정점들이 부모-자식 관계로 연결될 필요는 없다는 것이다. 최소 스패닝 트리 (MST, Minimum Spanning Tree) ? 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리이다. 최소 스패닝 트리를 구할 수 있는 알고리즘은 두 가지가 있다. 크루스칼 (Kruskal) 알고리즘 프림 (Prim) 알고리즘 : Prim Algorithm 크루스칼 (Kruskal) 알고리즘 크..

소수 (Prime Number) ? 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다. 소수의 반대말로는 합성수가 있다. 합성수 (Composite Number) ? - 세 개 이상의 양의 약수를 갖는 자연수. 소수 판별 주어진 수 n이 소수인지를 판단하는 가장 단순한 방법은 2부터 n - 1 까지의 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인하고, 약수가 없다면 소수란 사실을 알 수 있다. 여기에 합성수 n이 p x q로 표현될 때 한 수는 항상 √n 이하, 다른 한 수는 √n 이상이라는 점을 이용하면, n - 1 까지 순회하지 않고 √n까지만 순회하도록 최적화할 수 있다. O(√n)의 시간복잡도로 동작하는 소수 판별 알고리즘 1과 2는 예외로 처리한다. 2를 제외한 모든 짝수는 소수..

단순한 문자열 검색 문자열 'ACBABCBABC' 에서 'ABC'를 찾는다고 해보자. 단순한 방법은 'ABC'를 한 칸씩 옮기면서 비교하는 것이다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 같다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 같다. 문자열 끝까지 진행하며, 여기서는 문자열 패턴 'ABC'가 총 2번 등장하는 것을 알 수 있다. ACBABCBABC 하지만, 이 단순 비교는 ..

벨만-포드 (Bellman-Ford) ? 다익스트라 알고리즘은 한 시작점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 중 가장 유용한 알고리즘이다. 하지만, 음수 간선이 있는 그래프의 경우 그 정당성이 보장되지 않는다. 벨만-포드의 최단 경로 알고리즘은 이와 같은 문제점을 해결하는 알고리즘이다. 벨만-포드는 다익스트라와 동일한, 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우, 이 또한 알려준다. 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 이것은 BFS를 기반으로 한 번..

플로이드 와샬(Floyd Warshall) ? 모든 쌍 간의 최단 거리를 구하고 싶다면 다익스트라, 벨만-포드 알고리즘보다 좀더 빠르고 간단한 플로이드 (Floyd) 의 모든 쌍 최단 거리 알고리즘을 사용하면 된다. 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][] 를 계산한다. 이 배열의 원소 dist[u][v] 는 정점 u에서 v로 가는 최단 거리를 나타낸다. 정점의 경유점들 플로이드 알고리즘의 동작 과정을 이해하기 위해서는 경로의 경유점의 개념을 소개할 필요가 있다. 두 정점 u, v를 잇는 어떤 경로가 있다고 하자. 당연하지만 이 경로는 항상 시작점 u와 끝점 v를 지난다. 이 외에 이 경로는 다른 정점들을 지나쳐 갈 수도 있다. u와 v를 직접 연결하..