INFO C++ STL 라이브러리의 algorithm 헤더는 sort 정렬 함수를 제공합니다. sort 정렬 함수는 intro sort 정렬 알고리즘을 이용하는데 이는 quick sort 정렬 알고리즘을 기반으로 한 heap sort 와 insertion sort 를 혼합해 만든 알고리즘으로 최악의 경우에 n^2의 시간 복잡도를 가지는 quick sort의 단점을 보완하여 최악의 경우에도 nlogn의 시간 복잡도를 가지는 정렬 알고리즘 입니다. PS에서 빈번하게 사용되는 함수이기에, 한 번 숙지해 두면 알고리즘 풀이에 큰 도움이 될 것 입니다. #1 오름차순 정렬 - 1.1 벡터 오름차순 정렬 예제 - 1.2 배열 오름차순 정렬 예제 #2 내림차순 정렬 - 2.1 벡터 내림차순 정렬 예제 - 2.2 배열..
#문제정보 출처 : www.acmicpc.net/problem/1744 난이도 : 골드4 분류 : 그리디(GREEDY) 알고리즘 #문제분석 입력받은 수들을 양수,음수,0 으로 각각 다른 벡터에 저장해서 풀이했습니다. vector pos; // 양수 벡터 vector neg; // 음수 벡터 vector zero; // 0 저장 벡터 vector res; // 출력 값 CASE1 : 양수벡터 양수가 홀수개인 경우 : 가장 작은 값을 결과값에 더합니다. 양수가 짝수개인 경우 : 양수벡터를 오름차 정렬한 후 , 뒤에서 부터 2개씩 묶어 곱한 뒤 결과값에 더합니다. (내림차 정렬한 후 앞에서 부터 2개씩 곱해도 상관은 없습니다.) // positive int pSize = pos.size(); if (pSize..
#문제정보 출처 : www.acmicpc.net/problem/15903 #문제분석 알고리즘 분류 : 그리디(GREEDY) 그냥 충실히 더해주기만 하면 되는 간단한 그리디 문제이다. while (m--) { sort(card.begin(), card.end()); temp = card[0] + card[1]; card[0] = card[1] = temp; } 입력받은 m(합체 횟수) 만큼 반복을 돌려서 , sort로 오름차 정렬을 해준 뒤 문제에서 제시한 조건에 맞게 더한다. 자료형만 조심하면 딱히 어려운 부분은 없는 문제였다. #소스코드 #include #include #include using namespace std; typedef long long ll; ll result; int main() {..
#1 Queue Container 구조 & 특징 #2 멤버함수 #3 사용방법 #4 관련예제 INFO Queue [큐] 컨테이너는 C++ STL 표준 라이브러리가 제공하는 컨테이너 어댑터로 사용자가 따로 구현하지 않고 편리하게 사용할 수 있도록 하는 자료구조 입니다. Queue [큐] 자료구조의 특징과 구조에 대해서는 Computer Basic - DataStructure 카테고리에 정리해 두었으니, 혹시 큐에 대한 개념이 없다면 다음 게시글을 참고해 주세요. About Queue #1 Queue Container 구조 & 특징 ● FIFO[First in , First Out] 방식으로 동작합니다. ● deque, list 컨테이너에 붙여서 사용 가능한 컨테이너 어댑터입니다. (vector 컨테이너와는 ..
#1 Queue 정의 & 구조 #2 Queue 구현 with C/C++ * 큐 자료구조의 간략한 정의와 구조, 그리고 C언어를 이용해 구현한 내용을 정리해 보았습니다. 개인적인 공부 기록용으로 작성한 글이기에 잘못된 내용이 있을 수 있으며, 지속적으로 수정해 나갈 예정입니다. #1 Queue 정의 & 구조 Queue란, 한쪽에서 원소를 넣고 반대쪽에서 원소를 뺄 수 있는 자료구조이다. 먼저들어간 원소가 먼저 나오는 구조이기에 FIFO(First In First Out) 라고 하며, 은행의 대기번호를 생각하면 쉽게 이해가 가능하다.원소의 추가/제거 의 시간 복잡도는 O(1)이며, 맨 앞/뒤의 원소 확인의 시간 복잡도 또한 O(1)이다.배열을 이용해 구현 하는 경우 중간의 원소들을 확인하는 것이 가능하지만,..