Algorithm with C/DFS
-
LCS(최장 공통 부분 수열 - longest common subsequence) 재귀적 방법 & 중복제거의 메모이제이션Algorithm with C/DFS 2020. 9. 27. 23:47
발췌 문헌 ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하� ko.wikipedia.org LCS 문제는 최적의 부분구조를 가진다. 이 문제는 더 작은, "부분문제"로 쪼개질 수 있고, 이것은 반복해서 자명한 부분문제가 될 때까지 더 간단한 부분문제로 쪼개질 수 있다. LCS는 또한 겹치는 부분문제를 가진다. 더 높은 부분문제에 ..
-
조약돌 놓기 문제Algorithm with C/DFS 2020. 9. 16. 19:22
문제 출처 문제 i열에 돌을 둘 수 있는 가지수를 살펴보자. 위의 임시 테이블에 i열을 다음과 같이 설정하자. i열에 돌을 둘수 있는 경우의 수를 파악하자. 아래와 같이 4가지 경우가 있음을 알 수 있다. i열에 돌을 둘 수 있는 가지수는 4가지임을 알 수 있다. 우선 최적 부분구조의 존재를 확인해보자. n열 중 1열부터 i열까지 돌을 놓는 경우에 1열부터 i열까지의 합의 최고치를 생각해보자. 위에서처럼 i열에는 4가지 패턴 중 하나의 경우로 돌이 놓여질 것이다. (1). i열이 패턴1로 놓여 있을 경우의 최고점 (2). i열이 패턴2로 놓여 있을 경우의 최고점 (3). i열이 패턴3으로 놓여 있을 경우의 최고점 (4). i열이 패턴4로 놓여 있을 경우의 최고점 그리고, 다음과 같은 경우에 대해서도 생각..
-
N 개의 계단Algorithm with C/DFS 2020. 9. 16. 18:58
문제 N 개의 계단을 사람이 오른다고 하자. 한 번에 1계단 오르기도 하고, 2계단이나 3계단씩 오르기도 한다. 계단을 오르는데 몇 가지 방법이 있는가? 문제 분석 N 번째 계단에 도달하는 방법을 생각해보자. N - 1 번째 계단에서 한 계단 더 올라 N 번째 계단에 도달했을 수도 있고, N - 2 번째 계단에서 두 계단을 뛰어 N 번째 계단에 도달했을 수도 있고, N - 3 번째 계단에서 세 계단을 한 번에 뛰어 N 번째 계단에 도달했을 수도 있다. 그러므로, 마지막 계단에 오르는 방법의 가짓수는 그 전 세 계단에 도착하는 경우의 수를 전부 더한 것이다. 구현 프로그램 실행결과 소스 파일
-
이동 경로의 가지수를 구하라.Algorithm with C/DFS 2020. 9. 16. 18:47
문제 본인이 프로그래밍을 한 이후에 올바르게 값이 출력이 되는지 궁금할 것이다. 이 문제에서 구하는 경로의 개수는 아래와 같이 표현된다. 위와 같이 식이 세워지는 이유를 찾아보자. X번 오른쪽으로, 그리고 Y번 아래쪽으로 진행하여 만들 수 있는 모든 경로의 수를 세야 한다. 이 경로는 ( X + Y ) 개의 이동 단계로 구성된다. 경로 하나를 만들려면, X + Y 번 이동하는 가운데 X번은 오른쪽으로 움직이도록 해야 한다. 그러므로, 전체 경로의 수는 ( X + Y ) 가운데 X의 항목을 뽑는 경우의 수와 같다. 그래서, 위와 같은 이항식이 나온다. 문제 분석 위의 문제의 초점은 로봇이 움직이는 방향이다. 로봇은 두 방향으로만 움직이는 것이 가능하다. 그리고, 시작위치와 끝 위치가 주어져 있다. 여기서 ..
-
마족 찾기Algorithm with C/DFS 2020. 9. 9. 11:34
1. 문제 2. 문제 분석 이 문제는 BFS방식으로 접근하는 것이 올바르다. 주민의 수가 너무 많아지면, DFS방식에서는 stack overflow가 나타나기 때문이다. 그러나, 여기서는 DFS방식으로도 접근을 해볼것이다. 아래의 구현에서는 Res배열을 하나 선언할 것인데, 선언하는 이유는 아래와 같다. 마을 주민이 3사람이 있다고 하자. (1,2,3 이라고 칭하겠다.) 주민 1번이 마을 주민 2,3,4 번을 지목했다고 하자. 그러면 지목을 받은 주민 2번 주민이 지목을 한다. 3.4.5번 주민을 지목한다고 하자. 그리고, 3번 주민이 지목을 한다. 3번 주민이 2,4,5번을 지목했다고 했을 때, 이미 주민2번이 주민3번을 지목했고, 다시 3번 주민이 2번 주민을 지목한 상황이 되었다. 즉, 위와 같은 ..
-
집합의 부분 집합 출력하기 - 상태공간트리Algorithm with C/DFS 2020. 9. 7. 10:15
1. 문제 입력으로 ABC가 입력되었다고 가정했을 때, 이 ABC의 부분집합들을 출력하면 된다. 입력 ABC 출력 { } { A }, { A, B }, { A, B, C } { B }, { B, C } { C } 구현방법 먼저, 출력의 형태를 다음과 같이 다시 써보도록 하자. 집합의 원소 개수가 3일 때, 부분집합의 개수는 총 2^3 = 8개가 나온다. 구현 방식은 두 가지가 있다. 첫 번째 방식은 별도의 출력 배열을 가지고 있는 경우와 두 번째 방식은 별도의 메모 배열( 동적 프로그래밍을 위한 )을 두고서 기록하는 경우이다. 두 부분에서 일치하는 방식은 아래와 같다. 먼저 사용자로부터 집합 원소의 개수를 입력 받도록 하자. 입력으로 3이 들어오면, 3칸짜리 char형 배열이 만들어지면서 이 배열안에 각..
-
출근길은 즐거워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. 문제 분석 직관론적으로 조합을 이용해서 경우의 수를 구해볼 수 있다. 그러나, 우리는 컴퓨터 사고 방식으로 문제를 해결해야 한다. 이 문제를 해결하는 핵심은 다음과 같다. 출발점에서 각 지점까지 갈 수 있는 경우의 수를 적어나간다. 먼저, 가장 위의 도로, 가장 왼쪽 도로에 경우..