조준화의 오류정정

특정 상황에서 비교를 하지 않고 정렬을 함으로써 O(n) 시간 내에 정렬을 할 수 있다. 계수정렬(Counting Sort) 원소의 값이 한정적으로 0 ~ k의 자연수로 제한되어 있는 경우 사용 가능하다. 각 입력원소 x에 대해 x보다 작은 원소의 개수를 센다. 그리고 원소 x의 위치를 정한다. 예를 들어 x보다 작은 원소가 17개라면 x를 18번째 자리에 위치시킨다. 입력 배열 A와 출력을 저장할 배열 B, 임시 작업 공간 배열 C를 사용한다. ​ CountingSort(A, B, k){ vector C(k, 0); for j=1 to A.length C[A[j]]++; //C[i]는 값이 i인 원소의 개수이다. for j=1 to k C[j]+=C[j-1]; //C[i]는 이제 값이 i보다 작거나 같..

퀵 정렬 평균적으로 가장 좋은 성능을 가졌다. 기준 원소를 잡고 기준 원소를 기준으로 양쪽으로 재배치하면서 정렬한다. 퀵정렬 또한 Divide-and-conquer을 이용한다. ​ 분할 : 배열 A [p.. r]을 두 개의 부분 배열 A [p.. q - 1], A [q + 1.. r]로 분할한다. 전자는 A [q]보다 작거나 같은 원소를, 후자는 A [q]보다 크거나 같은 원소를 배치한다. ​ 정복 : 퀵 정렬을 재귀 호출해서 두 부분 배열을 퀵정렬한다. ​ 결합 : 부분 배열이 이미 정렬되어 있으므로 저절로 합쳐져 있다. 기본적인 알고리즘은 이렇고 자세한 구현은 코드로 보자. QuickSort(A, p, r){ if(p < r) q = Partition(A, p, r) QUICKSORT(A, p, q-..

선택 정렬 최소 원소를 찾고, 최소 원소를 제일 앞으로 보내는 것을 반복하면서 정렬한다. for루프를 (n-1) + (n-2) + (n-3) +... + 2 + 1번 반복하므로 시간 복잡도는 O(n^2)이다. for(int i=0; i

Stack LIFO(Last In First Out) 속성을 가진 자료구조이다. 책 쌓기처럼 가장 마지막에 push된 데이터가 pop된다. front에서 push, pop 모두 일어나며 벡터와 비슷한 메서드를 사용한다. Queue FIFO(First In First Out) 속성을 가진 자료구조이다. 줄 서기처럼 먼저 push된 데이터가 pop된다. front에서 pop, back에서 push가 일어나며 벡터와 비슷한 메서드를 사용한다. Priority_queue priority_queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 우선순위 큐 자료구조이다. priority_queue로 정의한다. container는 디폴트로 vector을 사용한다. deque로 사용할 수 있다. co..

TIL을 쓰는 걸 잊고 있었다. 굉장히 아쉬운 일이지만 이미 지난걸 다시 쓰긴 싫다. 오늘은 set, map 컨테이너 공부 후 set, map, 우선순위 큐와 관련된 문제를 하나씩 풀었다. 정렬 문제도 하나 풀었다. 정렬 문제가 제일 어려웠던 것 같다. 확통을 오랜만에 다뤄서 기억이 잘 안 났다. 정렬 문제들은 꽤 많이 풀어서 이제 다른 주제로 넘어가 볼까 한다. 정렬과 해시테이블, 기본 자료구조 문제는 꽤 다뤘으니 마지막 복습 겸 블로그에 정리하고 C++ 관련 컨테이너도 복습하는 식으로 마무리한다. 그리고 검색트리와 문자열로 넘어가야겠다. 문자열이 정말 취약한데 코테에서 여기저기 많이 나와서 이번 기회에 진짜 꼭 잡는다.

2 7 I 16 I -5643 D -1 D 1 D 1 I 123 D -1 9 I -45 I 653 D 1 I -642 I 45 I 97 D 1 D -1 I 333 answer : EMPTY 333 -45 이중 우선순위 큐는 우선순위를 최대와 최소로 두 개 가지고 처리하는 우선순위 큐이다. 우선순위 큐를 두 개 선언하는 방법과 맵을 쓰는 방법 멀티 셋을 쓰는 방법을 떠올렸다. 맵을 떠올린 이유는 입력하는 원소가 중복이 될 수 있어서 키를 원소로 하고 value를 해당 원소의 개수로 하려고 했는데 굳이 짜보진 않았다. 우선순위 큐와 멀티 셋 중 고민하다가 우선순위 큐 두 개를 쓰는 것보다 멀티 셋 하나로 처리하는 게 공간적으로 이득을 보는 것 같아서 멀티 셋으로 짰다. set 컨테이너 사용법과 포인터와 주소..

2 3 hat headgear sunglasses eyewear turban headgear 3 mask face sunglasses face makeup face answer : 5 3 해빈이의 옷을 종류별로 입을 수 있는 최대 가짓수를 계산하는 문제이다. 알몸은 안되며, 종류별로 착용하지 않을 수도 있다. 확률과 통계 시간에 종종 풀어본 유형의 문제인데, 해빈이 옷이 1번 종류 4개, 2번 종류 2개, 3번 종류 2개가 있다고 하면, 각 종류별로 입지 않는 경우 한 개씩을 추가해서 5 * 3 * 3을 하면 옷을 입지 않는 것을 포함 가능한 모든 조합의 수이다. 여기서 옷을 입지 않는 경우를 빼주면 답이 된다. 알고리즘은 이렇게 짜면 되는데, 구현이 문제다. 사실 옷의 이름은 필요가 없다. 종류별로 몇..

Map이란? key - value로 구성된 레드블랙트리이다. key와 value는 pair 객체 형태로 저장된다. key의 중복은 허용되지 않는다. multimap의 경우 중복 key를 허용한다. 삽입되면서 키를 기준으로 자동으로 정렬된다. 디폴트로 오름차순이다. Map 선언과 원소의 접근법 map 변수이름으로 선언한다. 이때 compare에 less를 주면 오름차순으로, greater을 주면 내림차순으로 정렬한다. 디폴트로는 오름차순으로 선언된다. m[key] = val;처럼 []를 사용하여 원소를 추가, 수정이 가능하다. []를 사용하여 원소를 추가하는 경우 value가 새로 만들어진 건지, 기존 값이 변경된 건지 구분할 수 없다. map.begin() 으로 맵의 시작 iterator을 반환할 수 있..

4 -1 2 1 3 answer : 6 6 0 1 2 4 3 5 answer : 27 1 -1 answer : -1 배열의 각 숫자를 위치에 관계없이 두 개씩 묶을 수도 있고 묶지 않을 수 있다. 그리고 원소들의 합을 구하는데, 묶은 수끼리는 곱하고 모든 수를 더해서 그 값이 최대가 되게 하면 된다. 우선 배열을 정렬한다. 그 후 규칙에 따라서 묶을지 말지, 어떤 수와 묶을지를 정하였다. 규칙 1) 음수끼리는 묶는다. 단, 작은 수 끼리 묶는다. 규칙 2) 묶이지 못한 음수는 0과 묶을 수 있으면 묶고 아니라면 묶지 않는다. 규칙 3) 0은 음수가 아니면 묶지 않는다. 규칙 4) 1은 묶지 않는다. 규칙 5) 양수는 양수끼리 묶는다. 단, 큰 수 끼리 묶는다. 이 정도 규칙을 생각했고, 이제 이 조건들을..

int 자료형으로 표현 가능한 숫자는 210,000,000(21억) 언저리까지이다. 그 이상의 숫자는 오버플로우가 발생하므로 long long 자료형을 사용해야 한다. 내가 코딩하다가 숫자가 21억이 넘어갈지 안 갈지 어떻게 알아??라는 의문이 들 수 있다. 1. 먼저 알고리즘을 생각해본다. 사람마다 다르지만 나는 퍼수도코드로 짜고 시작한다. 2. 시간복잡도를 생각해본다. O(N*M) 이런 식으로 나온다면 N과 M의 최댓값을 기준으로 곱해서 생각하면 된다. 얼추 21억이 넘겠다 싶으면 안전하게 long long으로 짜는 편이 좋다. 3. long long으로 코드를 바꿀 때 콤팩트하게 확실하게 안 바꿔도 되는 자료형을 제외하고는 다 바꾸는 편이 좋다. 연산 중 자동 형변환이 일어날 수 있다. 시간초과도 ..