Algorithm with C
-
숙직 선생님Algorithm with C/DFS 2020. 8. 31. 17:43
1. 문제 2. 문제분석 BFS 나 DFS는 항상 트리의 개념으로 이해를 해야 한다. 그리고, 위의 입력 예시와 같이 먼저, 선생님의 현재위치를 1로 고정시키고, 누군가의 위치를 15로 고정 시키자. 그러면 다음과 같이 될 것이다. 그리고 Tree의 개념으로 그림을 그려보자. 위의 그림에서 2, 5, 7이라는 붉은 상자안의 숫자의 의미는 선생님이 한 번에 이동할 수 있는 능력이다. 문제의 입력 예시 부분에서 볼 수 있다. 그리고, 위의 트리 구조에서 1은 선생님의 현재 위치이다. 즉, 선생님이 이동 할 수 있는 위치가 각 각 3,6,8 이라는 위치이다. 1 + 2 = 3 1 + 5 = 6 1 + 7 = 8 그리고, 3,6,8의 위치에서 다시 움직일 수 있는 위치는 아래와 같다. 3 + 2 = 5 3 + ..
-
Binary Search TreeAlgorithm with C/DFS 2020. 8. 31. 10:11
1. 문제 2. 구현 방법 이진 트리를 가지고 와서 만든다. https://designatedroom87.tistory.com/11?category=869064 3. 이진 트리의 연산 ( 노드의 개수, 단말 노드의 개수, 트리의 높이 구하기 ) 1. 이진 트리의 노드의 갯수 구하기 이진 트리 안의 노드의 갯수를 세어서 표시한다. 노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다. 각 각의 서브 트리에 대하여 designatedroom87.tistory.com 그리고, 이 문제는 이진 탐색 트리의 데이터 저장 함수만 만들면 된다. 3. 구현 프로그램 실행결과 4. 헤더 파일 & 소스 파일
-
JumpingCowAlgorithm with C/ETC 2020. 8. 31. 08:59
1. 문제 https://designatedroom87.tistory.com/64?category=881035 JumpingCow 1. 문제 2. 문제 분석 위에서 물약 배열을 탐색하는 함수를 SearchDFS함수라고 한다. 위의 재귀 함수의 호출 스택은 아래와 같다. 입력 배열이 4칸이고 배열의 값은 차례로 9,2,4,1이 들어 있다. 3. 구현 designatedroom87.tistory.com 2. 문제 분석 아래의 그림은 입력받은 물약을 나타낸 것이다. 부호는 점프의 방향을 의미한다. +이면 증가, -는 감소를 의미한다. 아래의 그림은 위의 물약 배열을 그린 그림이다. 기울기는 앞의 수와 뒤의 수를 뺀 차를 나타낸 것으로 양수값과 음수값을 갖는다. 3. 구현 프로그램 실행결과 4. 소스 파일
-
삼각화단 만들기Algorithm with C/ETC 2020. 8. 31. 08:43
1. 문제 문제는 아래에서 볼 수 있다. DFS를 이용해서 만들 수도 있지만, 선형 탐색을 이용해서 구현할 수 있다. https://designatedroom87.tistory.com/65?category=881035 삼각화단 만들기 1. 문제 2. 문제 분석 이 문제의 핵심은 "비선형 탐색이 반드시 답이 아니다." 라는 것을 보여주는 문제이다. 결론부터 말하면, 이 문제는 재귀 designatedroom87.tistory.com 2. 구현 프로그램 실행결과 3. 소스 파일
-
회문(Palindrome)Algorithm with C/BFS 2020. 8. 31. 07:46
1. 문제 문제는 아래에 정의되어 있다. DFS로 만든 것을 BFS로 구현할 것이다. https://designatedroom87.tistory.com/63?category=881035 회문(Palindrome) 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”.. designatedroom87.tistory.com 2. 자료 구조 정의 큐는 앞에서 만든 것을 이용한다. 그리고 큐에 저장할 정보는 탐색할 인덱스의 범위이다...
-
두더지 굴Algorithm with C/BFS 2020. 8. 30. 23:32
1. 문제 DFS에서 만든 두더지 굴을 BFS로 구현한 것이다. 문제는 아래의 글에서 보자. https://designatedroom87.tistory.com/61 큐에 저장할 데이터는 위치 정보이므로 아래와 같이 변경한다. 3. 구현 프로그램 실행결과 4. 소스 파일 & 헤더 파일 5. 두더지 굴의 수와 굴의 크기를 추가 그런데, 문제에서 보면 두더지 굴의 수와 그리고, 각 두더지 굴의 크기를 내림차순으로 출력을 해야한다. 기본적인 정렬 알고리즘은 버블 정렬을 이용하겠다. 그리고 각 두더지 굴의 크기를 저장할 변수를 배열로 선언하고 이는 전역 변수로 두겠다. DFS에서 만든 방식과 같다. 위의 함수를 호출하는 부분은 main함수에서 한다. 프로그램 실행결과 6. 소스 파일 & 헤더..
-
4종류 동전으로 N 센트를 표현하는 경우의 수Algorithm with C/DFS 2020. 8. 27. 19:22
1. 문제 쿼터( 25센트 ), 다임( 10센트 ), 니켈( 5센트 ), 페니( 1센트 ) 의 네 가지 동전이 무한히 주어진다고 했을 때, N 센트를 표현하는 모든 경우의 수를 구하라. 2. 문제 분석 이 문제는 재귀 문제이다. 함수 makeChange(N)을 부분 문제들의 답을 통해 계산하는 법을 알아내 보도록 하자. N = 100 이라고 해보자. 도합 100 센트의 잔돈을 만드는 방법을 계산해야 한다. 이 문제와 부분 문제들은 어떤 연관성을 가지는가? 100센트의 잔돈에는 쿼터가 0개, 1개, 2개, 3개, 4개 있을 수 있다는 것을 알고 있다. ( 쿼터는 25센트니까, 25 * 5 = 125센트가 되어서, 쿼터는 5개가 될 수 없다. ) 그러므로, 위의 관계가 성립한다. 이 결과를 좀 더 들여다보면..
-
미로 탐색Algorithm with C/BackTracking 2020. 8. 26. 19:26
0. 참고 문헌 1. 개념 미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데, 이들 각 길목에서 왼쪽으로 갈지, 오른쪽으로 갈지, 또 계속 가던 방향으로 계속 갈지의 물음(부분 문제)에 답(부분해)을 구하는 과정을 반복하면서 완성한 것이 탈출로(해) 이다. 여기에서 부분 문제의 답은 어느 것이라도 될 수 있다. 선택한 방향으로 끝까지 가봐야 '해를 이루는 부분해'가 될지 안될지를 알 수 있는 것이므로. 게다가 선택한 방향으로 가다 보면 새로운 갈래길목을 만나게 될 것이고, 그 곳에서도 또 여러 가능성을 두고 선택을 해야 하는 상황이 온다. 이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 두고 후보해라고 한다. 백트래킹이 다루는 문제들은 대개 후보해의 수가 굉장히 많다는 특징이 있..