Storage Gonie

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1 # C++(선정렬 후 카운트) #include #include #include using namespace std; int main() { int n; cin >> n; // 숫자입력받기 vector v(n); for (int i = 0; i > v[i]; // 정렬하기 sort(v.begin(), v.end()); // 숫자를 카운트 하기 long long num; int num_count = 0; int temp_count = 0; for (int i = 0; i < n; i++){ temp_count += 1; if(i == n-1 || v[i] != v..

용도 : pair가 그냥 두 자료형을 묶는 거라면, map은 왼쪽의 값을 key값으로 사용하고, 오른쪽의 값은 value값으로 사용한다. key와 value를 가지는 노드를 생성해서 정렬된 '트리형태'로 저장해두어 탐색속도를 높인다.(key를 기준으로 정렬됨) python의 딕셔너리와 비슷하나 딕셔너리는 해시테이블로 구성되고, map은 트리로 구성된다.(레드 블랙 트리가 사용됨) index를 이용해 자료에 접근하는 배열과 달리 key값을 이용해 value에 접근할 수 있다.(key는 unique해야함) 중복된 key를 사용하여 입력하면 덮어씌어짐. 추가, 삽입, 삭제 시 자동정렬된다는 것도 알아두자. 아래 사용할 수 있는 함수를 보면 알겠지만 pair로 map을 구현했다는 것을 알 수 있다. 1. 헤더파..

정렬을 적용한 문제풀이 # 가장 빈도가 높은 수를 출력하는 문제 - https://www.acmicpc.net/problem/11652 - 방법1) 정렬한 뒤 하나씩 카운트하기, if (a[i-1] != a[i]) 으로 서로 다른 수의 경계값을 인식함. 시간복잡도 = 정렬(NlogN) + 카운트(N) 정렬된 수에서 경계값을 인식시켜줄 때는 a[i] a[i+1]을 비교하고, 제일 마지막 값은 경계값을 인식 못 하므로 꼭 따로 조건 추가해주기! - 방법2) C++ STL의 map을 이용하여 개수를 카운트 하고, 가장 등장빈도가 높으면서 작은 수 인 것을 출력. 시간복잡도 = 하나씩 카운트(N) + 비교(N이하) * count 메소드를 사용할 수 없는 이유는 시간복잡도가 N*N이 되어버리기 때문. # 오름차순..

정렬을 적용한 문제풀이 # N개의 수를 입력받아서 정렬하는 문제 - https://www.acmicpc.net/problem/2751 - 퀵 정렬 직접구현, 병합 정렬 직접구현, STL sort함수 사용 3가지 방법으로 풀이를 진행하였음 # (x, y) 좌표 정렬하기 문제 - https://www.acmicpc.net/problem/11650 - 아래의 여러가지 방법으로 정렬할 수 있음 1) pair, vector, sort 사용 2) struct, vector, sort ( , , 비교함수) 사용 3) struct, vector, sort( , , 람다함수) 4) struct, vector, sort, 연산자 오버로딩 # (x, y) 좌표 정렬하기2 문제 - https://www.acmicpc.net/..

개념 - 병합정렬 처럼 두 부분으로 쪼개어지는 것은 동일하나 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 -..