Algorithm with C/DFS
-
행렬에서 최대 경로 구하기Algorithm with C/DFS 2020. 9. 2. 00:11
1. 문제 2. 문제 분석 행렬의 좌측상단에서 행렬의 원소( i, j )까지 도달하는 경로들의 점수 중 최고점을 구해보자. 원소( i, j )에 도달하기 직전에 방문할 수 있는 행렬의 원소는 2개이다. 즉, 원소( i-1, j ) 와 원소( i, j-1 ) 이다. 원소( i, j )는 무조건 방문되므로, 원소( i, j )의 값은 반드시 더해진다. 원소( i-1, j ) 거쳐서 원소( i, j )에 도달하는 경우와 원소( i , j-1 ) 거쳐서 원소( i, j )에 도달하는 경우 중에서 점수가 높은 쪽을 택하면 된다. 즉, (i-1,j)까지 도달하는 최고점수와 (i, j-1)까지 도달하는 최고 점수 중 큰 것에 원소(i,j)의 점수를 더하면 원소 (i,j)까지 도달하는 최고 점수가 된다. 위 점화식의 ..
-
숙직 선생님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. 헤더 파일 & 소스 파일
-
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/DFS 2020. 8. 23. 21:46
1. 문제 어떤 도시의 중심가는 n개의 동서방향 도로와 n개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며, 남북방향 도로는 왼쪽부터 1에서 시작하여 n까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 n까지 번호가 할당되어 있다. 또한, 동서방향 도로 사이의 거리와 남북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 ( 동서방향 도로 번호, 남북방향 도로 번호 )로 나타낸다. n이 6인 경우의 예를 들면 다음과 같다. 이 도시에는 두 대의 경찰차가 있으며, 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1,1)의 위치에 있고 경찰차2는 (n,n)의 위치에 있다. 경찰 본부에서..
-
삼각화단 만들기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..