백준 2751 수 정렬하기2 문제는 시간복잡도와 관계가 있는 문제이다. 일반적인 버블 정렬과 삽입 정렬로는 처리 시간이 오래 걸리기 때문에 좀 더 빠른 알고리즘으로 처리해야한다. 그 중에 대표적으로 Heap 정렬이 있다. 아래 코드는 Heap 정렬 코드다. #include #include #include void push_heap(std::vector& heap, int Value) { heap.push_back(Value); int index = heap.size() - 1; while (index > 0 && heap[(index - 1) / 2] < heap[index]) { std::swap(heap[index], heap[(index - 1) / 2]); index = (index - 1) / ..
전체 글
백준 2750 수 정렬하기 문제는 시간복잡도는 상관 없이 정렬만 되면 해결 할 수 있는 문제다. 정렬에는 대표적으로 버블 정렬과 삽입 정렬이 있다. 아래는 각 정렬 방식에 대한 코드이다. 버블 정렬(Bubble Sort) #include #include using namespace std; void InsertionSort(int *arr, int length) { int key; for (int i = 1; i key) { memmove(&arr[j + 1], &arr[j], sizeof(int) * (i - j)); arr[j..
백준 10818 문제는 N 개의 정수가 주어지면 최솟값과 최대값을 구하는 정말 간단한 문제이다. 근데 난 이 문제를 여러 번 틀렸는데, 이유는 문제에서 주어진 범위가 -1000000부터 1000000까지였다는 점을 주의하지 않았기 때문이다. 알고리즘은 정말 간단한 문제고, 쉽게 풀었지만 코딩 테스트에서는 정수의 범위를 간과하면 안된다것을 알아야한다. #include using namespace std; int main() { int N; cin >> N; int *arr = new int[N]; int min = 1000000; int max = -1000000; for (int i = 0; i > arr[i]; if (arr[i] < min) min = arr[i]; if..
분해합 문제는 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하는 문제이다. 최소의 문제를 구하는 문제이기 때문에 정수 1부터 시작해서 생성자를 구해서 최초의 생성자가 나오면 종료하면 된다. #include using namespace std; int main() { int N; cin >> N;..