C 자료구조/1. 재귀함수
-
문자열 순열로 출력하기C 자료구조/1. 재귀함수 2020. 7. 30. 17:33
먼저, 아래의 문제를 해결하기 전에 아래의 글을 보는 것이 도움이 될 수 있다. designatedroom87.tistory.com/45?category=868275 문자열 중복순열로 출력하기 1. 입/출력 문자열을 입력 받으면, 중복 순열을 출력하도록 만들어 보자. 아래는 입력에 따른 출력이다. 입력 ab 출력 aa ab ba bb 2. 아이디어 아래는 문자열 AB로 나타낼 수 있는 중복순열을 트리로 � designatedroom87.tistory.com 1. 개념 앞의 문자열 중복순열 출력하는 부분에서 중복을 제거하면 순열이 된다. 이는 기록(memoization)을 통해 이를 해결 할 수 있다. 2. 구현 프로그램 실행결과 3. 소스 파일 위의 문제를 해결했으면 Anagram에 대한 문제도 보도록 ..
-
문자열 중복순열로 출력하기C 자료구조/1. 재귀함수 2020. 7. 30. 17:33
1. 입/출력 문자열을 입력 받으면, 중복 순열을 출력하도록 만들어 보자. 아래는 입력에 따른 출력이다. 입력 ab 출력 aa ab ba bb 2. 아이디어 아래는 문자열 AB로 나타낼 수 있는 중복순열을 트리로 나타낸 것이다. 3. 구현 프로그램 실행결과 4. 소스 파일 위의 내용을 이해했으면, 중복을 제외한 순열을 출력해보자. designatedroom87.tistory.com/46?category=868275 문자열 순열로 출력하기 먼저, 아래의 문제를 해결하기 전에 아래의 글을 보는 것이 도움이 될 수 있다. designatedroom87.tistory.com/45?category=868275 문자열 중복순열로 출력하기 1. 입/출력 문자열을 입력 받으면, 중복 순열을 �� designatedro..
-
Fibonacci Sequence - 행렬을 이용한 분할 정복 방법 advancedC 자료구조/1. 재귀함수 2020. 7. 29. 17:36
1. 개념 designatedroom87.tistory.com/41?category=868275 Fibonacci sequence - 행렬을 이용한 분할 정복 방법 basic 1. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피보나치 수열의 점화식이다. 2. 구현 구현에 앞서서, 각 행렬들을 구조체로 정의하고, 행렬들 간의 곱셈을 하는 함수들을 만들어보�� designatedroom87.tistory.com 앞에서 피보나치 수열을 구할 때, 행렬의 연산을 통해 했는데, 좀 더 빠른 연산을 수행할 수 있도록 변경해보자. 기본적인 아이디어는 거듭 제곱에 쓰인 방식과 같다. 2. 구현 기존에 만든 FiboMatPower 함수만 수정하면 된다. 이 함수의 역할은 FiboMat행렬의 n제곱을 구하는..
-
Fibonacci sequence - 행렬을 이용한 분할 정복 방법 basicC 자료구조/1. 재귀함수 2020. 7. 28. 19:28
1. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피보나치 수열의 점화식이다. 2. 구현 구현에 앞서서, 각 행렬들을 구조체로 정의하고, 행렬들 간의 곱셈을 하는 함수들을 만들어보자. 프로그램 실행결과 3. 헤더 파일 & 소스 파일 위의 내용을 이해했으면 아래로 가보자. designatedroom87.tistory.com/49 Fibonacci Sequence - 행렬을 이용한 분할 정복 방법 advanced 1. 개념 designatedroom87.tistory.com/41?category=868275 Fibonacci sequence - 행렬을 이용한 분할 정복 방법 basic 1. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피..
-
거듭 제곱 구하기 - 분할 정복 방법C 자료구조/1. 재귀함수 2020. 7. 28. 18:59
아래의 내용을 먼저 보고 오는 것도 좋다. designatedroom87.tistory.com/47?category=868275 거듭 제곱 구하기 - basic 1. 개념 거듭 제곱은 아래와 같은 점화식으로 표현된다. 우리가 위의 C^n을 구하기 위해서는 C^(n-1)을 구하면 된다. 2. 구현 프로그램 실행결과 3. 소스 파일 위의 내용을 이해했으면 분할 정복 방법 designatedroom87.tistory.com 1. 설명 위의 점화식에서, n이 홀수일 때의 []기호는 가우스 기호이다. 위의 식에 n을 8이라고 두면 위의 식에서, n = 8일 때의 값을 구하려면, C의 제곱을 먼저 구한 뒤에 두 번 더 반복해서 제곱을 하면 된다. 결국, 3번의 곱셈을 하면 된다. n이 만약에 홀수라면 (예를 들어 ..
-
거듭 제곱 구하기 - basicC 자료구조/1. 재귀함수 2020. 7. 28. 18:56
1. 개념 거듭 제곱은 아래와 같은 점화식으로 표현된다. 우리가 위의 C^n을 구하기 위해서는 C^(n-1)을 구하면 된다. 2. 구현 프로그램 실행결과 3. 소스 파일 위의 내용을 이해했으면 분할 정복 방법에 대해 알아보자. designatedroom87.tistory.com/48?category=868275 거듭 제곱 구하기 - 분할 정복 방법 1. 설명 위의 점화식에서, n이 홀수일 때의 []기호는 가우스 기호이다. 위의 식에 n을 8이라고 두면 위의 식에서, n = 8일 때의 값을 구하려면, C의 제곱을 먼저 구한 뒤에 두 번 더 반복해서 제곱을 � designatedroom87.tistory.com
-
배열에서 최대값 찾기C 자료구조/1. 재귀함수 2020. 7. 16. 23:26
1. 개념 배열에서 최대값을 찾는 문제는 반복문을 이용해서 쉽게 구할 수도 있지만, 재귀함수를 통해 구할 수 있다. 배열의 길이를 5라고 하면, 0번 인덱스에서 4번 인덱스까지의 범위에서 최대값을 찾는 문제라고 한다면 1번 인덱스에서 4번 인덱스까지의 범위에서 최대값을 구했다고 가정하면 0번 인덱스와 비교를 통해 최대값을 구하면 된다. 위 그림에서, 배열의 길이가 5칸이라고 가정하고 보도록하자. 파란색 숫자는 재귀함수의 호출 순서이다. fromIndex는 위의 노란색 화살표이다. fromIndex가 배열의 맨 마지막 인덱스이면, 맨 마지막 인덱스를 리턴한다. 그러면서, 현재의 인덱스와 그 이전의 인덱스를 서로 비교해서 큰 값을 갖는 인덱스를 리턴하면 된다. 2. 구현 프로그램 실행결과