input1 output1 input1 output1 A*(B+C) ABC+* A+B*C-D/E ABC*+DE/- 해당 문제는 자료구조 중에서 스택을 이용하여 해결가능 한 문제이다. 문제 해결 과정은 아래와 같다. 피연산자를 만나면 바로 출력한다. 연산자가 들어오면 자신보다 우선순위가 높거나 같은것들을 제외하고 스택에 넣는다. 여는 괄호 '('를 만나면 스택에 넣는다. 닫힘 괄호 ')'를 만나면 여는 괄호 '('를 만날때 까지 스택에서 꺼내 출력한다. 우선순위 처리는 다음과 같다. 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 낮은 경우 스택에 있는 연산자를 꺼내 출력하고 처리 중인 연산자는 스택에 넣는다. 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 큰 경우 처리 중인 연..

input output 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 4 해당 문제를 먼저 해석하면, n x n 크기의 대나무 숲은 2차원 배열로 정의한다. 판다는 대나무가 많은 곳으로 이동하기 때문에 판다가 이동하는 만큼 생존한다고 볼 수 있다. 판다가 생존 가능한 최대 일 수는 아래 표로 정리하였다. 해당 문제는 DFS와 동적 계획법을 사용한다면 해결가능한 문제이다. 만약, DFS만을 진행한다면 이미 탐색한 곳에 대해서 다시 탐색하는 의미없는 탐색을 진행하기 때문에 최대 깊이까지 탐색한 후 백트래킹을 통해 동적계획법의 값을 저장한다. 백트래킹시에 현재 값에 1을 더해준 값을 반환한다. 전체 소스 코드는 아래와 같다. #include #define max(X,Y) ((X) >..

input1 output1 input1 output1 4 5 1 1 2 1 3 1 4 2 4 3 4 1 2 4 3 1 2 3 4 5 5 3 5 4 5 2 1 2 3 4 3 1 3 1 2 5 4 3 1 4 2 5 해당 문제는 DFS와 BFS로 간선들을 탐색한 결과를 정점 번호로 출력하는 문제이다. 해당 문제를 해결하기 위해서는 DFS와 BFS의 개념을 알고 있어야 한다. DFS(깊이 우선 탐색)이란 트리의 깊은 부분을 먼저 탐색한다는 개념으로 볼 수 있다. DFS는 스택 혹은 재귀함수를 이용한다. DFS는 각 노드를 탐색할 때 주로 사용된다. 동작 과정은 아래와 같다. 첫 시작 노드(루트 노드)를 스택에 삽입하고 방문 표시를 한다. 스택의 최상단 노드를 확인하고 그 노드와 인접한 노드를 스택에 삽입하고 방..

input1 output1 input2 output2 input3 output3 176 177 17 5 9 13 25 28 8 해당 문제는 자연수 N이 홀수인 경우와 짝수인 경우로 나누어 생각하면 쉽게 해결가능한 문제이다. 문제 해석 먼저 해보자. 홀수 인 경우 f(n) 의 값은 무조건 1이다. 짝수인 경우 f(2) = 2, f(4) =4, f(6) = 2 * f(3) ... 문제에서 원하는 수식의 값을 구해보자. S(n) = f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) + f(n) 이다. 점화식으로 표현하면 S(n) = S(b) + S(a-1) 이다. 다시 홀수 와 짝수의 경우로 알고리즘을 생각해보면 아래와 같다. if n % 2 == 0 f(n/2) = 1 // 짝수를..

input output 3 3 1 2 1 2 3 2 1 3 3 3 해당 문제는 최소 비용 신장 트리(MST)를 사용하는 알고리즘 중에서 Kruskal 알고리즘과 Prim알고리즘으로 해결 가능하다. 필자는 Kruskal 알고리즘을 사용하였다. Kruskal 알고리즘은 그리디 알고리즘이다. 그리디 알고리즘은 매 선택의 순간 마다 가장 최선의 선택을 하여 최종적인 해답에 도달하는 방법이다. 최선이라고 선택하였던 지역적인 해답들을 모아서 최종적인 해답에 도달했다고 해도, 그 해답이 전역적으로 최선이라는 보장은 없다. 하지만 Kruskal 알고리즘은 최선의 해답을 주는 것으로 증명되었다. Kruskal 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하..

intput output 8 4 3 6 8 7 5 2 1 + + + + - - + + - + + - - - - - 해당 문제는 스택 자료구조 개념을 알고 문제에서 원하는 바를 이해 한다면 충분히 해결 가능한 문제이다. 문제 해결 과정은 다음과 같다. 더보기 N 만큼 입력 받는다. 1부터 N까지의 수를 조합하여 목표 수열을 만든다.(단, 중복 제외) 수열은 push 와 pop 연산을 사용하여 확인한다. 두 연산으로 목표하는 수열이 있는지 확인한다. 두 연산으로 표현할 수 없다면 "NO"를 출력한다. Last In First Out 특성을 사용하여 오름차순 스택은 3가지 경우로 나뉘어 문제 해결이 가능하다. 더보기 스택의 상단 수가 목표 수 보다 낮은 경우 push 스택 상단 수가 목표 수와 같은 경우 po..

input output 7 35 49 26 27 28 29 30 31 48 25 10 11 12 13 32 47 24 9 2 3 14 33 46 23 8 1 4 15 34 45 22 7 6 5 16 35 44 21 20 19 18 17 36 43 42 41 40 39 38 37 5 7 해당 문제는 홀수인 자연수 N이 입력되면 중간 점을 기준으로 N*N 형태의 배열이 형성되고 배열은 달팽이 모양으로 숫자가 채워져야 한다. 배열을 중간부터 채우는것이 아니라 배열의 끝 부분부터 채우는 식으로 접근하였다. 생각해 보아야 할 조건은 아래와 같다. 배열을 채울 방향을 설정한다. 필자는 하 → 우 → 상 → 좌로 설정하였다. (방향 설정은 어떻게 풀이를 하냐느냐에 따라 다르다.) 배열을 채울 때 범위를 벗어난 경우 ..

input1 output1 input2 output2 input3 output3 2 1 2 3 4 5 6 36 3 1 2 3 4 5 6 69 1000000 50 50 50 50 50 50 해당 문제는 공간 지각 능력을 갖추고 주사위가 탁자 위에 있는 경우와 마주보았을 때의 경우를 동시에 생각해낸다면 해결할 수 있는 문제이다. 마주보았을 때의 경우 1 : 마주보는 면은 포함하지 않는다. A~F면이 0~5 순서로 입력된다고 가정하였을 때 A와 F는 0과 5, E와 B는 1과 4, C와 D는 2와3이 마주본다. 주사위가 탁자 위에 있는 경우 : 면이 1개만 보이는 경우, 면이 2개 보이는 경우, 면이 3개 보이는 경우로 나뉜다. N = 1 인 경우 탁자위에 주사위는 1개만 올라가므로 가장 최솟값을 가지는 면이..