[Binary Search] 이진 탐색은 오름차순으로 정렬된 배열을 기반으로 원하는 값을 찾을 때 사용하는 탐색 방법 중 하나이다. 만약 1부터 10까지 정렬된 배열에서 3을 찾고 싶다면, 가운데 mid값을 기준으로 mid값보다 3이 작다면 왼쪽 영역에서, 크다면 오른쪽 영역에서 3을 찾는다. 해당역역에서 다시 가운데 mid값을 찾아서 3과 비교해 영역을 나눠가며 비교의 범위를 절반씩 줄여 나갈 수 있게 된다. 한번 비교할 때마다 범위가 절반씩 줄어들기 때문에 시간복잡도가 O(logN)이다. [구현] class BinarySearch { public static void main (String[] args) { int[] arr = {1,2,3,4,5,6,7,8,9,10}; System.out.print..
[위상 정렬이란?] 여러 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것을 말한다. 먼저 위상 정렬을 하기 위해서는 자료들을 순서에 맞게 그래프로 표현해야 한다. 위상 정렬 알고리즘이란 그래프 상의 정점들을 순서에 맞게 나열하는 것이다. 그래프 상의 간선의 방향이 정점들의 순서를 나타낸다. 만약 A가 B를 가리키면, A가 B보다 먼저 앞선다는 뜻이다. 그래프에서는 진입차수와 진출차수라는 개념이 있다. 진입차수는 밖에서 한 정점으로 들어오는 간선의 수이고 진출차수는 한 정점에서 나가는 간선의 수를 말한다. [위상 정렬 과정] 1. 진입차수가 0인 정점과 이와 연결된 모든 간선을 지운다. 2. 남아있는 정점의 진입차수를 갱신한다. 3. 그래프에 모든 정점이 없어질때까지 1과 2과정을 반복한다. 1번..
- Total
- Today
- Yesterday
- 이진 탐색
- 13460
- 위상정렬
- parametric search
- lottie
- 2048 game
- mybatis
- 째로탈출2
- 12100
- acmpicpc
- 1157
- 이진 검색
- 7576
- 단어 공부
- acmicpc
- 조합 알고리즘
- Java
- 알파벳 찾기
- spring
- 알고리즘
- 자료구조
- 1085
- BOJ
- ACM Craft
- 약수
- 7569
- combination
- 1037
- 10809
- 파라메트릭
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |