분류 전체보기
-
출근길은 즐거워Algorithm with C/DFS 2020. 9. 2. 17:49
1. 문제 이번에는 출근길에 주위 경치의 아름다움을 느낄 줄 아는 즐거워 씨의 이야기이다. 즐거워 씨는 동네의 각 위치마다 아름다운 정도를 나타내는 자연수 값을 적어두고 있다. 아름다운 정도를 나타내는 즐거워 씨의 동네 지도는 다음의 2차원 배열로 나타낼 수 있다. 즐거워 씨의 동네에는 공사 중인 곳이 없다. [그림 1] 즐거워 씨도 매일 아침, 위치 (0,0)에서 위치 (4,4)로 출근한다. 즐거워 씨가 출근길에 느끼는 즐거움은 지나가면서 만나는 경치의 아름다움의 합이 된다. 예를 들어, 아래의 [그림 2]와 같이 출근하면 1+1+2+1+3+1+2+1+2 = 14 만큼의 즐거움을 느끼며 출근하게 된다. [그림 2] 즐거워 씨도 항상 최단 거리로 출근한다. 예를 들어, 아래 [그림 3]과 같은 경로는 매..
-
출근길Algorithm with C/DFS 2020. 9. 2. 16:24
1. 문제 지루해 씨는 매일 아침 집에서 회사까지 걸어서 출근한다. 회사에 지각하면 안 되는 지루해 씨는 항상 최단 경로를 고려한다. 아래 [그림 1]은 지루해 씨의 동네 지도다. 지루해 씨가 사는 동네는 곳곳에서 공사를 하고 있는데, 공사 중인 곳은 지나갈 수 없다. 왼쪽 위의 집에서 출발하여 오른쪽 아래의 회사에 도착해야 한다. [그림 1] Q. 출근길의 수 지루해 씨가 출근길로 택할 수 있는 경로는 모두 몇 가지인가? 2. 문제 분석 직관론적으로 조합을 이용해서 경우의 수를 구해볼 수 있다. 그러나, 우리는 컴퓨터 사고 방식으로 문제를 해결해야 한다. 이 문제를 해결하는 핵심은 다음과 같다. 출발점에서 각 지점까지 갈 수 있는 경우의 수를 적어나간다. 먼저, 가장 위의 도로, 가장 왼쪽 도로에 경우..
-
행렬에서 최대 경로 구하기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. 헤더 파일 & 소스 파일
-
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. 소스 파일