Kwin's Development Diary.

문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 문제 접근 방법 n!이라는 숫자의 일의 자리부터 처음으로 0이 아닌 수가 나오기 이전까지 총 0의 개수를 출력하는 문제이다. 예를 들면 3! = 6이므로 일의 자리부터 0이 아니므로 0을 출력 10! = 3268800이므로 일의 자리부터 십의 자리까지 0이 나오므로 2를 출력 이런식의 문제이다. 그렇다면 n이 입력되면 n!을 구해야 하는 것인가? 결론부터 말하면 아니다. n!은 1~n의 곱으로 만들어진 수이다. 그렇다면 맨 뒷자리에 0이 오려면 인수로 10이 있다는 소리가 된다. 아직 이정도의 정보만으..

플로이드-와샬(Floyd-Warshall Algorithm) = 플로이드 알고리즘, 로이-와샬 알고리즘, 로이-플로이드 알고리즘, WFI 알고리즘 : 음의 사이클이 없는 가중 그래프에서 최단 경로를 찾는 알고리즘이다 특징 ① 음의 간선이 있는 가중 그래프에서 사용 가능 (≠ 다익스트라 알고리즘(Dijkstra Algorithm)) 알고리즘 ① V1부터 Vn까지 연결된 간선 인접 행렬에 저장 ② 경유하는 정점으로 V1~Vn을 설정 (k) ③ 시작 정점(i)을 V1~Vn, 도착정점(j)을 V1~Vn으로 하는 경우 모두 탐색 이때, 의 값이 + 보다 1. 작거나 같으면 그냥 넘어감 2. 크면 값 대체 더보기 Before graph V1 V2 V3 V4 After graph V1 V2 V3 V4 V1 0 INF..

너비 우선 탐색(Breath First Search, BFS) : 하나의 정점으로부터 시작하여 인접한 정점들을 우선으로 탐색하여 최종적으로 모든 정점을 탐색하는 방법 특징 ① 목표 지점까지 최단 길이(경로)를 보장한다. ② 경로가 길수록 인접한 정점이 많이 생겨나므로(저장되므로) 저장 공간이 많이 필요하다. ③ 선입선출(FIFO, First In First Out) 구조이다. BFS 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue ③ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue 하여 구한 정점에서 ②반복 ④ 큐가 공백이 될 때까지 ②~③반복 더보기..

문제 세준이는 양수와 +, -, 그러고 괄호를 가지고 식을 만들었다. 그러고 나서 세준이는 괄호를 모두 지웠다. 그러고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 문제 접근 방법 괄호가 없는 식이 입력으로 주어진다. 이때 우리는 식의 결괏값을 최소로 만들어야 한다..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 문제 접근 방법 이번 문제는 입력으로 주어진 그래프의 연결 요소의 개수를 파악하는 문제이다. 이때, 연결 요소란? 한 정점에서 출발하여 도착할 수 있는 정점들의 집합이라 생각하면 쉽다. 이게 무슨 의미냐면 정점 V1과 간선을 통해 해당 정점 Vn에 도착할 수 있다면 같은 연결 ..

문제 위 그림과 같이 삼각형이 나선 모양으로 놓여 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 문제 접근 방법 이번 문제는 다이나믹 프로그래밍..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 ..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 문제 접근 방법 수빈이가 동생을 찾는 최소한의 시간을 출력한다. = ..

깊이 우선 탐색(Depth First Search, DFS) : 하나의 정점으로부터 시작하여 깊은 곳 우선으로 탐색하여 최종적으로 연결된 모든 정점을 탐색하는 방법 특징 ① 경로상의 노드들만 기억하면 되므로 차지하는 저장 공간이 적다. ② 같은 레벨의 경로보다 더 깊은 레벨을 우선으로 탐색한다. ③ 재귀적으로 동작하며, 후입 선출(LIFO, Last In First Out) 구조이다. 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정점을 스택을 pop 하여 받은 정점 v로 하여 다시..

이번 포스팅은 ArrayList와 HashSet을 어떤 상황에 사용하면 좋을 지에 대해 말해보려 한다. 이전에 성능과 상관없이 코드를 작성할 때는 굳이 HashSet은 사용하지 않았다. 왜냐면 정렬도 되지 않고 순서를 보장해주지 않기 때문이다. 그러나, 알고리즘 문제를 풀면서 HashSet을 다시 보게 되었고 그래서 두 자료형에 대해 장단점을 비교하여 어떤 상황에서 어떤 선택이 좋은 선택이 될지 알아보겠다. 성질 List는 중복을 허용, 순서를 보장 Set은 중복을 허용하지 않음, 순서를 보장하지 않음 위 성질을 바탕으로 우린 다음 두 가지를 비교해 볼 수 있다. 1. 중복의 허용 2. 순서의 보장 그렇다면 순서가 상관없으면서 중복 없이 저장하고 싶을 때만 Set자료형을 사용해주면 되는 것이 아닌가?라고..