IT지식/알고리즘4 [알고리즘] 이분탐색 알고리즘 문제 풀이하면서 이분탐색 알고리즘이 자주 사용되는 경우가 있어서 정리해놓으려고 한다. 이분 탐색이란? 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 배열 내부의 데이터가 정렬되어 있어야하만 할 수 있는 알고리즘이다. 변수 3개(low, high, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 이분탁샌의 구현? 탐색의 대상이 되는 자료들이 정렬되어 있어야한다. low와 high값에 의거해 중간값 mid 값은 (low + high) / 2 이다. arr[mid]값과 구하고자 하는 key값을 비교한다. : key > mid : 구하고자 하는 값이 중간값보다 높다면 l.. 2022. 12. 26. [알고리즘] 백트래킹에 대해 공부해보자 DFS? DFS는 끝이 나올 떄까지 한 방향으로 탐색하는 방식으로, 방향을 잘못 선정할 시 큰 손해를 볼 수 있다. Back Tracking : 해당 방향에 답이 없다고 판단되면, 되돌아가서 다른 방향을 탐색하는 기법 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로만 가는 의미이다. 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기를 하는 것이 백트래킹이다. 문제 풀이에서 활용할 때는, DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고,.. 2022. 12. 19. [알고리즘] Comparator 와 Comparable 기록용 참고: https://gmlwjd9405.github.io/2018/09/06/java-comparable-and-comparator.html [Java] Comparable와 Comparator의 차이와 사용법 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io Comparable과 Comparable 모두 인터페이스이다. 그러므로, 사용하고자 한다면 인터페이스 내에 선언된 메소드를 반드시 구현해야한다. Comparable 인터페이스는 compareTo 메소드를 구현해야하고, Comparator 인터페이스를 쓰려면 compare 메소드를 구현해야 한다. 역할은 비슷하지만 차이가 있다. Comparable의 compar.. 2022. 12. 12. [알고리즘] DFS, BFS 구현 (백준) BFS, DFS 둘다 모두 그래프를 탐색하는 방법이다. DFS 깊이 우선 탐색 (Depth-First Search) 1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다. 3. 검색 속도 자체는 너비 우선 탐색에 비해서 느리다. BFS 너비 우선 탐색 (Breadth-First Search) 1. 주로 최단 경로를 찾고 싶을 때 이 방법을 사용한다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { static int[][] check; //간선 상태 확인 static boolean [] visit; //방.. 2022. 11. 29. 이전 1 다음