그래프는 다양하게 있지만, 여기선 신장트리, 그 중에서도 MST (최소신장트리)에 대해 작성해보려고 한다. 신장트리 spanning tree: 그래프의 변형 트리는 부모 자식간의 관계, 그에 따른 차수, 높이가 있다. ex) 이진트리 여러 트리중에 신장트리란 각각의 정점들이 모두 연결된 트리 이다. 신장트리의 조건 (ST, spanning tree)(얘는 트리이므로)가중치는 있을 수 있지만, 무향(방향X)이다.cycleX () 그중에 최소신장트리(MST, minimum spanning tree)는 각각의 정점들이 최소비용으로 모두 연결되는 트리 이다.  MST 구현방법쿠르스칼 - 간선중심프림 - 정점 중심(간선이 많을 때 사용)MST - 쿠르스칼: 간선 기반 알고리즘으로 간선을 비용순으로 정렬하여 최소비..

최단경로가장 짧은 경로, 길찾기 최단경로 유형은 "한 지점에서 다른 지점까지의 최단경로",  "모든 지점에서 다른 모든 지점까지의 최단경로" 등으로 나눠볼 수 있다. 이러한 유형은다익스트라 알고리즘플로이드워셜 알고리즘그래프 알고리즘(BFS)greedy & DP 알고리즘벨만 포드 알고리즘등  정말 다양한 알고리즘으로 풀이할 수 있다. 다만 지금까지의 경험으로는 최단경로 문제는 왠만하면? 1~3번으로 거의 다 해결이 되는 느낌이었다.최단경로에는 가중치가 있는데 비용(cost), 거리(distance), 무게(weight) 이런식으로 있을 수 있다.  다익스트라현재 정점에서 다른 특정 정점가중치가 있는 경우O(NlogN) 플로이드워셜모든 정점에서 모든정점가중치가 있는 경우O(N^3) (ex) 사다리타기..?)..

정렬1. 선택 정렬: 가장 작은 데이터를 찾아서 순차적으로 앞쪽에 쌓는다선택 정렬의 특징첫번째 요소부터 나머지 요소들 중 가장 작은 요소와 자리를 교환한다.이 과정에서 앞에서부터 자동으로 정렬되게 된다.ex) 1회 : 9-1-7-5 -> 1-9-7-52회 : 1-9-7-5 -> 1-5-7-9// 선택 정렬 메소드 public static void selectionSort(int[] arr) { int n = arr.length; // 배열의 모든 요소를 순차적으로 탐색 for (int i = 0; i 선택 정렬의 시간 복잡도최악의 경우: O(n^2) 최선의 경우: O(n^2)평균: O(n^2) just 최악선택 정렬의 공간 복잡도O(1) (상수 공..

DFS, BFS그래프, tree를 어떻게 자료구조로 표현할것인가? 를 알기 위해 먼저 자료구조 Stack, Queue를 먼저 알아봤다.더보기 Java Platform SE 8 docs.oracle.comStack : FILO or LIFO 불공평한 자료구조 입구 1개 (입구와 출구가 같다)push(n) : n을 스택에 입력 / pop() : 맨 위(앞)에 있는 원소 반환 + 삭제 / peek() : 맨 위(앞)에 있는 원소 반환Stack의 자료구조는 stack, queue, arraydeque로 만들 수 있다. (하지만 왠만하면 arraydeque를 이용) Queue : FIFO 입구 1개, 출구 1개, 같은 방향으로 요소들이 흐른?다offer(n) : 큐 끝에 n 추가 / poll() : 큐 앞에 요소..

구현머릿속에 있는 알고리즘(사고)을 소스코드로 바꾸는 과정전형적인 문제풀이과정이 아닌, 문제를 읽고 이해해서 문제가 뭘 원하는지 파악해야한다. 문제가 요구하는 내용을 이해해서 이걸 코드로 작성(다양한 방법이 있음)시뮬레이션 : data 초기상태를 잘 받고, 규칙에 따를 수 있게 코드 작성 (시간의 흐름에 따라 데이터 수정등, 주로 반복문 사용)문제를 꼼꼼히 읽어야함 이것이 코딩테스트다 CH04. 예제1: n개의 방향을 입력받고, 방향에 따라 동서남북으로 이동 (단, 일정 범위를 넘어가는 방향은 무시), 최종적으로 도착한 좌표 출력더보기package 구현_ch04;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util...

