본문 바로가기

Algorithm17

Quick sort 퀵 정렬 - 주어진 배열을 피벗(pivot) 을 기준으로 작은 원소들은 왼쪽, 큰 원소들을 오른쪽으로 위치시킨다. - 이렇게 나뉜 두 개의 배열을 같은 반복을 반복하여 정렬한다. - 특정 기준을 바탕으로 배열을 나눈다는 점에서 병합정렬과는 차이가 있다. 또한, 병합 정렬의 경우 각 부분의 정렬이 끝난 후 병합 처리를 해줘야 하는 반면, 퀵 정렬은 추가적인 작업이 필요하지 않다. - 평균적으로 O(n log n)의 시간복잡도를 가진다. 과정 - Pivot을 배열의 가장 왼쪽으로 잡냐(Hoare-Partition) 혹은 오른쪽으로 잡냐(Lomuto-Partition) 에 따라 과정에 차이가 있을 수 있다. - Hoare-Partition을 기준으로 설명한다. - Pivot은 가장 왼쪽에 위치하며, 두 개의 .. 2021. 10. 9.
Merge sort Merge sort (병합 정렬) - 병합 정렬이란, 여러 개의 정렬된 자료의 집합을 병합하여 하나의 정렬된 집합으로 만드는 방식이다. - 자료를 최소 단위의 문제까지 나눈 후, 차례대로 정렬하여 최종 정렬 결과를 얻어내는 분할정복 알고리즘을 활용한다. - O(n log n) 의 시간복잡도를 가진다. 과정 - 배열을 병합 정렬을 통해 정렬하는 과정을 살펴보자. - 우선 전체 배열에 대하여, 최소 크기의 부분집합이 될 때까지 분할작업을 계속한다. - 배열의 경우, 위 그림처럼 배열 안의 원소가 1개일 경우 최소 크기의 부분집합이 된다. - 분할 작업이 완료되면, 병합 단계에 들어간다. 각 2개의 부분집합을 정렬하면서, 하나의 집합으로 병합한다. - 최종적으로, 모든 부분집합이 1개로 병합될 때까지 반복한다.. 2021. 10. 9.
그리디 그리디 알고리즘 - 문제를 단순 무식하게, 탐욕적으로 푸는 알고리즘이다. - 탐욕적으로 해결한다는 것은 곧 현재 상황에서 지금 당장 좋은 것만 고른다는 것을 의미한다. - 문제 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야 함 - 보통 '가장 큰 or 작은' 과 같은 기준이 제시되므로, 정렬 알고리즘과 함께 출제되는 경우가 많다. 그리디 알고리즘의 정당성 - 그리디 알고리즘으로 문제의 해법을 찾았을 때는, 반드시 그 해법이 정당한지 검토해야 한다. - 그리디 알고리즘을 이용했을 때 최적 해를 구할 수 없는 가능성도 적지 않으므로 유의해야 한다. 다음 그림을 보자. 루트 노드부터 시작하여 거쳐가는 노드 값의 합을 최대로 만들고 싶을 때? 단순히 매 상황에서 가장 큰 값을 고른다면.. 2021. 9. 30.
비트연산 활용 비트연산 정리 & 연산자 특정 비트를 0으로 만들 수 있음 특정 비트가 0인지 1인지 검사하는 용도 (ex. 홀, 짝 확인) 0101 & 0000 ------- 0000# 홀짝 확인 a = 2 b = 3 print(a & 1) print(b & 1) >> 0 >> 1| 연산자 특정 비트를 1로 만드는 데에 활용될 수 있음 0101 & 1111 ------- 1111XOR 연산자 비트 단위로 비교하는 연산 (같으면 0, 다르면 1) 비트 토글(특정 비트를 반전하는 역할) 0101 & 1111 ------- 1010# XOR - 반전 # a배열에서 b의 원소를 인덱스 0->1, 1->0 으로 바꾸기 a = [1, 0, 0, 1, 1, 0, 0, 0] b = [0, 1, 2, 7] for i in b: #a[.. 2021. 9. 29.

티스토리툴바