C 자료구조
-
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. 구현 프로그램 실행결과
-
Graph - Topological SortC 자료구조/Graph 2020. 7. 14. 00:17
내용 1. 개념 아래와 같은 그래프가 있다고 하자. 위와 같은 방향 그래프에서 간선가 있다면 정점u는 정점v를 선행한다고 한다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬이라 한다. 위의 그림에서 많은 위상 정렬이 가능한데, 몇 개만 예를 들어보자. A,B,C,D,E,F B,A,C,D,E,F 가 있다. 그러나, C,A,B,D,E,F는 위상 순서가 아니다. 위가 위상 순서가 아닌 이유는 간선가 존재하기 때문에 A번 정점이 끝나야만 C번 정점을 시작할 수 있기 때문이다. 2. Topological Sort 알고리즘 방향 그래프를 대상으로 위상 정렬을 하기 위한 알고리즘은 간단하다. 먼저 진입 차수가 0인 정점을 선택하고, 선택된 정점..