알고리즘공부

힙 정렬 힙 트리 구조 (Heap Tree Structure)를 이용하는 정렬 방법이다. 힙이 무엇인지 알기 전에 이진 트리(Binary Tree)에 대해 알고 있을 필요가 있다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(node)에 담은 뒤에 노드를 두개 씩 이어 붙이는 구조를 말한다. 이 때 트리 구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗힌다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 구조이다. 위와 같은 구조를 이진트리라 한다. 여기서 트리(Tree)라는 것은 말 그대로 가지를 뻗어나가는 것처럼 데이터가 서로 연결되어있다는 것이다. 완전이진트리(Complete Binarat Tree) 에 대해서도 알아보자. 완전 이진트리는 데이터가 루트(Root) 노드 부터 ..

문제 2022 연세대학교 미래캠퍼스 슬기로운 코딩생활에 N명의 학생들이 응시했다. 이들 중 점수가 가장 높은 k명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라. 커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다. 입력 첫째 줄에는 응시자의 수 N과 상을 받는 사람의 수 k가 공백을 사이에 두고 주어진다. 둘째 줄에는 각 학생의 점수 x가 공백을 사이에 두고 주어진다. 출력 상을 받는 커트라인을 출력하라. 제한 1 ≤ N ≤1000 1 ≤ k ≤ N 0 ≤ x ≤ 10000 예제 입력 1 5 2 100 76 85 93 98 예제 출력 1 98 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을..

지난 시간에는 클래스(Class)를 정의해서 여러 개의 변수가 존재하는 상황에서 '특정한 변수'를 기준으로 정렬하는 방법에 대해 알아봤다. 다만 클래스를 정의하는 방식은 프로그래밍 속도 측면에서 별로 유리하지 않다. 실제 프로그래밍 대회에서 문제 하나를 풀기 위해 클래스를 정의하고 있는 것은 적절치 못하다. 따라서, 일반적으로 프로그래밍 대회와 같이 빠른 개발이 필요할 때는 페어(Pair)라이브러리를 사용하는 것이 효율적이다. #include #include #include using namespace std; int main (void) { vectorv; v.push_back(pair(90, "민지")); v.push_back(pair(85, "해린")); v.push_back(pair(82, "다니..

sort() 함수의 기본 사용법 sort() 함수는 C++의 algorithm 헤더에 포함되어 있다. 기본 사용법은 다음과 같다. #include #include using namespace std; int main(void) { int a[10] = {9, 3, 5, 4 ,1, 10, 8, 6, 7, 2}; sort(a, a + 10); for(int i = 0; i < 10; i++) { cout score < student.score; } }; int main(void) { Student students[] = { Student("민지", 90), Student("해린", 93), Student("다니엘", 91), Student("하니", 85), Student("혜인", 80), }; sort(..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 7 6 5 8 3 5 9 1 병합 정렬 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다. 즉, 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬하는 것이다. 병합 정렬은 퀵 정렬과 다르게 피벗 값이 없고, 항상 반으로 나눈다는 특징이 있다. 바로, 이 특징이 단계의 크기가 logN이 되도록 만들어준다. 7 6 5 8 3 5 9 1 인 모두 크기가 개별 배열로 즉, 크기가 1인 배열 상태로 시작한다. 1단계에서는 각 배열의 크기가 2이고, 크기가 1개 였던 것들을 두 개씩 묶어서 합친 것이다. 1단계에서는 6 7 / 5 8/ 3 5/ 9 1로 나눠진 것을 확인할 수 있다. 2단계에서는 크기가 ..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 1 10 5 8 7 6 4 3 2 9 삽입 정렬 문제를 풀 때 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 '필요할 때만' 위치를 바꾸게 된다. 코드 및 풀이 (with. c언어) #include int main(void) { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for(i = 0; i = 0 && array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j ..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 버블정렬 가까이에 있는 두 숫자끼리 비교해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다. 코드 및 풀이 (with c언어) #include int main(void) { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for (i = 0; i array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } for (i = 0; i < 10;..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 선택정렬 가장 작은 것을 선택해 제일 앞으로 보내는 알고리즘 코드 및 풀이 (with. c언어) #include int main (void) { int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for (i = 0; i array[j]) { min = array[j]; index = j; } } temp = array[i]; array[i] = array[index]; array[index] = temp; } for..