코딩 헬스장

그래프를 탐색하는 방법은 DFS, BFS가 있다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. 1. DFS (깊이 우선 탐색) 최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없으면 옆으로 이동하여 같은 방법으로 탐색 모든 노드를 방문하고자 하는 경우 이 방법을 선택 BFS(너비 우선 탐색)보다 좀 더 간단하다는 장점이 있음 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느림 스택 또는 재귀 함수로 구현 2. BFS (너비 우선 탐색) 최대한 넓게(인접한) 탐색한 후 더 이상 갈 곳이 없으면 아래로 이동하여 같은 방법으로 탐색 주로 두..

1. 이진(이분) 탐색 이진 탐색이란 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 정렬되어 있는 리스트에서 찾으려는 데이터와 중간 위치의 데이터를 비교하며 탐색 범위를 절반씩 좁혀거며 데이터를 찾는 방법으로, 배열 데이터가 정렬되어 있어여만 사용할 수 있는 알고리즘이다. 시간 복잡도는 아래와 같다. 전체 데이터의 수를 N이라고 가정했을 때 1) 첫 번째 탐색 후 절반만 남아 남은 수가 \( \frac{N}{2} \) 개 2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 \( \frac{N}{2} \) * \( \frac{1}{2} \) 개 3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 \( \frac{N}{2} \) * \( \frac{1}{2} \) * \( \frac{1}..

1. 조합 조합의 경우에는 순서가 중요하지 않기 때문에 중복되는 것을 빼고 뽑는다. ex) 1,2,3,4 숫자를 이용한 조합 => [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] 2. 순열 순열의 경우 순서가 중요하기 때문에 중복되는 값([a,b], [b,a]과 같은 값들)이 있어도 다 뽑는다. 순서를 고려한다는 것은 순서가 바뀌면 다른 것으로 취급함을 의미한다. ex) 1,2,3,4 숫자를 이용한 순열 => [1,2], [1,3], [1,4], [2,1], [2,3], [2,4], [3,1], [3,2], [3,4], [4,1], [4,2], [4,3] 3. 요약 4. 구현 아래 코드로 순열, 중복순열, 조합, 중복조합을 만들 수 있다. function getCombinatio..