이누의 개발성장기

자릿수의 합 비교하기 자연수 n을 받고, n개의 자연수를 받는다. 각 자연수의 각 자릿수를 모두 더한 값(자릿수의 합)을 비교하여 그 값이 가장 큰 자연수를 출력한다. 자릿수의 합이 같을 경우 더 큰 수를 출력한다. 예를들어 5를 n으로 입력하고, 125 15232 79 1325 97를 입력하면 97이 출력된다. 풀이 #include int digit_sum(int x) { int tmp,sum = 0; while (x>0) { tmp = x % 10; sum += tmp; x = x / 10; } return sum; } int main() { //freopen("input.txt", "rt", stdin); int n, num, i, sum, max=-2147000000, res; scanf("%d"..

N까지의 약수 갯수 모두 구하기 N을 입력받고 1~N까지의 약수를 하나씩 출력한다. 예를 들어, 8을 입력하면 1의 약수 개수 ~ 8의 약수 개수를 하나씩 출력하여, 1 2 2 3 2 4 2 4 와 같이 출력된다. 풀이 (단순 접근) #include int main() { //freopen("input.txt", "rt", stdin); int n, i, j, num = 0; scanf("%d", &n); for(i=1; i

영어단어 복구 알고리즘 특정 단어를 대소문자 구문없이 중간중간 공백을 포함하여 한줄로 입력하면, 그를 소문자의 이어진 문자로 복구해주는 알고리즘이다. 예를 들어, 'bE au T I fu L'과 같이 입력하면 이를 'beautiful'로 바꾸어 출력해준다. 풀이 #include int main(){ //freopen("input.txt", "rt", stdin); char a[101], b[101]; int i, p=0; gets(a); for(i=0; a[i]!='\0'; i++){ if(a[i]!=' '){ if(a[i]>=65 && a[i]

특정 리스트를 정렬하는 방법에는 여러 가지가 있다. 그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다. 그 중 합병 정렬에 대해 알아보자. 합병 정렬은 병합 정렬이라고도 불린다. 정렬된 두 리스트의 합 정렬 먼저 알아야 할 것이 있다. 합병 정렬은 정렬된 임의의 두 리스트가 있을 때, 두 리스트를 합치면서 정렬하기 위해서는 두 리스트의 성분을 처음부터 하나씩 비교해면서 새로운 리스트에 넣어주다가 둘 중 어느 한 리스트의 성분 모두 없어지면, 나머지는 그냥 새로운 리스트의 뒤에 들어가면 된다. ex. [1,2,3,5] [4,6,7,8]이 있을 때 이를 합치면서 정렬하려 한다. 처음부터 성분을 비교하면서 넣다 보면 어느 순간 새로운 리스트에 [1,2,3,4,5]까지 ..

비트연산자를 활용하여 부분집합 만들기 n이 어떤 집합의 원소 갯수라고 하자. - 특정 부분집합에 대한 특정 원소의 포함여부는 각 원소마다 2가지 경우를 가진다. (들어간다 or 들어가지 않는다.) - 이를 원소의 갯수만큼 반복하여 생각하면, 모든 부분집합의 경우의 수를 알 수 있다. - 즉, 어떤 집합의 부분집합은 2의 n승 만큼 존재한다고 할 수 있다. 이를 활용하여 특정 집합의 부분집합들을 찾을 수 있다. - 우선 부분집합의 개수를 비트 형태로 생각해보자. 배열 arr이 6개의 원소를 가진다면, - 000000~111111의 숫자로 대변할 수 있는 부분집합들을 가질 것이다. (2의 n승개) 이를 기반으로 각 부분집합을 한줄씩 출력해주는 코드를 작성해보았다. 1 2 3 4 5 6 7 8 9 arr = ..

완전검색 (Brute force) 완전검색은 Brute force라고 불리는 만큼 매우 무식한 알고리즘 기법이다. 가능한 경우의 수를 전부 확인하고 답을 그 중에서 답을 찾아내는 것이다. 어떤 리스트에서 숫자 100을 찾을 때 해당 리스트를 전부 돌면서 숫자 100과 일치하는 값을 찾는 것이 그 예시이다. 사실 나는 이것을 알고리즘이라 불러도 되는지도 잘 모르겠다. 하지만 오류없이 답을 확실하게 찾아낼 수 있고, 가능한 경우의 수가 적을 때는 상당히 유용하게 사용된다고 한다. 자격 검정 시험 등에서도 우선 완전검색 방법으로 답을 도출해낸 다음, 성능 개선을 위해 다른 알고리즘을 도입하는 것이 바람직하다고 할 수 있겠다.

