고오급 개발자가 되는길

어떻게든 푼다! 완전 탐색 - 가장 기본적으로 접근하는 방식이므로 많은 연습이 필요하다 완전탐색이란? - 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법 - 그 중에서도 백트래킹을 통해야 하는 상황 해결 • 모든 코테 문제에서 기본적으로 접근해봐야하므로 많은 연습이 필요하다 장점 : 부분 점수를 얻기 좋다 단점 : 전부 탐색하기에 시간 복잡도가 일반적으로 높다. 1. N개중 중복을 허용하고 순서대로 나열하는 알고리즘 구현 (재귀함수) // 만약 M 개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것! // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다. static void rec_func(int k) { if (k == ..

알고리즘 유형별 문제풀이 실제로 현업에서는 알고리즘 및 자료구조를 사용하지는 않지만 알고리즘으로 코딩 테스트를 보는 이유는? -> 개발이란 무엇인지를 이해하고 있는가에 대해서 알아보는 시간 왜 알고리즘으로 코딩테스트를 하는가?! => 실제 개발자가 하는일과 공통점이 있기 때문 개발자가 하는 일 알고리즘 문제를 푸는 과정 1. 무엇을 만들어야하는지 파악 문제이해 2. 기능성, 효율성을 따져서 만들 방법 찾기 기능성,효율성을 따져 문제가 원하는 정답 구현 3. 프로그래밍을 통해서 직접 구현하기 프로그래밍을 통해서 직접 구현 • 필수 테크닉 - 정렬 - 문자열 처리 - DP(Dynamic Programming) - Dijkstra (다익스트라) - BFS & DFS - 완전 탐색 - 이분 탐색 • 높은 난이도..

자료구조와 알고리즘 정리 자료구조 • 배열 (Array) - 같은 유형의 데이터를 여러개 넣어 관리하는 데이터구조 • 큐 (Queue) - 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 (FIFO) • 스택 (Stack) - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터구조 (LIFO) • 링크드 리스트 (Linked List) - 데이터와 다음 데이터의 주소를 저장하는 공간을 같이 저장하여 중간 데이터 삽입,삭제 시 데이터를 찾아갈 수 있다. - 데이터 저장 단위인 Node와 이전노드와 연결 정보를 가진 포인터로 구성 º 더블 링크드 리스트 (Double Linked List, 이중 연결 리스트) - 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 • 해쉬 테이블 (Hash T..

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

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