Greedy 탐욕법현재 상황에서 지금 당장 좋은 것만 고르는 방법개인적으로 알고리즘 방법중 가장 단순 무식한 방법, 단순 암기가 필요하지 않은 방법, 다양한 유형에서 어떻게든 답을 낼 수 있는 방법 이라고 생각한다. 모든 경우의 수를 다 따지는 완전 탐색(브루트포스)을 대비해서 꼭 필요한 (최선의) 선택을 통해서 답을 구함Greedy의 전제조건 : "수학적으로 증명된" 당연한 논리 (막연한 추측은 절대 네버 금물)타고난 수학적 직관력..(은 없어서) 오랜 경험을 통한 판단 해야한다.그래프 알고리즘(DFS, BFS) 에서 Greedy를 사용할 수 있다. 이것이 코딩테스트다 CH03.문제1 큰 수의 법칙: n개의 숫자들 중 m번 더해서 만들 수 있는 최대값을 출력 (단, 같은 수는 k번까지 반복 가능)더보기..

선형 구조 : 자료를 순차적으로 나열한 형태 배열 연결 리스트 스택/큐 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 트리 구성 요소 (너무.. 깔끔한 그림;) 트리는 그래프와 비슷한 구성 요소를 갖는데, 그래프의 정점 → 트리의 노드 이다. 또한, 그래프와 살짝 비교될만한게, 트리는 계층구조를 가지고 있다. 그래서 부모노드, 자식노드 이런 용어가 생긴 것. 레벨 vs 높이 vs 깊이 아파트로 비교했을 때, 레벨 : 각 층 여기는 0층, 여기는 3층 이런식으로 (루트 노드부터 노드까지 연결된 간선 수의 합) 높이 : 이 아파트의 최고 높이 (가장 긴 루트 경로의 길이) 깊이 : 해당 층수까지의 높이 = 레벨 (루트 경로의 길이) Heap Tree (우선순위 큐) 힙트리는 ..

선형 구조 : 자료를 순차적으로 나열한 형태 배열 연결 리스트 스택/큐 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 그래프 구성 요소 정점(Vertex) : 데이터 간선(Edge) : 정점들을 연결하는데 사용 가중치 그래프 : 각 간선에 가중치(중요도, 거리등)가 있는 그래프 방향 그래프 : 정점간의 방향이 있는 그래프 DFS 깊이 우선 탐색 Depth First Search 막다른 길(더이상 연결된 간선이 없을 때 까지)이 나올 때까지 정점을 계속 방문 하는 그래프 끝까지 갔다가 다시 시작 정점으로 돌아오는 부분은 재귀함수로 구현할 수 있다. 그래프의 전체적인 모양을 파악하기 쉽다. void Dfs(int here) { // 방문 visited[here] = true;..

선형 구조 : 자료를 순차적으로 나열한 형태 배열 연결 리스트 스택/큐 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 스택 Stack 메모리에 LIFO(Last-In-First-Out)으로 데이터를 저장하는 구조 : 메모리에 가장 나중에 들어간 데이터가 먼저 출력되는형식 되돌리기 기능같은 곳에 사용하면 좋겠다.(ctrl+z) 따라서 벡터(동적배열)이나 연결리스트 둘중 어느 것으로도 구현할 수 있다. 필요한 기능이 1. 메모리에 데이터 입력하기, 2. 마지막으로 입력된 데이터(맨 뒤에 있는 데이터) 출력하기 2가지 이기 때문. 이건 벡터를 이용해서 stack을 구현한건데, stack의 타입을 list로만 바꿨음에도 잘 동작한다. → 내부적인 구조는 벡터에서 리스트로 바뀌지만..

선형 구조 : 자료를 순차적으로 나열한 형태 배열 연결 리스트 스택/큐 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 1. 배열 (STL Array) 메모리 크기 고정(절대 변경 불가), 연속된 주소 장점 : 연속된 메모리 단점 : 메모리 추가/축소 불가 2. 동적 배열(vector) 메모리 크기의 여유분을 두고(1.5배~2배) 설정, 연속된 주소 만약 여유분이 다 차면, 다같이 연속된 메모리위치로 이사 (여유분의 이유 : 이사횟수를 최소화하기 위해) 장점 : 유동적인 삽입(메모리 여유분 추가 예약으로 이사 최소) 단점 : 중간 삽입 / 삭제 할 경우 나머지가 옆으로 이동해야함 동적 배열 구현 벡터 사용시 헤더 추가 push_back : 현재 저장된 데이터 크기(size)..