yevdev◡̈

💡최단 경로 찾기? 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제이다. 💡어떻게 구할까? 무작위 방법 : 모든 도시들이 다 연결되어 있다면 출발점에서 가능한 경로의 수는 θ(n!) 다익스트라 최단경로 알고리즘 그리디 알고리즘 (결과적으로) 출발점에서 가까운 도시부터 차례대로 최단 경로를 탐색 한번 결정된 최단 경로는 절대 바뀌지 않으며 출발점에서 더 먼 도시의 최단 경로를 구할 때 이용 ➰최단 경로 찾기 알고리즘의 종류 단일 시작점 최단 경로 알고리즘 : 출발지점을 하나 선택하면 나머지 다른 모든 지점까지의 최단 경로를 알려주는 유형 모든 쌍 최단 경로 알고리즘 : 모든 지점들간의 최단 경로를 알려주는 유형 최단 경로 찾기 알고리즘은 프림의 최소 신장 트리 알고..

💡신장트리? 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리 정점의 수가 n 개, 신장트리의 간선의 수는 n-1 개 💡최소 신장 트리? 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리 💡어떻게 최소 신장 트리를 찾을까? 무작위 기법 가능한 신장 트리를 모두 구한 다음, 최소 비용의 신장 트리를 선택 모든 정점 간에 간선이 있는 완전 그래프의 경우 신장 트리의 수는 n^(n-2) 그리디 알고리즘 크리스컬과 프림 알고리즘 있음 알고리즘 입력은 1개의 연결요소로 된 가중치 그래프이다. 💡크리스컬 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 '욕심내어' 그 선분을 추가 시킨다. 각 단계에서 가중치가 최소인 간..

💡최근접 점의 쌍 (Closest Pair) 문제? 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 💡간단한 해결 방법 : O(n^2) 알고리즘 모든 점에 대해 각각의 두점 사이의 거리를 계산하여 가장 가까운 점의 쌍 찾기 비교헤야 할 쌍은 몇개? nC2 = n(n-1)/2 = O(n^2) 한쌍의 거리 계산은 O(1) 따라서 시간 복잡도는 O(n^2) 💡보다 효율적인 해결방법 : 분할 정복 이용 n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍 찾기 2개의 부분해 중에서 짧은 거리 (d)를 가진 점의 쌍을 일단 찾기 (재귀적으로) 결합 : 두개의 부분해를 취합할 때는 반드시 두 부분 문제서 각각 한 점 씩 포함되는 점의 쌍 중에서 그 거리가..

이미 분할정복 알고리즘을 활용한 대표적인 문제를 몇개 블로그에 작성해놓았다. 여기에는 분할정복의 의미와 사용시에 주의할 점을 작성하고자 한다! 💡분할 정복 (Divide-and-Conquer) 알고리즘 ? 주어진 문제의 입력을 분할하여 문제를 해결 (정복) 하는 방식의 알고리즘 하향식 접근방법 (Top-down) 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래의 문제의 해를 얻음. Divide : 나누기 Conquer : 각 부분해를 해결 Combine : (필요하다면) 부문제의 해를 결합 🚫분할 정복을 적용하는데 있어서 주의할 점 분할 정복이 부적절한 경우 : 입력이 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경..

선택문제? n개의 숫자들 중에서 k번재로 작은 숫자를 찾는 문제 💡어떻게 해결하면 좋을까? 첫번째 방법 : 순차탐색! 최소숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거 숫자제거 = 추가 수행시간 + 추가 메모리 필요 O(kn) -> 최악의 경우, n번의 순차 탐색 ! 주어진 숫자 개수 n이 크면 커질 수 있다. 두번째 방법 : 숫자들을 정렬한 후, k번째 숫자를 찾는다. O(nlogn) k가 작을 경우, 1번 방법이 유리 그렇지 않을 경우, 2번 방법이 유리 💡아이디어 이진탐색 활용 : 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 1/2로 나눈 두 부분 중에서 한 부분만을 검색 선택문제는 입력이 정렬되어 있지 않아서, 입력 숫자들 중에서 (퀵..

💡합병정렬 알고리즘? 안정정렬에 속하며, 분할 정복 알고리즘의 하나 분할 정복 방법 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결 대개 순환 호출을 이용하여 구현 (재귀적) 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우, 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬 두부분 리스트를 다시 하나의 정렬된 리스트로 합병 [ 합병정렬 알고리즘의 구체적인 개념 ] 하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 ..

💡퀵 정렬(Quick sort) 알고리즘? 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함 분할 정복 방법을 통해 리스트를 정렬 리스트 가운데서 하나의 원소를 고름, 이 원소를 피벗 이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 비펏보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. -> 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. -> 리스트의 크기가 0이나 1이 될때까지 재귀를 반복 💡구체적으로 알고리즘을 파헤쳐보자 퀵 정렬은 다음의 단계로 이루어진다. 분할 : 입력 ..

알고리즘 수업 첫주차 실습 ! 알고리즘과는 별로 안친하고,, 친해지려고 노력하고 싶은,,, 사람으로써,,,, 여기에 푼 해답 코드는 모두,,,, 완벽하고,, 막그런 코드는 아니니,,, 유의하시길,,,, 내멋대로 내맘대로 푸는 코드...!!! Description 여러 명의 사람들을 위한 치킨을 준비하려고 한다. 피보나치 수열(Fibonacci Numbers)과 제켄도르프 정리(Zeckendorf's Theorem)를 이용하여, 인원 수가 주어졌을 때 필요한 치킨의 양을 구하여라. Input 주어진 사람의 수 (입력되는 값은 문자열 형태의 값임. 형변환 후 사용할 것) 입력 값은 최대 300,000,000 이하의 자연수 Output 필요한 치킨의 마리 수 Sample Input 17 Sample outpu..