Storage Gonie

개념 - 병합정렬 처럼 두 부분으로 쪼개어지는 것은 동일하나 Pivot item이 존재하여 이를 기준으로 나뉘어진다. 이를 기준으로 나눌 때 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시키게 된다. 또한, 병합정렬과 다르게 병합과정이 존재하지 않는다. - 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇값을 무엇으로 하느냐에 따라 효율이 크게 달라진다. - Top-down 방식으로(재귀) 구현됨 - 평균 시간복잡도는 O(nlogn), 최악의 경우 O(N^2) 시간복잡도 * 분할 방법에 따라 Hoare(호어), Lomuto(로무토) 방법이 존재함. * 위 두 방식 모두 평균적인 시간복잡도는 O(NlogN) 이지만 최악의 시간복잡도는 모두 O(N^2)이 될 수 있음. * 특정 상황에 의해서 Hoare(호..

개념 - 자료를 최소 단위로 쪼갠뒤, 차례대로 정렬 및 병합하여 최종 결과를 획득하는 방식 - Top-down 방식으로(재귀) 구현됨 - 평균 시간복잡도는 O(nlogn), 최악의 경우에도 O(nlogn) 으로 동일. 그림으로 이해하는 정렬 과정 1. 쪼갠다. 아무 조건없이 개수가 하나인 부분집합이 될 때까지 계속 둘로 2. 합친다. 원래의 크기로 합쳐질 때까지 매 단계마다 정렬하면서 내부에서 일어나는 세부 정렬과정 * 레코드를 '배열 혹은 Python의 List'로 구성하여 구현할 경우 오버헤드가 발생함 - 공간오버헤드 : 두 집합을 서로 비교하여 정렬된 상태로 합친걸 잠시 옮겨둘 배열 또는 리스트가 필요. - 이동오버헤드 : 정렬된 상태의 데이터를 원본데이터에 옮겨주는 과정이 필요. * 레코드를 '연..

# 정렬 알고리즘 - 시간복잡도에 따라 크게 2가지로 나눌 수 있다. - 실제 사용하게 되는 것은 효율이 좋은 O(NlogN) 알고리즘임. 1. 시간 복잡도가 O(N^2)인 알고리즘 - 선택, 버블, 삽입 정렬 2. 시간 복잡도가 O(NlogN)인 알고리즘 - 퀵, 힙, 병합 정렬 # 언어별 정렬함수 - 정렬 알고리즘을 직접 구현하는 것 보다는, 효율적으로 구현된 내장 함수를 사용하는 것이 더 좋다. @ C++의 경우 - STL인 헤더의 sort() 사용, sort(begin, end) 는 begin부터 end전까지 정렬해줌 begin은 첫번째 원소를 가리키고, end는 마지막 원소 다음을 가리킨다. // 배열을 정렬하는 소스 int a[10] = {}; sort(a, a+10); // a배열에서 ind..

소인수분해(Prime Factorization) # 개념 - 어떤 수 N을 소수의 곱으로 표현하는 것 - 소수를 직접 구하지 않아도 되며, 소수인지 아닌지 판단했던 원리를 이용한다. - n이 소수가 아닌 경우, 1과 n을 제외한 두 수 n = a * b 형태로 나타낼 수 있고 중복되는 조합을 제외하기 위해 a

소수(Prime number) # 두줄 요약 - 연속된 범위에서 소수만 찾아내는 문제는 에라토스테네스의 채를 이용하고, - 띄엄띄엄 있는 수들을 소수인지 아닌지 따지는 문제라면 소수를 판단하는 세 번째 방법을 이용하자. # 개념 - 1보다 크고 약수가 1과 자기 자신밖에 없는 수 - N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 작은 자연수로 나누어 떨어지면 안된다. @ 소수를 판단하는 첫 번째 방법 => 하나의 수 당 O(N), N개의 수라면 O(N^2) - 2보다 크거나 같고, N-1보다 작거나 작은 자연수로 나누어 떨어지면 소수가 아닌 것으로 처리. - 시간복잡도 O(N) bool prime(int n) { if (n < 2){ return false; for (int i = 2; i..

진법변환(Base Conversion) # 세 줄 요약 - A진법을 B진법으로 바꾸고 싶다면 "A진법 -> 10진법 -> B진법" 을 거치면 된다.(A, B는 10진법이 아님) - "A진법 -> 10진법", "10진법 -> B진법" 각각의 변환 방법은 아래와 같다. - 입력이 0이 들어올 때 출력이 0으로 되도록 처리해주는 것을 깜빡하지 말자. # 개념 n진법이란 각 자리가 0 ~ n-1의 수로 표현되는 것을 말함 @ A진법의 수 -> 10진법의 수 변환 방법 - 방법1) 2진법을 10진법으로 바꾸는 방법을 생각하면 됨. 2진법 101은 10진법으로 1*2^2 + 0*2^1 + 1*2^0 = 5 ex) 3진법의 수 102를 10진법의 수로 변환하는 예시 1*3^2 + 0*3^1 + 1*3^0 = 11 -..

최대공약수(GCD, Greatest Common Divisor) # 한줄요약 - 최대공약수를 구할 땐 유클리드 호제법을 이용하자. # 개념 - 최대공약수는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. - 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다. - 3개 이상의 수에 대한 최대공약수를 구해야 하는 경우 GCD(GCD(A,B), C) 이런 방식으로 2개씩 묶어서 계산하면 된다. @ 최대공약수를 구하는 첫 번째 방법 => 시간복잡도 : O(N) - a와 b를 2 ~ min(a,b) 까지의 모든 정수로 나누어 보는 것. - 가장 쉬운 방법 int g = 1; // 모든 경우에 두 수는 공약수 1을 가지기 때문에 1로 초기화함 for(int i = 2; i 가장 효율적임 - 유클리드 호제..

나머지 연산 개념 # 자주 등장하는 곳 - 다이나믹 문제에서 전체 경우의 수를 구하는 문제일 때, 답을 M으로 나눈 나머지를 출력하라는 문제가 자주 등장한다. 이 때 최종 계산값에 나머지 연산을 수행한 단순 계산값을 출력하면 된다고 생각하지만 그렇지 않다. 이런 문제의 의도는 중간 및 최종 계산값이 int형의 저장범위를 넘어서기 때문에 이를 극복하여 문제를 해결하라는 것이다. - 이런 유형의 문제는 다음의 원리를 이용해 memoization 배열인 d[i]에 M으로 나눈 나머지 값을 저장함으로써 해결할 수 있다. # 사용가능한 법칙 1. (A + B) % M = ((A % M) + (B % M)) % M 2. (A x B) % M = ((A % M) x (B % M)) % M 3. (A - B) % M ..

암호코드 문제 - https://www.acmicpc.net/problem/2011 문제요약 숫자로된 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램 A - 1, B - 2, ,,, Z - 26 ex) 25114 -> "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" (총 6가지) 해결 방법 1. D 정의 D[i] = "i번 문자까지 해석했을 때, 나올 수 있는 해석의 가지수" 암호는 두가지 중 하나이다. - 1자리 수 암호 : 1(A) ~ 9(I) -> 0 제외 - 2자리 수 암호 : 10(J) ~ 26(Z) 2. 점화식 세우기 case 1) 한자리 수의 암호로 보는 경우(....0) i번째 문자까지 해석했을 때 나올 수 있는 해석의 가..

합분해 문제 * 어려워서 깊은 이해는 못하겠지만 암기는 할 수 있을 듯 하다. - https://www.acmicpc.net/problem/2225 문제요약 N과 K값이 주어지면 0~N의 수 K개로 N을 나타낼 수 있는 모든 경우의 수를 구하고 그 수를 1,000,000,000로 나눈 나머지를 출력하라. 해결 방법 1. D 정의 D[K][N] = "K개의 수를 더해서 합이 N이 되는 경우의 수" 마지막 항이 L값을 가진다면 이전 항들의 합은 N-L임 그리고 L을 분리시킨다면 K-1개의 수를 더해서 합이 N-L이 되는 경우의 수가 됨. 따라서, D[K][N]은 다음의 점화식으로 구할 수 있음 이렇게 맨 뒤의 항을 하나씩 분리시키는 과정이 반복될 때 'K'와 'N'을 입력받으면 K는 1~'K' 의 범위를 가..