이것저것

(오름차순으로 정렬하는 경우) 가장 원시적인 방법으로 "매번 가장 작은 것을 선택한다" 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 swap 하고, 그 다음으로 작은 데이터를 선택해 앞에서 두번째 데이터와 swap 하는 과정을 반복 - N-1 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. - 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요 - 연산횟수 : N + (N-1) + .... + 2 => 근사치 : N(N+1)/2 => O(N^2) (선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 정도 이상이면 정렬 속도 급격하게 느려진다)

Set - LinkedList 와 달리 데이터의 중복을 허용하지 않는다. - 인덱스 대신 iterator를 이용해 검색 - 순서가 보장되지 않는다. - insert, erase - 삽입/삭제 : O(logN) - Set은 Map의 축소형 => Key 만 있는 Map (Map도 Key는 중복 불가하기 때문에) set s; s.insert(1); s.insert(2); s.insert(1); s.insert(2); //s안에는 1,2,1,2 가 아닌 1,2만 있다 Map - key-value 형식으로 데이터를 저장 - 순서가 보장되지 않는다. - Key는 중복 불가, value는 중복 가능 - 삽입/삭제/탐색 : O(logN) - map m; //string : key, char : value (pair 형..

- 현재 우선순위 큐 안에서 제일 우선순위가 높은 원소가 pop됨 - 주요 명령어 : push, pop, top - Heap 을 이용해서 구현 - heap 은 트리 구조로 되어있다. (노드들로 구성되어있으며, 각 노드는 부모-자식 관계로 이루어져 있다.) - max heap : 숫자가 클 수록 우선순위가 높다. - min heap : 숫자가 작을 수록 우선순위가 높다. - 삽입/삭제 : O(logN) c++ 에서 priority queue는 max heap으로 구성된다. min heap으로 구성하기 위해서는 greater 을 사용하여 정렬하면 된다. - max heap priority queue 선언 priority_queue pq; - min heap priority queue 선언 priority_q..

소수와 관련된 알고리즘은 두 가지가 있다. 어떤 수 N이 소수인지 아닌지 판별하는 방법 N보나 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법 (N이하의 소수) 소수 : 약수가 1과 자기 자신밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. ⇒O(N) N이 소수가 되려면, 2보다 크거나 같고 N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문 ( N=a x b로 나타낼 수 있는데, a가 작을수록 b는 크다. 가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 N/2를 넘지 않는다.) ⇒O(N/2) N이 소수가 되려면, 2보다 크거나 같고, 루트 N보다 작거나..

최대공약수(혹은 최소공배수)를 구할때 유클리드 호제법을 사용하면 간단하다. a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b,r) 과 같다. r=0 이면 그 때, b가 최대 공약수이다. //재귀함수를 사용하여 구현한 유클리드 호제법 int GCD(int a,int b){ if(b==0){ return a; }else{ return GCD(b,a%b); } } 세 수의 최대공약수는 다음과 같이 구할 수 있다. GCD(a,b,c) = GCD(GCD(a,b),c) 네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다. 최소공배수는 줄여서 LCM이라고 한다. 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수 최소공배수는 GCD 를 응용해서 구할 수 있다. G = ..

모든 경우를 다 해본다 = 모든 방법을 다 한번씩 시도해본다. 가능한 방법의 개수(경우의 수)를 새봐야한다 방법의 개수가 많지 않을 때만 사용 가능하다. 방법의 수를 새본다. 새보고 시간 제한을 넘지 않을 것 같은 경우만 사용 문제의 가능한 경우의 수를 계산해본다. 직접 계산을 통해서 구한다. 대부분 손으로 계산 가능한 모든 방법을 다 만들어본다. 하나도 빠짐없이 만들어야한다. 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀호출사용, 비트마스크 사용이 있다. 각각의 방법을 이용해 답을 구해본다. 경우의 수 N 명의 사람이 한줄로 서는 경우의 수 → N! N 명의 사람 중에서 대표 두명을 뽑는 경우의 수 → (N)(N-1)2 N 명의 사람 중에서 반장 1 부반장 1을 뽑는 경우의 수 (..

매 순간 최선의 경우만을 골라간다 (나중은 생각하지 않는다!) 동전 거스름돈 문제 10,50,100,500 원 동전들을 무한하게 갖고 있다. 손님에게 800원을 거슬러주려고 할 때, 동전을 최소한으로 주는 방법은? ⇒ 금액을 큰 것부터 주면 좋다. (800 - 500 - 100 - 100 -100) Greedy 이다. 100, 400, 500 원 동전들을 무한하게 갖고 있다. 손님에게 800원을 거슬러 주려고 할 때, 동전을 최소한으로 주는 방법은? ⇒ Greedy Algorithm이 먹히지 않는다. (400+400 = 800, 동전 두개씀) 문제가 그리디 문제인지 판별하는 것이 어렵다! 정당성 증명 (두 가지 조건 만족하면 Greedy) 1. 탐욕적 선택 속성 모든 경우를 볼 필요없이 항상 최선의 경우..