재귀함수
-
연구활동 가는 길( 인접 행렬 풀이 )Algorithm with C/BackTracking 2020. 8. 19. 19:08
1. 문제 2. 문제 분석 위는 SetDataLoadDataFromFile함수가 호출이 되면, 이차원배열g_Path에 cost가 저장이 된다. cost값이 0이라는 의미를 2가지를 포함하고 있다. 1. 자기 자신에서 자기 자신으로 갈 때의 cost값은 0이다. 2. '길'을 갈 수가 없는 경우에 cost값은 0이다. (현재의 정점과의 연결이 안된 경우) 예를 들어서, g_Path[0][0] = 0 의 의미는 자기 자신에서 자기 자신으로 갈 때의 경우이다. g_Path[1][2] = 0 의 의미는 1번 정점과 2번 정점은 서로 연결되지 않았다는 의미이다, 여기서, 탐색을 할 때 이차원 배열의 행과 열은 다음과 같다. 행 요소 = 현재의 정점 열 요소 = 현재의 정점과 연결된 다음 정점 이를 토대로 다시 설..
-
삼각화단 만들기Algorithm with C/DFS 2020. 8. 17. 19:26
1. 문제 2. 문제 분석 이 문제의 핵심은 "비선형 탐색이 반드시 답이 아니다." 라는 것을 보여주는 문제이다. 결론부터 말하면, 이 문제는 재귀를 쓰는 방식보다 for문을 3번 돌려서 구하는 것이 빠르다. 우리는 2가지 방식 전부를 만들어 볼 것 이다. 그리고, 이 문제를 해결하기 전에 한 가지 약속을 하자. 아래와 같은 가정을 하는 이유는 밑에 나온다. 삼각형의 각 변의 길이를 A,B,C라고 두면, C를 가장 긴 변, B는 C다음으로 긴 변, A를 가장 작은 변이라고 가정하자. ( A
-
회문(Palindrome)Algorithm with C/DFS 2020. 8. 14. 18:12
1. 문제 We define a palindrome to be a sequence of characters that reads the same backward as it does forward. For example, “tacocat” and “12221” are palindromes, but, “tacocats” and “8675” are not. We define a subsequence to be a sequence formed by copying a contiguous section of elements from sequence and deleting 0 or more characters from it. Walter wants to improve his understanding of strings..
-
이항계수C 자료구조/1. 재귀함수 2020. 8. 3. 18:58
이항계수를 구현하는 방법은 2가지 방법이 있다. 하나씩 알아보자. 이항 계수는 다음과 같이 순환적으로 정의된다. case 1 case 2. factorial을 활용한 방법 구현 1. 프로그램 실행결과 소스 파일 구현 2. factorial을 활용한 방법 아래의 내용을 참고해도 된다. designatedroom87.tistory.com/2?category=868275 1. Factorial Factorial은 다음과 같이 표현된다. designatedroom87.tistory.com 프로그램 실행결과 소스 파일
-
문자열 AnagramC 자료구조/1. 재귀함수 2020. 7. 30. 17:50
1. 개념 Anagram 이란 문자들의 순서를 재배열하여, 동일하게 만들수 있는 문자열이라고 한다. 즉, 같은 알파벳으로 이루어진 문자열을 의미하는것이다. 아래의 예를 들어보자. 입력 abc cba 출력 Anagram ------------------------------------------------------------------------------------------- 입력 noon onno 출력 Anagram ------------------------------------------------------------------------------------------- 입력 abg abw 출력 Not Anagram 아래에서 다음의 문제를 먼저 보고 오도록 하자. designatedroom8..
-
문자열 순열로 출력하기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. 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이 만약에 홀수라면 (예를 들어 ..