공부 기록 일지/Algorithm

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

지난 시간에는 클래스(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 퀵 정렬 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 퀵정렬에서는 기준값 (=피벗(Pivot))이 있는데, 보통 첫 번째 원소를 피벗 값으로 설정하고 사용한다. 다음과 같이 1이라는 값이 먼저 피벗 값으로 설정되었다고 생각해보자. (1) 10 5 8 7 6 4 3 2 9 이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾는다. 이 때 1보다 큰 숫자로는 바로 10을 찾을 수 있고, 1보다 작은 숫자는 찾지 못해서 결국 1까지 도달한다. 이 때 작은 값의 인덱스가 큰 값의..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 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..