본문 바로가기

Algorithm

 (30)
[Algorithm] 분할정복 알고리즘 이미 분할정복 알고리즘을 활용한 대표적인 문제를 몇개 블로그에 작성해놓았다. 여기에는 분할정복의 의미와 사용시에 주의할 점을 작성하고자 한다! 💡분할 정복 (Divide-and-Conquer) 알고리즘 ? 주어진 문제의 입력을 분할하여 문제를 해결 (정복) 하는 방식의 알고리즘 하향식 접근방법 (Top-down) 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래의 문제의 해를 얻음. Divide : 나누기 Conquer : 각 부분해를 해결 Combine : (필요하다면) 부문제의 해를 결합 🚫분할 정복을 적용하는데 있어서 주의할 점 분할 정복이 부적절한 경우 : 입력이 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경..
[Algorithm] 선택문제 알고리즘 (feat. Quick-Sort) 선택문제? n개의 숫자들 중에서 k번재로 작은 숫자를 찾는 문제 💡어떻게 해결하면 좋을까? 첫번째 방법 : 순차탐색! 최소숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거 숫자제거 = 추가 수행시간 + 추가 메모리 필요 O(kn) -> 최악의 경우, n번의 순차 탐색 ! 주어진 숫자 개수 n이 크면 커질 수 있다. 두번째 방법 : 숫자들을 정렬한 후, k번째 숫자를 찾는다. O(nlogn) k가 작을 경우, 1번 방법이 유리 그렇지 않을 경우, 2번 방법이 유리 💡아이디어 이진탐색 활용 : 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 1/2로 나눈 두 부분 중에서 한 부분만을 검색 선택문제는 입력이 정렬되어 있지 않아서, 입력 숫자들 중에서 (퀵..
[Algorithm] 합병정렬 (Merge sort) 💡합병정렬 알고리즘? 안정정렬에 속하며, 분할 정복 알고리즘의 하나 분할 정복 방법 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결 대개 순환 호출을 이용하여 구현 (재귀적) 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우, 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬 두부분 리스트를 다시 하나의 정렬된 리스트로 합병 [ 합병정렬 알고리즘의 구체적인 개념 ] 하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 ..
[Algorithm] 퀵 정렬 (Quick Sort) 💡퀵 정렬(Quick sort) 알고리즘? 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함 분할 정복 방법을 통해 리스트를 정렬 리스트 가운데서 하나의 원소를 고름, 이 원소를 피벗 이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 비펏보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. -> 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. -> 리스트의 크기가 0이나 1이 될때까지 재귀를 반복 💡구체적으로 알고리즘을 파헤쳐보자 퀵 정렬은 다음의 단계로 이루어진다. 분할 : 입력 ..
[Algorithm] 피보나치킨 / Fiona-chicken 알고리즘 수업 첫주차 실습 ! 알고리즘과는 별로 안친하고,, 친해지려고 노력하고 싶은,,, 사람으로써,,,, 여기에 푼 해답 코드는 모두,,,, 완벽하고,, 막그런 코드는 아니니,,, 유의하시길,,,, 내멋대로 내맘대로 푸는 코드...!!! Description 여러 명의 사람들을 위한 치킨을 준비하려고 한다. 피보나치 수열(Fibonacci Numbers)과 제켄도르프 정리(Zeckendorf's Theorem)를 이용하여, 인원 수가 주어졌을 때 필요한 치킨의 양을 구하여라. Input 주어진 사람의 수 (입력되는 값은 문자열 형태의 값임. 형변환 후 사용할 것) 입력 값은 최대 300,000,000 이하의 자연수 Output 필요한 치킨의 마리 수 Sample Input 17 Sample outpu..

티스토리툴바