이진 탐색이란?'정렬된 배열(리스트)'에서 탐색 범위를 절반으로 줄여가며 특정 값을 찾는 알고리즘탐색할 때마다 탐색 범위가 절반으로 줄어들기 때문에 '탐색해야 할 데이터의 양이 많을수록 유리'동작 방식동작 방식정렬된 배열의 중간 값을 찾아서 목표 값과 비교한다.목표 값보다 작다면 왼쪽 절반을 탐색하고 크다면 오른쪽 절반을 탐색한다.목표 값과 중간 값이 같을 때까지 위 과정을 반복한다.구현 방법반복문 이용한 방법정렬된 배열의 첫 번째 인덱스를 low로 선언하고 마지막 인덱스를 high로 선언한다.while문을 이용하여 high가 low보다 크거나 같을 때까지 아래 탐색을 실행한다.중간 인덱스(mid)와 중간 값(midValue)를 구한다.중간 값 > 목표 값이라면 왼쪽 배열을 탐색한다.중간 값 이라면 오른..

다이나믹 프로그래밍이란하나의 큰 문제를 여러 개의 작은 문제로 나누어 풀면서 그 결과를 저장해 나가며 큰 문제를 해결할 때 재활용하는 것을 의미한다.DP 사용하는 이유일반적인 재귀 함수의 불필요한 중복 연산을 줄이기 위해 동적 계획법을 사용한다.일반적인 재귀를 사용하면 동일한 작은 문제를 여러 번 반복 하여 계산하기 때문에 비효율적이다.DP는 동일한 작은 문제를 저장(Memoization)해두고 나중에 같은 문제가 나오면 재활용하여 중복 연산을 피할 수 있기 때문에 일반적인 재귀 함수에 비해 효율적으로 계산할 수 있다.피보나치 수열 예시D[12]가 세 번이나 반복해서 계산되었다. 이때 DP를 사용하면 D[12]를 한 번만 계산하고 저장한 후 나중에 재활용하여 사용하기 때문에 훨씬 효율적으로 계산할 수 있..

DFS(Depth First Search)란?한 경로를 끝까지 탐색한 후, 이전 경로로 돌아가서 다른 경로를 탐색하는 방법이다.DFS에서 사용하는 알고리즘은 백트래킹(backtracking) 알고리즘이다. 백트래킹이란 해를 찾아가는 도중 지금 가는 경로가 해가 아니라면 왔던 경로로 되돌아가는 것을 의미한다. 즉, 트리의 마지막 노드에 도달했을 경우 이전 노드로 되돌아가서 새로운 경로를 찾는 것을 의미한다.재귀 함수와 스택을 이용하여 구현한다. 재귀를 이용할 경우 종료 조건을 명시해서 무한 반복에 빠지지 않게 해야 한다.딱 두 가지만 생각하면 된다.DFS 탐색 과정한 경로를 끝까지 탐색한다.마지막 노드에 도달했다면 이전 노드로 돌아가서(backtracking) 탐색하지 않은 노드가 있는지 확인한다.탐색하지..

BFSBFS(Breadth First Search)는 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법이다. 즉, 시작 정점으로부터의 거리가 가까운 정점들부터 차례로 방문해 나가는 방법이다.BFS 특징큐(Queue) 자료구조를 사용하여 구현한다.각 노드들을 방문하면서 방문한 노드와 연결된 노드를 큐에 추가하고 빼면서 한 번씩 탐색한다.회색 노드(큐에 추가), 검정 노드(큐에서 삭제)노드 방문 여부를 체크하지 않으면 무한 반복에 빠질 위험이 있기 때문에 반드시 체크해야 한다.BFS 문제 유형최단 경로 탐색미로 찾기2차원 배열로 주어진 미로에서 시작점에서 출발해 출구까지의 최단 경로 찾기특정 거리 내 노드 탐색소셜 네트워크 탐색특정 거리 내에 있는 친구 찾기전염 확산 모델링전염병이 특정 거리 내에 얼마..

그리디 알고리즘이란?매 선택에서 당장 최적의 답을 선택하여 결과를 도출하는 기법이다.즉, 백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 최적의 선택을 하고 선택했다면 더 이상 다른 선택은 검증하지 않는 것을 의미한다.그리디 알고리즘 문제점당장 현재 최적의 선택을 한다면 전체적으로는 최적이 아닐 수 있다는 문제가 있다.A에서 다음 단계로 갈 때 당장의 최적 값은 A -(1)-> C이고 C에서 다음 단계로 가는 최적의 방법은 C -(150)-> E이다.이렇게 당장 현재의 최적의 선택만 고려한다면 전체적으로 볼 땐 최적의 선택이 아닐 수 있다는 것이다.그럼에도 불구하고 그리디 알고리즘은 속도가 매우 빠르기 때문에 자주 사용될 수 있다. 하지만 항상 최적해가 되지 않으므로 특수한 조건을 만족해야 사용할 ..

완전 탐색이란?완전 탐색이란 말 그대로 모든 경우의 수를 다 만들어보고 답을 찾는 방법이다.만약 자물쇠의 비밀번호가 3자리라면 000 ~ 999까지 최대 1000번의 경우의 수를 만들어 정답을 찾을 것이다.이러한 완전 탐색 방법은 최적의 해를 찾을 수는 있지만 시간 복잡도와 공간 복잡도가 너무 커서 입력 값이 작을 때 주로 사용한다.완전 탐색 종류완전 탐색은 아래 사진과 같이 7가지 알고리즘이 존재한다.브루트 포스(Brute Force)발생할 수 있는 모든 경우를 탐색하는 방법이다.시간 복잡도가 매우 커질 수 있기 때문에 주로 가능한 경우가 적고 완전 탐색으로 충분히 빠르게 해결할 수 있는 기초적인 문제에서 사용한다.주로 반복문과 조건문으로 모든 경우를 탐색하거나 재귀를 이용하여 구현한다.반복문아래 코드..