yevdev◡̈

💡배낭 문제 n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제 💡부분 배낭 문제 물건을 부분적으로 (쪼개서) 담는 것을 허용 최적해를 위해서 '욕심내어' 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다. 만약, 그 다음으로 값나가는 물건을 '통째로' 배낭에 넣을 수 없게되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다. 💡의사코드 입력 : n개의 물건 및 각 물건의 무게, 가치, 배낭의 용량 C 출력 : 배낭에 담은 물건 리스트 L, 배낭에 담은 물건의 가치 합 v 1. 각 물건에 대해 단위 무게당 가치를 계산 2. 물건들을..

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

이미 분할정복 알고리즘을 활용한 대표적인 문제를 몇개 블로그에 작성해놓았다. 여기에는 분할정복의 의미와 사용시에 주의할 점을 작성하고자 한다! 💡분할 정복 (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..