BFS (너비 우선 탐색) 트리나 그래프를 탐색하는 방법으로 시작 정점에서 가장 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법이다. BFS를 구현할 때는 Queue를 활용하는데 왜 Queue를 쓰는지 아래의 과정을 통해 알아보자. BFS 탐색 과정 1. 루트 노트 방문 2. 큐에서 A를 제거 후 방문 처리, 다음 인접 노드들 큐에 삽입 3. queue 에서 요소 하나 pop(B) 후 방문 처리, B의 인접 노드 큐에 삽입 4. queue 에서 요소 하나 pop(C) 후 방문 처리, C의 인접 노드 큐에 삽입 5. queue 에서 요소 하나 pop(D) 후 방문 처리, D의 인접 노드 큐에 삽입 6. queue에서 남아있는 요소들을 위와 같은 방법으로 방문 및 표시하면서 큐가 완전히..
순차 탐색 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 데이터 크기에 따라 효율이 다르기 때문에 데이터가 많다면 비효율적인 방법 최악 : O(n) 이진 탐색 데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 비교할 때마다 탐색 범위를 반으로 줄이면서 특정한 값의 위치를 찾는다 분할 정복 알고리즘 - 리스트 개수 0,1개일 때 처리하고 2개 이상일 때 재귀 호출로 구현 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료 (mid=key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key) 중간 값보다 검색 값이 작다면 중간값 기준 배열의..
재귀호출 함수안에서 동일한 함수를 호출하는 방식 시간복잡도 : O(n) 스택 기반 방식 동적계획법, 분할 정복 DP : 입력 크기가 작은 부분 문제들을 해결후 memoization 기법을 사용해 보다 큰 크기의 문제를 해결, 상향식 분할 정복 : 문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘, 하향식 공통점 : 문제를 잘게 쪼갬 차이점 : 동적 : 상위 문제 해결시 재활용, 부분 문제 중복 분할 : 부분 문제를 서로 중복되지 않음 재귀호출은 계속 계산하지만 DP는 이전 계산한 값을 저장하기 때문에 계속 쓸 수 있다. 시간복잡도 비교적 나아진다. 대신 공간 복잡도는 희생된다
