Algorithm with C/ETC
-
Catalan NumberAlgorithm with C/ETC 2020. 9. 8. 23:47
1. 문제 1부터 n 까지의 정수가 차례로 스택에 push 된다. push 가 이루어지는 중간에, 또는 모든 숫자들이 push된 이 후에 언제든지 임의로 숫자들을 pop 할 수 있다. 이렇게 pop 된 숫자들을 차례로 나열한 수열을 catalan number 라 한다. 예를 들어, n이 4 라면 1,2,3,4 가 차례로 push 된다. 1,2,3,4 모두 push 된 뒤, 네 번 pop 하면 4,3,2,1 이라는 수열이 만들어 진다. 반면에 1,2 가 push 된 뒤, 두 번 pop을 하고, 나머지 3,4 가 push 된 뒤 또 두 번 pop을 하면 2,1,4,3 이라는 수열이 만들어 진다. 따라서, 앞서 말한 대로 4,3,2,1 과 2,1,4,3 은 둘 다 catalan number 이다. 하지만 ..
-
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] 반지원정대가 소유하고 있는 마법의 두루마리에는 와 를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져, 반지원정대는 화산 속으로 떨어지게 된다. 다리를 건널 때, 다음의 제한조건..
-
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. 소스 파일