다익스트라 알고리즘 (Dijkstra Algorithm) 개념 - 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 - BFS와 DP를 활용한 최단경로 탐색 알고리즘 - DP를 활용하는 이유는 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 활용하기 때문 - 그래프의 간선마다 가중치가 존재할 때 사용 (음의 가중치는 존재하지 않음) 구현 - 최단 거리 테이블 MAX 값으로 초기화 (최단 거리를 저장해야 하므로 큰 수로 초기화 시킴) - 출발 노드 설정 - 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택 - 해당 노드를 거쳐 다른 노드로 이동하는 비용을 계산하여 최단 거리 테이블 갱신 - 계속해서 가중치가 가장 짧은 노드를 선..
부분집합(Subset) 개념 - 집합에 포함된 원소들을 선택하는 것 - 아무 것도 안 뽑는 것부터 전체 다 뽑는 것까지 조합의 경우를 다 더한 것과 같음 - 부분집합을 이용하여 조합으로 사용하고 싶으면 지금까지 선택한 원소의 개수가 r개가 되면 조합을 구할 수 있음 - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 - 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합 구현 - 하나의 원소에 대해서 선택, 비선택 하는 과정을 재귀로 진행 - isSelected[cnt] = true : 선택 - Subset(cnt+1) : 다음 원소 (선택에 대한 처리하면서 뒤에 따라오는 모든 경우를 따짐) - isSelected[cnt] = false : 비선택 - Subset(cnt+1) :..
조합(Combination) 개념 - 서로 다른 것들(n개) 중에서 몇 개(r개)를 순서없이 골라낸 것 - nCr - 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합 구현 - 중복체크를 안하면서 코드가 더 간결해짐 - 시작 위치(start)를 매개변수로 넘겨 매개변수부터 끝까지 탐색 -> 중복이 발생하지 않음 - 현재 뽑은 수가 i이므로 i 다음 수부터 조합을 시도하도록 i+1을 넘김 - input[] : 서로 다른 숫자(n개)를 저장하기 위한 Integer 배열 - numbers[] : 뽑은 숫자(r개)를 저장하기 위한 Integer 배열 코드 public static void combination(int cnt, int start){ if(cnt == R){ System.out.println..
순열(Permutation) 개념 - 서로 다른 것들(n개) 중에서 몇 개(r개)를 뽑아 순서있게 한 줄로 나열 - nPr - 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합 - n번째 수를 뽑을 때, n-1번 비교를 해야 사용 가능한 수를 판단할 수 있음(최악의 경우) 구현 - 몇 번째 자리의 수를 뽑는지 달라지고 있기 때문에 해당 부분이 가변적임 -> 매개변수로 받아옴(cnt) - input[] : 서로 다른 숫자(n개)를 저장하기 위한 Integer 배열 - numbers[] : 뽑은 숫자(r개)를 저장하기 위한 Integer 배열 - isSelected[] : 중복 체크를 위한 Boolean 배열 - 해당 자리를 선택하고 뒤를 다 탐색하고 다시 돌아오면 다른 수를 또 탐색해야하므로 그 자..