고오급 개발자가 되는길

신장트리(Spanning Tree) - 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 - 사이클이 존재하지 않는다 최소 신장 트리(Minimum Spanning Tree, MST) - Spanning Tree 중에서, 간선의 가중치 합이 최소인 신장트리 - 대표 최소 신장 알고리즘 : Kruskal's algorithm, Prim's algorithm • 크루스칼 알고리즘(Kruskal's algorithm) - 탐욕 알고리즘 사용 - 간선을 가장 작은 순서대로 정렬하여 선택, 사이클이 발생하면 탈락! • Union-Find 알고리즘 - 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 떄 사용 - 각 개별의 집합을 묶어서 하나의 그래프로 만든다 - 여러 노드가 존재할 떄,..

최단 경로 알고리즘 - 두 노드를 잇는 가장 짧은 경로를 찾는 문제 - 가중치 그래프에서 간선의 가중치 합이 최소가 되도락하는 경로를 찾는 것이 목적 다익스트라 알고리즘 - 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제 - 우선순위 큐를 사용하는 방식으로 설명, MinHeap방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보 추출 구현 방법 1) 첫 정점을 기준 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장 - 초기에는 첫 정점의 거리 0, 나머지는 무한대(inf)로 저장 2) 우선순위 큐에서 노드를 꺼냄 - 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내진다. - 첫 정점에 인접한 노드를 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장..

탐욕 알고리즘 (Greedy algorithm) - 최적의 해에 가까운 값을 구하기 위해 사용된다. - 여러 경우 중 하나를 결정해야할 때 마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 EX 1 : 동전 문제 public class GreedyAlgorithm { public void coinFunc(Integer price, ArrayList coinList) { Integer totalCoinCount = 0; Integer coinNum = 0; ArrayList details = new ArrayList(); for (int index = 0; index < coinList.size(); index++) { coinNum = price / coin..

탐색 알고리즘 • 순차 탐색 (Sequential Search) - 데이터가 담겨있는 리스트를 앞에서 부터 하나씩 비교하여 원하는 데이터를 찾는 알고리즘 public class SequencialSearch{ public int searchFunc(ArrayList dataList, Integer searchItem){ for(int index = 0; index 시간복잡도 : O(n) • 이진 탐색 (Binary Search) - 탐색할 자료들을 둘로 나누어 해당 데이터가..

병합 정렬 (Merge Sort) - 재귀용법을 활용한 정렬 알고리즘 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 단계별 이해 1단계 : 정렬되지 않은 배열을 끝까지 분리하는 단계 2단계 : 분리한 데이터를 단계별로 합치는 단계 import java.util.ArrayList; import java.util.Collections; public class MergeSort { public ArrayList mergeFunc(ArrayList leftList, ArrayList rightList) { ArrayList mergedList = new Array..

재귀 용법 (Recursive call, 재귀 호출) • 함수 안에서 동일한 함수를 호출하는 형태 팩토리얼 예제 public class Factorial{ public int factorialFunc(int n){ if(n > 1){ return n * this.factorialFunc }else{ return 1; } } } 시간/공간 복잡도 O(N) 동적 계획법과 분할 정복 • 동적 계획법 (Dynamic Programming, DP) - 입력 크기가 작은 부분 문제들을 해결한 뒤, 해당 부분의 해(풀이)를 활용해서 보다 큰 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 - 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용하여 쉬운 문제를 해결하는 방식 - Memoizat..

기본 정렬 알고리즘 공간 복잡도(Space Complexity) - 프로그램을 실행 및 완료한느데 필요한 저장공간의 양 - 총 필요 저장 공간 • 고정 공간 : 코드 저장 공간, 단순 변수 및 상수 EX) 코드의 양,줄 • 가변 공간 : 실행 중 동적으로 필요한 공간 EX) for문을 통한 반복 횟수 버블 정렬 (Bubble Sort) - 인접한 두 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘 import java.util.ArrayList; import java.util.Collections; public class BubbleSort { public ArrayList sort(ArrayList dataList) { // 입력한 dataList의 siz..

데이터 구조 : 힙(Heap) 1. 힙(Heap) 이란? - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 • 완전 이진 트리 (Complete Binary Tree) - 노드를 삽입할 떄 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 2. 힙을 사용하는 이유 - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸린다. => 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다. - 최대값 또는 최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현 등에 활용 • 힙과 이진트리의 공통점 - 모두 이진 트리 이다 • 차이점 - 힙은 데이터 삽입 시 무조건 왼쪽에서 부터 데이터를 넣어, 왼쪽 및 오른쪽 자식의 노드 값은 어느것이 큰지 모른다. - 이진 탐색 트..

트리(Tree) 구조 • 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 - 이진 트리(Binary Turee) 탐색 알고리즘 구현을 위해 많이 사용됨 용어 • Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) • Root Node : 트리 맨 위에 있는 노드 • Level : 최상위 노드를 Level 0으로 하였을 떄, 하위 Branch로 연결된 노드의 깊이를 나타냄 • Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 • Child Node : 어떤 노드의 상위 레벨에 연결된 노드 • Leaf Node : Child Node가 하나도 없는 노드 • Silbing : 동일한 Parent No..

해쉬 테이블 (Has Table) 1. 해쉬 테이블 • 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조 • 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산 • Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐 • 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당, 키에 따른 데이터 저장 및 탐색 지원 2. 용어 • 해쉬 함수(Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 • 해쉬, 해쉬 값 , 또는 해쉬 주소 : 해쉬 함수를 통해 리턴된 고정된 길이의 값 • 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접..