컴퓨터 공학 기초/알고리즘 ( algorithm )
-
Merge Sort (병합 정렬)컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 10. 27. 03:19
병합 정렬이란 ? 병합 정렬 (Merge Sort) 은 정렬 알고리즘 중 하나로 분할 정복 알고리즘을 사용한다. 즉 문제를 작은 2개의 문제로 분리하여 분리 된 각각의 작은 문제를 해결하여 해결한 결과를 가지고 원래의 문제를 해결하는 방식이다. 보통의 분할 정복 방법은 순환 호출 (재귀 함수)를 이용하여 구연하게 된다. 병합 정렬 과정 병합 정렬은 다음과 같은 과정으로 수행 된다. 입력 받은 List를 2개의 List로 나눈다. 이때 나누는 횟수는 나누어진 List가 더이상 나누어 질 수 없을때 까지 반복한다. 더 이상 나누어 질 수 없게 된 경우 2개의 List의 각 요소를 비교하여 (큰값, 작은값) 을 새로운 리스트에 옮긴다. 만약 위의 과정에서 2개의 List 중 하나라도 요소가 모두 옮겨져 요소가..
-
N개의 수에 대한 최대공약수 구하기컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 22. 20:19
유클리드호제법을 이용하여 먼저 0번째와 1번째의 최대공약수를 구한뒤 구한 공약수와 다음 번째 수의 최대공약수를 구하는 방식으로 요소의 마지막 즉 N번째 까지 연산을 수행하게 되면 N개의 숫자의 공통 된 최대공약수를 구할 수 있다. 풀이 // HelloNew_C+.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include "stdafx.h" #include #include #include #include #include int gcd(int a, int b){ int tmp; while (b > 0){ tmp = a; a = b; b = (tmp % a); } return a; } using namespace std; int main(){ int n, s, nData; int res ..
-
팩토리얼 0의 개수 구하기컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 22. 13:08
팩토리얼이란 계승을 의미한다 예를들어 10의 팩토리얼은 1 * 2 * 3 * 4 * 5* 6 * 7 * 8 * 9 * 10 을 의미한다. 현재 구하고 싶은 값은 10 팩토리얼에서 나오는 연속된 0의 갯수이다. 예를들어 10팩토리얼의 값 3628800 이있다면 여기서 가장 뒤의 연속된 0 의 개수를 구하는 것이다. 뒤 자리가 0이 나오기 위해서는 값에 10이 더해지는 수 밖에 없다. 따라서 2 * 5 가 몇번나왔는지만 확인하면 된다. 해결을 하기 위해서는 2가지 방법이 있다. 1. 3628800 을 소인수 분해 하여 총 5가 몇개나오는지 확인하는 방법이 있다. 2. 10의 값을 5로 나누고 몫의 값을 파악하는 방법 + 25 * 1, 25 * 2 와 같이 5 * 5 가 두번 나올 경우를 파악 // Hello..
-
최대공약수 (유클리드호제법) 최소공배수컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 21. 12:42
최대공약수란 ? 어떤 수 A 와 B가 있을 때 A 와 B 서로의 약수에서 공통된 수들 중 가장 큰 수를 의미한다. 가장 간단하게 구할 수 있는 방법은 A와 B중 작은 값을 구하여 2부터 작은 값 까지 순회하면서 A와 B의 나머지 연산을 통해 구하는 방법이 있다. 해당 방법은 시간복잡도 o(N) 이라는 시간복잡도를 가지고 있으며 해당 방법보다 빠른 유클리드 호제법이라는 알고리즘이 존재한다. 유클리드호제법의 로직은 다음과 같다. int gcd(int a, int b){ if (b == 0){ return a; } else { return gcd(b, (a%b)); } } int main(){ int aNum, bNum; cin >> aNum; cin >> bNum; cout (16, (24 % 16)) ->..
-
Stack 을 이용한 알고리즘컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 13. 13:20
이번 포스트에서는 스텍 자료구조를 활용하여 문제를 해결한다. 스텍의 특성은 선입후출의 특성을 가지고 있다. 문제 1. 스텍 구현 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 해결 // Data_struct_c+.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include #include #include using namespace std; class STACK{ // ..