Greedy Algorithm Greedy Algorithm은 말그대로 탐욕적인 알고리즘이다. 목표를 이루기 위해 큰 그림을 바라보지 않고, 현재 가장 좋아보이는 것으로 이동해나간다. 예를 들어, 더 높은 산을 가기위한 알고리즘을 구현한다고 할때 A산은 현재 30도의 경사를 보이고, B산은 현재 40도의 경사를 보인다고 하자. B산이 현재 경사가 더 높다고 해서 더 높은 산이 되는 것은 아닐 것이다. 하지만 Greedy Algorithm은 해당 정보를 기반으로 B산을 선택하고 올라간다. 이렇듯, Greedy Algorithm은 완벽한 결과를 보장해주지는 않는다. 하지만 간혹 Greedy Algorithm이 완벽한 결과를 도출해내는 경우도 있고, 속도가 매우 빨라 다른 느린 알고리즘을 대신하여 많이 사용된..

다이나믹 프로그래밍 다이나믹 프로그래밍이란 어떤 문제를 해결하는 것에 있어, 중복적인 계산을 최대한 피하는 방법이다. (2*5) + (2*6)의 문제를 해결할 때를 생각해보자. (2*5)만 알면 (2*6)은 (2*5 + 2)로 해결할 수 있다. 따로 (2*5)를 또 계산할 필요가 없이 미리 해결한 (2*5)의 결과값을 이용한 것이다. 이것이 다이나믹 프로그램의 핵심이다. 문제가 더더욱 복잡하고 중복되는 계산이 많은 상황에서는 여러 계산과정을 생략할 수 있어 유용할 것이다. 좀 더 자세히 살펴보자. 다이내믹 프로그래밍의 조건 1. 최적 부분 구조 : 부분 문제의 최적의 답을 통해 상위문제(기존문제)의 최적의 답을 구할 수 있다. ex. 피보나치 수, fib(n) = fib(n -1) + fib(n - 2)..

특정 리스트를 정렬하는 방법에는 여러 가지가 있다. 그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다. 그 중 퀵정렬에 대해 알아보자 퀵 정렬 합병 정렬의 combine단계에서는 크기를 비교해가며 새로운 리스트를 생성했다. 즉, 합병 정렬은 combine단계에서 많은 과정을 수행한다. 하지만 퀵 정렬은 이와 다르게 divide에서 많은 과정을 수행한다. 퀵 정렬의 과정 퀵 정렬은 주로 기준점으로 삼을 임의의 성분을 필요로 한다. 주로 대상 리스트의 제일 마지막 성분을 사용한다. 이를 pivot이라고 부른다. 이 pivot을 기준으로 더 작은 성분은 모두 왼쪽으로, 더 큰 성분은 모두 오른쪽으로 이동한다. (divide) 그리고 왼쪽의 리스트와 오른쪽의 리스트를 각..

분할정복 (Divide and Conquer) 이는 재귀함수에 대한 명확한 이해가 필요한 파트이다. 재귀함수가 부족하다고 생각하면 좀 더 공부를 해놓고 학습을 하는 것이 좋겠다. 분할정복은 이름 그대로 문제를 분할하여 해결하는 것이다. 이는 총 3단계로 구성된다. 1. Divide : 문제를 나눈다. 2. Conquer : 나눠진 문제를 각각 해결한다. 3. Combine : 각각 해결한 두 문제의 답을 결합한다. 여기서 생각해야 될 것은 분명 우리는 어떤 문제를 해결하기 위해 분할정복을 시작했다. 그런데 여기서 2번단계를 보면 '나눠진 문제를 각각 해결한다' 라고 한다. 이 말은 결국 무엇이겠는가? 이 2번 단계에서 나눠진 문제에도 각각 분할정복을 적용할 수 있다는 뜻이다. 그리고 당연하게도 그렇게 2..