본문 바로가기

대학교

2.1 Recursion에 대한 이해 앞선 내용에서는 Maximum Range Sum을 구하는 함수를 구현하고 거기에서 중복되는 연산부분을 없애는 방식으로 수행 속도를 향상시켰다. 이것을 하는데 있어서는 아무런 사전 지식이 없어도 생각을 해본다면 Live하게 짤 수 있는 알고리즘이었다.이번에는 Recursion이 무엇인지에 대해 살펴보도록 하겠다.Recursion을 한국말로 번역을 하자면 '반복'이라는 뜻을 가지고 있다. 즉 Recursive function은 같은 함수가 반복..
실습 2주차 [3] Coin Combination 문제 여러 종류의 동전이 있어서 그 동전들을 이용해서 특정한 금액을 만드려고 한다. 처음에 coin 종류의 개수를 입력 받고, 그 다음에는 각 동전마다의 액면가를 입력 받으며, 마지막으로 원하는 가격을 입력한다. 출력해야 할 값은 그 가격을 만들 수 있는 동전의 조합의 개수이다. 여기서 동전의 종류의 개수는 최대 10개까지만 입력한다고 가정하자. 입력 형식{동전 종류 수} 동전1 동전2 동전3 ... 동전n {원하는 가격} Hint : Recu..
1.2 Maximum Range Sum (2) 앞에서 사용한 알고리즘의 Time Complexity는 $O(n^3)$이었다. 이것을 줄이기 위해서는 불필요한 연산을 줄이는 것이 가장 먼저 할 수 있는 방법이다. 일단 앞의 알고리즘을 이용해서 작성한 소스코드를 다시 살펴보도록 하자. int getMaximumRange1(int *arr, int size){ int max = INT_MIN; for(int i=0; i<size; i++){ for(int j=i; j<size; j..
1.1 Maximum Range Sum (1) Maximum Range Sum이란 길이가 n인 배열을 받아서 구간을 잡아 그 구간에 있는 모든 배열 값을 더해서 그 값이 최대가 되도록 하는 값을 찾도록 하는 문제이다.그냥 바로 생각하면 배열의 모든 값을 더하면 최댓값이 될 수 있다고 생각할 수도 있지만, 이렇게 하려면 배열의 모든 값이 양수라는 조건이 있어야 한다. 즉, 임의의 숫자에 대해서는 이렇게 생각할 수 없다는 것이다.그러면 이 문제를 어떻게 하면 해결 할 수 있을까? 가장 간단한 방법은..
실습 2주차 [2] Binary Search 문제10^6개 만큼의 서로 다른 unsigned integer가 정렬된 형태로 input에 들어오고, 다음으로는 10^4개 만큼의 서로 다른 unsigned integer가 들어온다.이 때 처음의 10^6개의 데이터는 배열에 들어가며, 그 다음 input인 10^4개의 데이터에 대해서 binary search를 이용해서 해당하는 인덱스를 반환해서 각각 출력하게 한다.만약 해당하는 값이 없는 경우에는 -1을 반환한다.입력 형식숫자1 숫자2 ... 숫자..
실습 2주차 [1] Greatest Common Divisor 문제 최대 공약수(Greatest Common Divisor)를 Recursive code로 구현하여 100개의 쌍에 대해서 최대 공약수를 출력하도록 한다. 입력의 경우 음이 아닌 정수가 입력되며 N과 0의 최대 공약수는 N을 출력하도록 한다. 입력 형식숫자1 숫자2 숫자3 숫자4 ... 숫자199 숫자200 출력 형식 : 입력된 두 쌍의 숫자에 대해서 각각 최대공약수를 구해서 각 줄마다 출력을 하도록 한다. 답안 #includ..
실습 1주차 [2] Insertion Sort 문제Insertion sort를 이용해서 주어진 정수들을 오름차순으로 정렬해서 출력한다. 단, 숫자의 개수가 10,000개를 넘지 않는다.입력 형식(숫자 개수)숫자1 숫자2 ... 숫자N출력 형식 : 주어진 N개의 숫자를 공백으로 구분하여 오름차순으로 출력 한다.Ex)입력54 7 3 10 1출력1 3 4 7 10답안#include <iostream> using namespace std; #define MAX_LEN 10000 void..
실습 1주차 [1] Bubble Sort 문제Bubble sort를 이용해서 주어진 정수들을 오름차순으로 정렬해서 출력한다. 단, 숫자의 개수가 10,000개를 넘지 않는다.입력 형식(숫자 개수)숫자1 숫자2 ... 숫자N출력 형식 : 주어진 N개의 숫자를 공백으로 구분하여 오름차순으로 출력 한다.Ex)입력54 7 3 10 1출력1 3 4 7 10답안#include <iostream> using namespace std; #define MAX_LEN 10000 void bu..