경로 찾기 문제특정 노드에서 다른 노드로의 경로가 존재하는지 확인예: 미로 탈출, 두 지점 사이의 연결 여부기본적인 DFS를 통해 특정 정점에서 도달 가능한 정점을 찾는다거나, 도달 가능한 정점의 수를 세는 것이 가능하다.단순히 그 점에서 DFS를 한 번 수행하면 된다.예제 문제 - 바이러스백준 2606번: 바이러스(S3)public class Main { static ArrayList[] graph; static boolean[] visited; static int ret = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp..

Lower BoundLower Bound는 정렬된 배열에서 특정 값(= 키 값) 이상이 처음으로 나타나는 위치를 찾는다.=> 즉, 주어진 값 이상인 첫 번째 원소의 인덱스를 반환한다. 특징중복된 값이 존재할 때, 가장 처음 등장하는 위치를 반환값이 존재하지 않으면 삽입될 첫 번째 위치를 반환import java.util.Arrays;public class LowerBoundExample { public static void main(String[] args) { int[] arr = {1, 2, 4, 4, 4, 7, 9}; int target = 4; int index = lowerBound(arr, target); System.out.println..

필자는 모든 문제를 Top-Down 방식으로 풀이했다.계단 오르기계단 오르기(S3) 동적계획법(DP)를 연습하는 데에 좋은 문제라고 생각이 되어 가져와봤다. 내용 자체는 어렵지 않지만, 조건을 제대로 만족하는 식을 작성해내지 못한다면 매우 어렵게 느껴질 수 있다. 규칙은 다음과 같다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.여기서 특히 2번 조건을 잘 고려하여 재귀호출 식을 작성해야 한다.전체코드를 보기 보다는 핵심이 되는 재귀호출을 할 함수를 보자코드static int game(i..

순열(Permutation)여러 개의 요소 중에서 순서를 고려하여 특정 개수를 뽑는 문제로, 완전 탐색의 대표적인 유형이다.보통 '백트랙킹'을 사용하여 구현한다백준 - 모든 순열(S3, 10974번)을 예제로 코드를 살펴보자.최적화 전import java.util.*;public class Main { static int N; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); N = sc.nextInt(); permutation(new ArrayLis..

소수소수(prime number): 양의 약수가 1과 자기 자신 두 개 뿐인 자연수1은 소수도 아니고 합성수도 아님 => 예외 처리 필요!가장 단순한 소수 판별 방법n이 주어졌을 때, 2 ~ n-1까지 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인최적화 포인트: 합성수 n이 p * q로 표현될 때, 한 수는 항상 sqrt(n) 이하, 다른 한 수는 항상 sqrt(n) 이상이다.=> n-1까지 순회하지 않고 sqrt(n)까지만 순회하도록 최적화 가능입력의 개수가 작은 경우에만 사용 가능 (32비트 정수)public static boolean isPrime(int n) { // 맨 처음에 1 이하의 수와 2를 예외 처리 if (n 많은 수에 대해 소수 판단을 해야 하는 경우?=> 에라토스테..

도입무향 그래프의 스패닝 트리(spanning tree): 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 함 (사이클 X, 정점들이 꼭 부모-자식 관계일 필요 X)그래프의 스패닝 유일하지 X최소 스패닝 트리(Minimum Spanning Tree, MST) 문제: 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제= 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제MST 문제를 푸는 2가지 유명한 알고리즘크루스칼 알고리즘프림 알고리즘두 알고리즘 모두 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘 => 결국 같은 방법으로 증명 가능크루스칼 ..

도입최단 경로 문제: 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제가중치가 없는 그래프의 경우, 너비 우선 탐색(BFS)로 찾을 수 있음가중치가 있다면..? => 다익스트라, 벨만-포드, 플로이드-워셜 등의 알고리즘 필요이러한 알고리즘들은 정점들의 목록을 구해주는 것이 아니라, 최단 경로의 길이를 찾아줄 뿐실제 경로를 계산하기 위해서는 너비 우선 탐색에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내는 코드를 작성해야 함음수 간선의 중요성그래프에 대한 최단 경로 문제 해결 시 가장 먼저 유의할 점 => '음수 가중치를 갖는 간선(음수 간선)이 있는지의 여부'왜? => 음수 간선을 지나면 전체 경로의 길이가 짧아지는데, 가중치의 합이 음수..

도입개념너비 우선 탐색(Breadth First Search, BFS): 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정큐를 사용하여 항상 먼저 넣은 정점을 먼저 꺼내도록 구현깊이 우선 탐색과 달리 너비 우선 탐색에서는 '발견'과 '방문'이 같지 않음. 모든 정점은 다음 3개의 상태를 순서대로 거침아직 발견되지 않은 상태 (= discovored[i] = false)발견되었지만 아직 방문되지는 않은 상태 (= 큐에 저장되어 있는 상태 && discovored[i] = true)방문된 상태 (= 큐에서 꺼내어진 상태)너비 우선 탐색 스패닝 트리(BFS Spanning Tree): 너비 우선 탐색에서 새 정점을 발견하는 데 사용한 ..

깊이 우선 탐색깊이 우선 탐색의 정의탐색(serach) 알고리즘: 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘탐색 과정에서 얻어지는 정보들을 통해 그래프의 구조를 알 수 있음깊이 우선 탐색(depth-first search, DFS): 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 방법이 과정에서 더 이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아감깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다(백트래킹)더 따라갈 간선이 없을 경우 뒤로 돌아간다는 점은, '재귀 호출'을 ..

본 게시글은 '알고리즘 문제 해결 전략 1'을 읽고 단순히 정리한 내용입니다.동적 계획법동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 '문제를 나누는 방식'이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. 그러기 위해서는 각 문제의 답을 메모리에 저장해둘 필요가 있다. 이때 이미 계산한 값을 저장해 두는 ..