본문 바로가기

CS/알고리즘6

코딩테스트 자료구조, 알고리즘 정리 알아야 할 개념 시간복잡도, 공간 복잡도 알아야 할 자료구조 배열, 연결 리스트, 스택, 큐, 덱, 힙, 트리, 해시, 그래프 알아야 할 알고리즘 정렬, 구현, 재귀, 그리디, 탐색(+DFS/BFS, 백트래킹, 이분 탐색), 다이내믹 프로그래밍, 그래프 알고리즘 알고리즘 배열 문제 Array, LinkedList Sliding window Two Pointer 1차원 BFS/DFS 구현 재귀 Back Tracking Union-Find Divide and Conquer 그리디 정렬 기본 정렬 문제 Merge Sort Quick Sort 탐색 DFS/BFS Back Tracking 이분 탐색 Binaray Search Parametric Search 다이내믹 프로그래밍 기본 DP 2차원 DP 최장 증가 부.. 2022. 6. 16.
[알고리즘] Binary Search 이분탐색 - JAVA BinarySearch를 사용하면 검색 범위를 logN으로 엄청나게 단축시킬 수 있다. 만약 탐색할 범위가 너무 크다면 고려해봐야 한다. 특히 응용이라고 할 수 있는 최댓값, 최솟값을 찾아야 하는 이분 탐색을 이용하는 매개 변수 탐색 Parametric Search는 굉장히 유용하다. 주의할 점은 이분 탐색을 사용하기 이전에 탐색할 배열은 무조건 정렬되어있어야 한다. 이분 탐색은 기준 값과 가변 값을 통해 Start와 End를 결정한다. package Search.BinarySearch; public class BinarySearchTest { static int[] arr; public static void main(String[] args) { arr = new int[]{1,3,5,7,9,11,13.. 2022. 6. 9.
[알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm) [알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 출발지 -> 경유지 -> 목적지를 이용하여 최단 경로를 구하게 된다. 이 과정을 반복하게 되면 고정된 출발지에서 모든 edge의 최단 경로를 구할 수 있다. 필요 사항 우선 순위 큐 (순서대로 확인하는 것이 아닌, 거리가 가장 짧은 것부터 수행하기 때문에 수행 시간을 단축) 고정된 출발지에서 목적지까지의 경로 값 저장 배열 최소 비용을 만들기 위해 필요한 Node의 개수는 항상 3개라고 생각해야 한다. [출발, 경유, 목적] 출발지 -> 경유지, 경유지 -> 목적지로 따로 생각해야 한다. 경유지를 반복문을 돌리므로 목적지는 복수개다. 주목할 부분은 경유지 -> 목적지 인 부분이다. 목적지였던 부분이 다음.. 2022. 4. 20.
[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) [알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) 플로이드 워셜 알고리즘은 edge에서 edge로 이동할 때 최소비용을 구하는 알고리즘이다. 모든 경로의 최소비용을 구할 수 있다. 구현 플로이드 워셜 알고리즘의 구현은 간단하다. k, i, j를 사용하는 3중 for문이 있을 때 3중 for문으로 가장 바깥 k를 사용하는 for문은 edge의 총개수만큼 반복한다. k는 중간에 거쳐가는 edge이다. i는 시작 edge, j는 도착 egde로 사용한다. 현재 비용보다 거쳐가는 비용이 더 적다면 거쳐가는 비용을 사용한다. 자기 자신으로 가는 경로는 0, 도착이 불가능한 경로는 INF(충분히 큰 값)로 표시한다. 이해 구현은 간단하지만 이해는 쉽지 않았다. 플로이드 워셜 알고리.. 2022. 4. 17.
[JAVA] 알고리즘 DFS[Depth-First Search] 깊이 우선 탐색 [JAVA] 알고리즘 DFS [Depth-First Search] 깊이 우선 탐색 DFS [Depth-First Search]는 깊이 우선 탐색이며 깊이를 우선적으로 탐색합니다. 2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 깊이 탐색을 통해 방문하여 모든 노드를 탐색하는 방법입니다. BFS와 마찬가지로 모든 노드를 탐색하는 방법 중 하나입니다. DFS - 재귀, stack 자료 구조 활용 BFS - Queue 자료 구조 활용 DFS를 코드로 구현하기 위해선 3가지가 필요합니다. 탐색할 2차원 배열 또는 그래프 방문처리를 하기 위한 boolean type Stack 자료 구조 또는 재귀 함수 1 2 static boolean[] visited = new boolean[9]; /.. 2022. 3. 16.
[JAVA] 알고리즘 BFS[Breadth-First Search] 너비 우선 탐색 [JAVA] 알고리즘 BFS [Breadth-First Search] 너비 우선 탐색 BFS [Breadth-First Search]는 너비 우선 탐색이며 너비를 우선적으로 탐색합니다. 2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 주변을 순차적으로 방문하여 모든 노드를 탐색하는 방법입니다. 모든 노드를 탐색하는 알고리즘으로 깊이 우선 탐색을 하는 DFS와는 달리 Stack을 이용하지 않으며 Queue를 이용하여 전개할 수 있습니다. DFS - 재귀, stack 자료 구조 활용 BFS - Queue 자료 구조 활용 BFS를 코드로 구현하기 위해서 3가지를 우선적으로 구현해놓아야 합니다. 탐색할 2차원 배열 또는 그래프 방문처리를 하기 위한 boolean type Queue 자료.. 2022. 3. 16.

티스토리툴바