소파와 바보개의 블로그

Binary Search?배열 내의 요소를 찾는 일반적인 접근 방법은 전체 배열을 for loop로 순회하는 것 입니다. 이러한 접근 방법의 시간복잡도는 O(N) 입니다. 만약 배열 내 요소들의 순서가 임의대로 생성된다면 별다른 방법이 없겠지만 배열이 정렬되어 있다면 훨씬 더 빠른 시간에 수행할 수 있는 좋은 방법이 있습니다. Binary Search는 정렬된 배열에서 요소를 O(logN) 시간에 찾아냅니다.Binary Search Implementation 1 일반적인 구현 방식으로, 초기 상태에는 모든 배열 요소가 탐색 대상입니다. 그러나 step이 진행될 때마다, 탐색 대상을 절반으로 줄입니다. 각 단계에서는, 탐색 대상의 중간 요소를 확인합니다.  만약 중간 요소가 탐색 대상과 같다면 탐색은 종료..

Sorting in C++매번 정렬할 때마다 정렬을 직접 구현하는 것은 좋은 생각이 아닙니다. C++ 등의 Programming Language들은 좋은 내장 라이브러리를 제공합니다. 예를 들면, C++의 standard 라이브러리에는 배열과 다른 자료 구조들을 쉽게 정렬 할 수 있게 도와주는 sort function이 내장되어 있습니다. 이런 것들을 사용하면 시간도 절약할 수 있고 훨씬 더 좋은 성능을 내줍니다. 아래 코드는 vector를 오름차순으로 정렬합니다. vector v = {9, 8, 7, 5, 4, 2, 6}; sort(v.begin(), v.end()); // 2 4 5 6 7 8 9 아래 코드는 vector를 내림차순으로 정렬합니다. vector v = {9, 8,..

Counting Sort?O(NlogN) 에 정렬하지 않으려면 배열의 요소를 비교하는 것 외에 다른 정보를 이용해야 합니다.  Counting Sort는 만약 배열 내의 모든 요소가 0...c 사이의 정수라면 c = O(N)에 배열을 정렬합니다. Counting Sort는 bookkeeping 배열을 사용하며, 이 배열은 원본 배열의 값을 인덱스로 갖습니다. 원본 배열을 1회 순회하면서 이 배열에서 등장하는 빈도 수를 계산 합니다. 예를 들어, { 1 3 7 9 8 9 5 1 } 이라는 배열이 있을 때이것에 대한 bookkeeping 배열은 { 2 0 1 0 1 0 1 1 2 } 입니다. bookkeeping 배열 생성에는 O(N) 시간이 걸리고, 이 작업이 끝나게 되면 앞에서 부터 읽으면서 갯수 만큼 ..

Merge Sort?앞선 Bubble Sort와 같이 연속적인 요소들을 교환하는 방식이 아니라면 O(NlogN)에 정렬하는 것이 가능합니다. 그 중 한가지는 재귀(Recursion)를 기반으로 한 Merge Sort입니다. Merge Sort는 부분 배열인 [S ... E] 를 다음 과정으로 정렬합니다. 1. 만약 S와 E가 같다면 재귀 호출을 종료합니다.  2. S와 E의 중간 요소를 계산합니다. k = (S+E)/2 3. 재귀적으로 부분 배열을 정렬합니다. [S ... k] 4. 재귀적으로 부분 배열을 정렬합니다. [k+1 ... E] 5. 정렬된 부분 배열들, [S ... k] 와 [k+1 ... E] 를 정렬된 [S ... E] 로 합칩니다. Merge Sort는 부분 배열의 크기를 매 단계마다 ..

[백준/BOJ] 11920 버블 정렬 (c++)11920번: 버블 정렬 2025.02.17 - [Competitive Programming] - 02. 정렬 (Sorting Theory) (1. bubble sort) 정렬 (Sorting Theory) (1. bubble sort)Bubble SortO(N^2)에 수행되는 간단한 알고리즘입니다.짧은 두개의 중첩된 Loop로 구성됩니다.Bubble Sort는 N개의 round가 있습니다. 각 round마다 배열의 요소들을 순회합니다.두개의 정확한 순서로 배치dnsldprp.tistory.com버블 정렬 과정에서 버블 정렬의 round가 K번 진행되었을때의 배열 상태를 출력하는 문제입니다.input size가 10만이므로 O(NK) 시간복잡도를 갖는 버블 ..

[백준/BOJ] 1377 버블 소트 (c++) https://www.acmicpc.net/problem/1377 2025.02.17 - [Competitive Programming] - 02. 정렬 (Sorting Theory) (1. bubble sort) 정렬 (Sorting Theory) (1. bubble sort)Bubble SortO(N^2)에 수행되는 간단한 알고리즘입니다.짧은 두개의 중첩된 Loop로 구성됩니다.Bubble Sort는 N개의 round가 있습니다. 각 round마다 배열의 요소들을 순회합니다.두개의 정확한 순서로 배치dnsldprp.tistory.com 최대 50만개의 배열이 주어지고 Bubble Sort를 수행했을때 몇번째 round에 정렬이 완료되는지를 알아내야 합니다...

Bubble Sort?O(N^2)에 수행되는 간단한 알고리즘입니다.짧은 두개의 중첩된 Loop로 구성됩니다. Bubble Sort는 N개의 round가 있습니다. 각 round마다 배열의 요소들을 순회합니다.두개의 정확한 순서로 배치되어 있지 않은 연속적인 요소가 발견되면 두개를 변경합니다.아래와 같은 코드로 수행됩니다. REP(i, 0, N) { REP(j, 0, N-1) { if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } } } 첫 번째 round가 끝나게 되면, 가장 큰 요소는 정확한 위치 (맨 끝)에 위치하게 됩니다.그리고 K 번째 round가 끝나게 되면 K 번째 큰..