고오급 개발자가 되는길

백트래킹 (Backtracking, 퇴각 검색) - 제약 조건 만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크 하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단 되는 즉시 이 후보군은 체크를 하지 않는다는 표기를 하고, 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)을 상태 공간트리를 통해 표현 - 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 넘어가 탐색 • Promising : 해당 루트가 조건에 맞는지를 검사하는 기법 • Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법 대표 문제 • N Que..

프림 알고리즘 (Prim's Algorithm) - 시작 정점을 선택한 후 , 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는방식, - 최소 신장 트리를 확장해가는 방식 구현 1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입 2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입 3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서, => 최소 Heap , PriorityQueue 사용 - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 넘어간다 (사이클 방지) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 최소 신장 트리에..

신장트리(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) - 탐색할 자료들을 둘로 나누어 해당 데이터가..

언젠가 미국주식 관련 프로젝트를 할떄 사용 해볼듯.. pricing 에서 구독한 후 Dashboard탭 에서 발급받은 KEY를 사용하여 API 사용 현재 한국증권 데이터는 가져오지 못하는 것 같다. https://www.yahoofinanceapi.com/ Yahoo Finance API www.yahoofinanceapi.com

병합 정렬 (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..