동적 계획법 Dynamic ProgrammingDP라고 불리는 동적 계획법은 이름대로 동적인 알고리즘이 아니다. 이름과 관련이 없으니 DP는 그냥 외워야 한다. DP는 큰 문제를 작은 문제로 나누어 재사용하는 방법을 사용한다.여기서 포인트는 '작은 것으로 나눈다'가 아니라 '재사용한다'를 주목해야 한다. 알고리즘을 처음 공부할 때는 DP에 대해 정확히 이해하지 못했다. 작은 문제로 나눈다는 것에만 집중해 분할정복법(Divide&Conquer)과 비슷한 방법이구나 라고만 알고있었다. 하지만 분할정복과 접근 방식만 같을 뿐, 계산 결과를 재사용한다는 점에서 큰 차이점이 있다.  분할 정복 Divide and Conquer말 그대로 주어진 문제를 분할하여 작은 문제로 나누고, 작은 문제부터 해결해 병합하여 전..

알고리즘 평가 요소 1. 시간 복잡도 (Time Complexity)코드의 실행 시간이 얼마나 빠른가? 알고리즘의 수행 시간을 나타낸다.실행 시간이 빠를수록 주어진 시간 내에 더 많은 일을 할 수 있어 효율적이다. 2. 공간 복잡도 (Space Complexity)얼마나 메모리를 적게 쓰는가? 알고리즘 수행에 필요한 메모리 공간을 의미한다.실행하는 코드가 요구하는 메모리 공간이 적을수록 한번에 사용할 수 있는 여분의 공간이 더 많이 생긴다.더 적은 용량을 사용할수록 더 많은 공간을 사용할 수 있어 효율적이다. 시간복잡도와 공간복잡도는 알고리즘을 평가하는 요소로 중요하게 여기고, 그 중 시간복잡도를 더 고려한다.시간복잡도와 공간복잡도 계산을 할 땐 점근적 표기법을 이용하여 나타낸다.    점근적 표기법 (..

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 ..

전에 파이썬을 이용해 1260번을 풀어본 적이 있다. 이번에는 자바를 이용해서 1260번을 풀고, DFS와 BFS를 구현하려고 한다. [알고리즘] 깊이우선탐색(DFS) & 너비우선탐색(BFS) 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선..

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

탐욕법 Greedy Method 각 단계마다 최적의 방법을 찾는 알고리즘. 여러 조각으로 나누고, 단계마다 답의 한 부분을 만들어가는 방법. 탐욕이라는 이름대로 그리디 알고리즘은 다음 단계를 고려하지 않고, 현재 단계에서 최적해를 찾아낸다. 이 때문에 지역적으로 최적인 답을 찾을 때는 매우 유용하게 사용되는 알고리즘이다. 하지만 지역적 최적이 최종적으로 최적이라는 보장은 없다. 1. 문제 해결 방법 1) 선택 절차 Selection Procedure 현재 상태에서 최적인 답을 선택한다. 2) 적절성 검사 Feasibility Check 조건을 벗어나지 않는지 검사한다. 3) 해답 검사 Solution Check 문제가 해결되었는지 검사한다. 아닐 시 선택 절차로 돌아가 반복한다. 2. 정당성 증명 1) ..

문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20)..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. Queue클래스를 사용해 문제를 풀어보았다. 풀이 입력받은 N을..

문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..