재귀
-
N 개의 계단Algorithm with C/DFS 2020. 9. 16. 18:58
문제 N 개의 계단을 사람이 오른다고 하자. 한 번에 1계단 오르기도 하고, 2계단이나 3계단씩 오르기도 한다. 계단을 오르는데 몇 가지 방법이 있는가? 문제 분석 N 번째 계단에 도달하는 방법을 생각해보자. N - 1 번째 계단에서 한 계단 더 올라 N 번째 계단에 도달했을 수도 있고, N - 2 번째 계단에서 두 계단을 뛰어 N 번째 계단에 도달했을 수도 있고, N - 3 번째 계단에서 세 계단을 한 번에 뛰어 N 번째 계단에 도달했을 수도 있다. 그러므로, 마지막 계단에 오르는 방법의 가짓수는 그 전 세 계단에 도착하는 경우의 수를 전부 더한 것이다. 구현 프로그램 실행결과 소스 파일
-
CheeseAlgorithm with C/DFS 2020. 8. 13. 17:55
1. 문제 2. 문제 분석 위의 문제에서 쓰이는 알고리즘이 흡사 스타크래프트에서 저그의 크립이 없어지는 알고리즘과 같을 것이라는 생각이 들지 않는가? 그리고, 이 문제는 앞에서 했던 "두더지 굴" 문제를 응용할 것이다. 아래와 같이 치즈가 놓여져 있는 이차원 배열이 있다고 가정해보자. 치즈가 놓여져있는 공간은 1, 없으면 0 . 첫 번째로 우리는 탐색 지점을 배열의 첫 번째 인덱스라고 가정하겠다. (0,0)이 초기값 탐색 방향은 편의상 "아래->오른쪽->위 -> 왼쪽" 이라고 하겠다. 처음에 시작점에 도착했는데, 치즈가 없는 공간이었다. 이 부분을 -1로 세팅을 한다. 그리고, 탐색을 해보자. 탐색은 치즈가 놓여있지 않은 곳을 시작으로 탐색을 한다. (재귀 호출을 이용해서.) 다만 탐색을 진행하다가 탐색..
-
문자열에서 공백이 2칸 이상이면 한칸 씩으로 만들기C 자료구조/1. 재귀함수 2020. 8. 4. 18:23
1. 문제 문자열 중에서 단어 사이에 나타나는 공백이 2개 이상인경우 하나씩의 공백만 존재하도록 만들기 2. 구현 첫 번째로 문자열에 공백이 있는지를 알아내는 함수를 만들어 보자. 이 함수의 이름을 ThereIsBlank 라고 부르자. 아래의 ThereIsBlank함수가 필요한 이유는 문자열에 공백이 2칸미만일 때까지 계속 작업이 계속되어야 하기 때문이다. BlankControl함수는 문자열을 탐색하는 함수이다. 아래의 Shift 함수는 한 칸 왼쪽으로 이동시키는 함수이다. 아래의 main 함수에서 BlankControl 함수는 문자열에 공백이 2칸이상 존재할 때까지 호출이 된다. 그리고 Visual Studio 2019에서 gets함수를 쓰면 경고가 떠서, gets_s함수를 사용. 프로그램 실행 결과1..
-
파스칼의 삼각형C 자료구조/1. 재귀함수 2020. 8. 3. 19:18
위의 삼각형대로 출력하는 것이 이번 챕터의 내용이다. 위의 그림을 좀 더 자세히 그려보도록 하자. 조합은 아래와 같이 계산 된다. 이항계수에 대한 내용은 아래에서 보고 오도록 하자. designatedroom87.tistory.com/54?category=868275 이항계수 이항계수를 구현하는 방법은 2가지 방법이 있다. 하나씩 알아보자. 이항 계수는 다음과 같이 순환적으로 정의된다. case 1 case 2 구현 1. 프로그램 실행결과 소스 파일 구현 2. 프로그램 실행결과 소 designatedroom87.tistory.com 그리고, 위의 파스칼의 삼각형을 아래와 같이 수식화 할 수 있다. 힌트 먼저, Combination을 계산하는 함수를 하나 만들도록 하자. combination은 위와 같이 ..
-
소수 3개 이상의 곱 으로 구성된 합성수 찾아라.C 자료구조/1. 재귀함수 2020. 8. 3. 18:35
문제 n 이하의 자연수 중에서 소수 3개 이상의 곱 으로 구성된 합성수를 선택하여 출력하는 프로그램을 작성한다. 예를 들면, 8 = 2 * 2 * 2, 12 = 2 * 2 * 3, 30 = 2 * 3 * 5등이 소수 3개 이상의 곱으로 구성된 합성수이다. n에는 8이상의 자연수를 입력하기로 한다. 입력 8이상의 자연수 n을 입력 : 50 출력 소수 3개 이상의 곱으로 구성된 합성수 : 8 12 18 20 27 28 30 42 44 45 50 2. 구현 프로그램 실행결과 3. 소스 파일
-
-
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. 개념 아래의 두 식을 행렬로 만들자. 아래의 첫 번째 식은 피..