일지
-
JUNGOL...97일지 2021. 7. 19. 14:29
Beginner_Coder/재귀/다음 조합(next combination) 문제 1부터 N까지의 N개의 정수 중에서 K개를 뽑아낼 때 가능한 경우들을 조합이라고 한다. 예를 들어 N=5고 K=3일 경우 가능한 모든 조합은 다음과 같다 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 [ 1 2 3 ] 과 [ 3 1 2 ] 와 같이 순서는 다르나 뽑힌수가 같은 경우는 한가지로 간주한다. 다시 말해서 뽑힌 순서는 고려하지 않는다는 것이다. N과 K가 입력되고 N과 K에서 가능한 조합 중 하나가 입력될 경우, 조합들을 오름차순으로 정렬 했을 때 다음으로 나오는 조합을 출력하는 프로그램을 작성하라. 입력 형식 입력의 첫번째 줄에는 N과 K가 입력된다(5≤..
-
알고리즘...22일지 2021. 7. 19. 14:23
특수 정렬 알고리즘 두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다. 기수 정렬 입력이 모두 k 이하의 자리수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 기수 정렬 알고리즘 RadixSort(A[], n, k) { for i ← 1 to k { i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다. } } ※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
JUNGOL...96일지 2021. 7. 18. 11:28
Beginner_Coder/재귀/로또(Lotto) 문제 로또에서는 {1, 2, 3, ... , 48, 49} 번호 중에 6개를 선택해야 한다. 로또 번호를 선택하는 데는 여러 가지 전략이 있겠지만 우리는 49개의 수 중에서 K( 6 < K < 13)개가 이미 선택되어 있다고 가정하고 이 선택된 수들로 만들 수 있는 로또 번호를 만들어 보기로 한다. 예를 들어 K = 8이고 선택된 수들의 집합 S = {1,2,3,5,8,13,21,34} 라고 할 때, 가능한 로또 번호는 [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34]. 로 28개가 있다. 수의 개수 K와 K개의 수가 주어질 때 가능한 로또 번호를 출력..
-
JUNGOL...95일지 2021. 7. 16. 13:56
Beginner_Coder/재귀/장난감조립 문제 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다. 예를 들어보자. 기본 부품으로서 1, 2, 3, 4가 있다. 중간 부품 5는 2개의 기본 부품 1과 2개의 기본 부품 2로 만들어진다. 그리고 중간 부품 6은 2개의 중간 부품 5, 3개의 기본 부품 3과 4개의 기본 부품 4로 만들어진다. 마지막으로 장난감 완제품 7은 2개의 중간 부품 5, 3개의 중간 부품 6과 5개의 기본 부품 4로 만들어진다. 이런 경우에 장..
-
알고리즘...21일지 2021. 7. 16. 13:49
힙 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. HeapSort.hpp #pragma once #include "../Common.hpp" void BuildHeap(int arr[], int n); void Heapify(int arr[], int k, int n); /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void HeapSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } BuildHeap(arr, n); for (int i = n - 1; i > 0; i--) { Comm..
-
JUNGOL...94일지 2021. 7. 15. 14:08
Beginner_Coder/재귀/숫자고르기 문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이 때 집합의 크기는 3이다. 만..
-
알고리즘...20일지 2021. 7. 15. 14:03
힙 정렬 루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다. 힙 만들기 입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다. 힙 생성 알고리즘 BuildHeap(A[], n) { for i ← └n / 2┘ downto 1 { Heapify(A, i, n); } } Heapfipy(A[], k, n) { left ← 2k; right ← 2k + 1; // 작은 자식 고르기 if (right ≤ n) then { if (A[left] < A[right]) then { smaller ← left; } else { smaller ← right; } } // 왼쪽 자식만 있는 경우 else if (left ≤ n) then { smaller ← left; } //..
-
JUNGOL...93일지 2021. 7. 14. 13:30
Beginner_Coder/재귀/주사위 던지기2 문제 자연수 N과 M을 입력 받아서 주사위를 N번 던져서 나온 눈의 합이 M이 나올 수 있는 모든 경우를 출력하는 프로그램을 작성하시오. 입력 형식 첫 줄에 주사위를 던진 횟수 N(2≤N≤7)과 눈의 합 M(1≤M≤40)이 들어온다. 출력 형식 주사위를 던진 횟수의 합이 M이 되는 경우를 모두 출력한다. 작은 숫자 부터 출력한다. 입력 예 3 10 출력 예 1 3 6 1 4 5 1 5 4 1 6 3 2 2 6 2 3 5 … 6 2 2 6 3 1 RollDice2.h #include class RollDice2 : public Base { private: void AllNumbersSameTotal(int arr[], int n, int m, int dept..