이분 탐색 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다.배열의 원소가 정렬되어있어야만 사용할 수 있다. 사용하는 상황 1) 특정 배열 안에 원소 x가 존재하는지 확인해야할 때 2) x이하, 또는 x이상의 원소가 몇 개 존재하는지 확인해야할 때 3) x와 가장 가까운 원소가 무엇인지 확인해야할 때 코딩테스트에서의 사용 상황 탐색 범위가 큰 상황에서 사용해라!1) 탐색 범위가 2000만을 넘어가는 상황2) 처리해야할 데이터의 개수나, 값이 1000만 단위 이상으로 넘어가는 상황-> 이진탐색과 같이 O(log N)의 속도를 갖는 알고리즘으로 처리해야함을 기억해야한다. 알고리즘 1. 탐색하고자 하는 배열을 오름차순 정렬한다 array.sorted() 2. start, end를 변수에 저장한다. a...
DFS / BFS DFS BFS 탐색 방법 깊이 우선 탐색 (시작 노드 선택은 자유롭지만, 관행적으로 번호가 낮은 순서부터 처리한다.) 너비 우선 탐색 (가까운 것 먼저) 자료구조 / 구현 방법 스택 자료구조 개념 재귀함수를 이용해 구현하면 간결 큐 자료구조 개념 큐를 이용해 구현 시간복잡도 O(N) O(N) -실제 수행 시간이 DFS보다 좋다. DFS (Depth-First Search) 1. 탐색 시작 노드를 스택에 삽입 후 방문 처리한다. 2. 최상단 노드의 인접 노드를 확인한다. a. 인접노드 중 최상단 노드에 방문하지 않은 노드가 있다면 스택에 삽입 후 방문처리한다. b. 방문하지 않은 노드가 없다면, 최상단 노드를 스택에서 꺼낸다. 3. 모든 노드를 방문할 때 까지 2번 과정을 반복한다. BF..
부르트 포스 (Brute Force) - 모든 경우의 수를 파악해야할 때 사용한다. [완전 탐색] - 경우의 수를 만들기 위한 방법을 작성해야한다. (순열, 재귀, 비트마스크 등) 알고리즘 1. 부르트 포스 문제가 맞는지 확인한다. a. 문제가 모든 경우의 수를 파악해야하는 경우 b. 입력되는 데이터의 범위가 작고, 시간 제한이 꽤 긴 편이다. - [1초 당 연산 횟수] O(N) = 1억 O(NlogN) = 500만 O(N^2) = 1만 O(N!) = 11 2. 어떤식으로 경우의 수를 만들지 결정하기 (순열, 재귀, 비트마스크 등) a. 단순한 문제 => 반복문 사용 b. 사전성(순서) 확인 => 순열 사용 c. 가지치기를 하는 경우 => 재귀 - 중간에 답이 아닌 것이 확실해지는 것이 한 무더기 생기는..
- Total
- Today
- Yesterday
- 16진수 입력
- Swift
- ord
- python
- 파이썬
- 리플릿
- 백준
- 레플릿
- 프로그래머스
- 이것이 코딩테스트다
- 반복문
- 깃허브
- Code up
- 정답
- COMMIT
- 코드 업
- 깃
- 설명
- CHR
- level1
- 시간초과
- for문
- SwiftUI
- baekjoon
- replit
- do while
- 코드업
- CodeUp
- 부르트포스
- 기초 100제
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |