하고 싶었던 그리고 하고 싶은 일

최단 경로 알고리즘 최단 경로 문제? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 함이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 (single-source) 최단 경로 문제 그래프 내의 특정 노드 u에서 출발해, 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제 단일 도착 (single-destination) 최단 경로 문제 모든 노드들로부터 출발해, 그래프 내의 특정 노드 u로 도착하는 가장 짧은 경로를 찾는 문제 단일 쌍 (single-pair) 최단 경로 문제 주어진 노드 u와 v간의 최단 경로를 찾는 문제 전체 쌍 (all-pair) 최단 경로 문제 그래프 내의 모든 노..

탐욕 알고리즘 (Greedy) Greedy algorithm 또는 탐욕 알고리즘 이라고 불림 최적의 해에 가까운 값을 구하기 위해 사용 매 순간 최적이라고 생각되는 경우를 선택해 최종적인 값을 구하는 방식 탐욕 알고리즘 예 동전 문제 지불해야 하는 값이 4720원 일 때, 1원, 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 public class GreedyAlgorithm { public void coinFunc(Integer price, ArrayList coinList) { Integer totalCoinCount = 0; Integer coinNum = 0; ArrayList details = new Arr..

너비 우선 탐색 (BFS) BFS 와 DFS ? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식 예제 BFS : A - B - C - D - G - H - I - E - F- J 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회 DFS : A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 끝까지 순회 한 후, 같은 레벨에 있는 노드들의 자식을 순회 Java 로 그래프를 표현하는 방법 HashMap 과 ArrayList 를 활용해서 그래프를 표현 할 수 있음 B..

그래프 이해 그래프란? 정점 (Vertex) 또는 노드 (Node) 와 간선 (Edge) 으로 표현하기 위해 사용 그래프 용어 노드 (Node) : 위치를 말함, 정점 (Vertex) 라고도 함 간선 (Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고 함) 인접 정접 (Adjacent Vertex) : 간선으로 직접 연결된 정점 (노드) 참고 정점의 차수 (Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length) : 경로를 구성하기 위해 사용된..

동적 계획법과 분할 정복 동적계획법 (DP 라고 부름) 입력 크기가 작은 부분 문제들을 해결 한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 부분 문제를 해결하므로써 전체 문제를 해결하는 알고리즘 동적 계획법 상향식 접근법 : 가장 최하위 해답을 구한 후 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법 사용 이전에 계산한 값을 저장해 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨 피보나치 수열 분할 정복 문제를 나눌수 없을 때까지 나누어서 각각 풀고 병합하여 문제의 답을 얻는 알고리즘 하향식 접근법 : 일반적으로 재귀함수로 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 병합 정렬..

재귀 호출 (Recursive call) 함수 안에서 동일한 함수를 호출하는 형태 익숙해져야함 예제 [ 팩토리얼 ] 2! = 1 x 2 3! = 1 x 2 x 3 4! = 1 x 2 x 3 x 4 규칙! : n! = n x (n - 1)! 함수 생성 함수 탈출 조건 생성 n = 1 이면 return n 그게 아니면 return n * 함수(n - 1) public class Factorial { public int factorialFunc(int n) { if(n

삽입 정렬 두 번째 인덱스부터 시작 해당 인덱스 (key 값) 앞에 있는 데이터 (B)부터 비교해서 값이 작으면, B 값을 뒤 인덱스로 복사 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 데이터가 두 개일 때 삽입 정렬 import java.util.*; ArrayList list = new ArrayList(); list.add(5); list.add(2); if(list.get(1) < list.get(0)) { Collections.swap(list, 1, 0); } System.out.println(list); // [2, 5] 데이터가 세 개일 때 삽입 정렬 import java.util.*; ArrayList list = new Arr..

선택 정렬 주어진 데이터 중 최소값을 찾음 해당 최소값을 맨 앞과 교체 맨 앞을 제외한 나머지 데이터를 동일 한 방법으로 교체 데이터가 두 개일 때 선택 정렬 import java.util.*; ArrayList list = new ArrayList(); list.add(8); list.add(2); if(list.get(0) > list.get(1)) { Collections.swap(list, 0, 1); } System.out.println(list); // [2, 8] 데이터가 세 개일 때 선택 정렬 import java.util.*; ArrayList list = new ArrayList(); list.add(10); list.add(2); list.add(8); // 작은 데이터 int min..

버블 정렬 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 데이터가 두 개일 때 버블 정렬 import java.util*; ArrayList list = new ArrayList(); list.add(5); list.add(3); if(list.get(0) > list.get(1)) { Collections.swap(list, 0, 1); } System.out.println(list); // [3, 5] 데이터가 세 개일 때 버블 정렬 import java.util.*; ArrayList list = new ArrayList(); list.add(10); list.add(3); list.add(5); for(int i = 0; i < list.si..

알고리즘 계산 복잡도는 두가지로 나뉘어짐 시간 복잡도 공간 복잡도 둘다 만족시키기는 어려움 시간과 공간은 반비례적 경향 대용량 시스템 보편화로 시간 복잡도가 우선 공간 복잡도 프로그램 실행/완료 시 필요한 저장 공간 총 필요 저장 공간 고정 공간 (알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수 가변 공간 (알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛) / c: 고정 공간, 𝑆𝑝(𝑛) : 가변 공간 공간 복잡도는 가변 공간에 좌우됨 공간 복잡도 계산 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 됨 예제 1 n! 구하기 n! = 1 * 2 * 3 * ... * n 공간 복잡도는 O(n) / 실행시 사용되는 저장공간을 계산하..