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개만 올라가므로 가장 최솟값을 가지는 면이..

input output 10 5 2 3 1 4 2 3 5 1 7 1 1 2 2 3 3 4 5 5 7 해당 문제는 시간 제한과 메모리 제한에 의해 많은 실패를 겪었던 문제이다. 필자는 시간복잡도가 nlogn 정렬 알고리즘인 합병정렬과 힙정렬을 사용하였으나 시간초과가 발생하였다. nlogn의 시간복잡도를 가지는 알고리즘을 사용하지만 N의 범위가 (1 ≤ N ≤ 10,000,000) 이기 때문에 최악의 경우 퀵정렬은 O(n^2)의 형태를 띄어 시관초과가 발생하고 합병정렬은 최선, 최악, 평균의 모든 시간복잡도가 O(nlogn)이기 때문에 보다 더 빠른 알고리즘이 필요하다고 생각했다. 카운팅 정렬(Counting Sort)은 시간 복잡도가 O(n+k)로 비교 연산이 없는 정렬 방법이다. 우리는 집합 내의 가장 ..