Algorithm with C
-
Self-numberAlgorithm with C/ETC 2020. 9. 7. 12:04
1. 문제 2. 문제 분석 위에서 셀프넘버를 구해야 한다고 했다. 그런데 문제의 예시에서 나왔다시피, 숫자 91과 100의 제네레이터는 101로 서로 같다. 위의 에시에서 보다시피, 중복되는 제네레이터를 기록해야 한다. 즉, 메모이제이션 기법을 써야하며, 배열로 두자. 그리고, 배열의 인덱스를 어떤 용도로 쓰냐면, 해당 정수의 제네레이터로 쓰자. 문제 풀이 방법은 2가지가 있는데, 둘 다 메모이제이션 기법을 쓰며, 해당정수의 각 자리수를 얻어내는 방법은 동일하다. 해당 정수의 각 자리수를 얻어내는 방법은 while문을 이용해서 10으로 나눈 나머지와 몫을 이용하면 쉽게 알 수 있다. 3. 자료 구조 정의 Array배열은 기록을 위한 배열이다. 즉, 중복을 막기위함이다. 배열의 길이가 왜이렇게 크냐라는 질..
-
BridgeAlgorithm with C/ETC 2020. 9. 7. 11:33
1. 문제 절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 이고, 다른 하나는 이다. 아래 [그림 1]은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 를 표시하는 것이고, 아래의 가로줄은 를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 { R, I, N, G, S } 중 하나이다. [그림 1] 반지원정대가 소유하고 있는 마법의 두루마리에는 와 를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져, 반지원정대는 화산 속으로 떨어지게 된다. 다리를 건널 때, 다음의 제한조건..
-
숙직 선생님Algorithm with C/BFS 2020. 9. 7. 10:19
1. 문제 https://designatedroom87.tistory.com/77?category=881035 숙직 선생님 1. 문제 2. 문제분석 BFS 나 DFS는 항상 트리의 개념으로 이해를 해야 한다. 그리고, 위의 입력 예시와 같이 먼저, 선생님의 현재위치를 1로 고정시키고, 누군가의 위치를 15로 고정 시키자. 그러면 designatedroom87.tistory.com 2. 필요한 자료 구조 정의 위와 같이 전역 변수를 정의하며, 변수의 목적은 다음과 같다. 각 위치까지 이동한 회수가 배열의 값으로 기록 된다. 배열의 인덱스가 숙직 선생님의 이동한 위치로 쓰이며, 배열의 값은 숙직 선생님이 이동한 위치(인덱스)로 올때 까지의 이동 회수이다. 배열이 16칸인 이유는 숙직 선생님이 이동할 위치는 ..
-
집합의 부분 집합 출력하기 - 상태공간트리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. 문제 분석 직관론적으로 조합을 이용해서 경우의 수를 구해볼 수 있다. 그러나, 우리는 컴퓨터 사고 방식으로 문제를 해결해야 한다. 이 문제를 해결하는 핵심은 다음과 같다. 출발점에서 각 지점까지 갈 수 있는 경우의 수를 적어나간다. 먼저, 가장 위의 도로, 가장 왼쪽 도로에 경우..
-
행렬에서 최대 경로 구하기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)까지 도달하는 최고 점수가 된다. 위 점화식의 ..