분류 전체보기
-
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..
-
퀵 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 14. 12:29
퀵 정렬 가장 끝 원소를 기준으로 그보다 작은 원소를 왼쪽에 큰 원소를 오른쪽으로 옮겨 정렬한다. 퀵 정렬 알고리즘 끝 원소를 기준으로 작은 원소를 좌측에 큰 원소를 우측으로 옮기고 좌측 배열과 우측 배열에 대해 같은 과정을 반복한다. 퀵 정렬 알고리즘 QuickSort(A[], p, r) { if (p < r) then { q ← Partition(A, p, r) QuickSort(A, p, q - 1) QuickSort(A, q + 1, r) } } Partition(A[], q, r) { 배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 리턴한다. } ※ 퀵 정렬의 시간 복잡도는 모든 원소들이 한쪽으로 몰리는 최악의 경우 Ο(n²), 평균적으로 Ο(nl..
-
JUNGOL...92일지 2021. 7. 13. 15:21
Beginner_Coder/재귀/주사위 던지기1 문제 주사위를 던진 횟수 N과 출력형식 M을 입력 받아서 M의 값에 따라 각각 아래와 같이 출력하는 프로그램을 작성하시오. M = 1 : 주사위를 N번 던져서 나올 수 있는 모든 경우 M = 2 : 주사위를 N번 던져서 중복이 되는 경우를 제외하고 나올 수 있는 모든 경우 M = 3 : 주사위를 N번 던져서 모두 다른 수가 나올 수 있는 모든 경우 * 중복의 예 1 1 2 와 중복 : 1 2 1, 2 1 1 1 2 3 과 중복 : 1 3 2, 2 1 3, 2 3 1, 3 1 2 입력 형식 첫 줄에 주사위를 던진 횟수 N(2≤N≤5)과 출력모양 M(1≤M≤3)이 들어온다. 출력 형식 주사위를 던진 횟수 N에 대한 출력모양을 출력한다. 작은 숫자부터 출력한다..
-
알고리즘...19일지 2021. 7. 13. 14:14
퀵 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. QuickSort.hpp #pragma once #include "../Common.hpp" void QuickSort(int arr[], int p, int r, bool printData = false, int n = 0); int Partition(int arr[], int p, int r); /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void QuickSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } QuickSort(ar..
-
JUNGOL...91일지 2021. 7. 12. 12:09
Beginner_Coder/재귀/하노이1 문제 하노이의 탑에 대한 전설은 아래와 같다. 고대 인도의 베나레스(현재 베트남의 하노이)에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 기둥이 동판 위에 세워져 있다. 기둥 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓여 있다. 이것은 신성한 브라흐마의 탑이다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 기둥으로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮긴다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 된다. 기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2,..
-
알고리즘...18일지 2021. 7. 12. 12:05
퀵 정렬 가장 끝 원소를 기준으로 그보다 작은 원소를 왼쪽에 큰 원소를 오른쪽으로 옮겨 정렬한다. 퀵 정렬 알고리즘 끝 원소를 기준으로 작은 원소를 좌측에 큰 원소를 우측으로 옮기고 좌측 배열과 우측 배열에 대해 같은 과정을 반복한다. 퀵 정렬 알고리즘 QuickSort(A[], p, r) { if (p < r) then { q ← Partition(A, p, r) QuickSort(A, p, q - 1) QuickSort(A, q + 1, r) } } Partition(A[], q, r) { 배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 리턴한다. } 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
JUNGOL...90일지 2021. 7. 11. 12:27
Beginner_Coder/재귀/팩토리얼 문제 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다. 0! = 1 1! = 1 2! = 2 n! = n * (n-1)! ： 와 같이 정의된다. 예로 4! = 4×3×2×1 = 24 이다. n! 이 주어졌을 때 결과를 출력하는 프로그램을 작성하라. * 결과가 int범위를 넘는 경우 자료형 long long 입력/출력 서식문자 %lld 를 사용한다. 입력 형식 입력은 한 줄로 이뤄지며 팩토리얼의 숫자 n(1≤n≤15)이 입력된다. 출력 형식 n!에 대한 계산 결과를 "출력예"처럼 과정을 출력하고 마지막에 결과를 출력한다. 입력 예 4 출력 예 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 24 Factor..
-
JUNGOL...89일지 2021. 7. 10. 12:15
Beginner_Coder/자료처리/쇠막대기 문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. - 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. - 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다. 이러한..