🔻Algorithm/basic

❗이분 탐색이분 탐색이란 정렬된 리스트 안에서 탐색 범위를 절반씩 줄여가며 원하는 값을 찾을 때까지 탐색하는 알고리즘이다 ❗동작 방식사전에 정렬된 리스트에서 39를 찾고자 한다. 1. start = 0, end = 9로 시작하여 두 값의 mid를 찾으면 인덱스 4가 된다.data[4]가 가리키는 값이 20이므로 39보단 작기 때문에 start의 위치는 인덱스 4보다 1 더 큰 곳으로 변경한다.2. start = 5, end = 9로 다시 탐색하면 mid는 인덱스 7이 된다.data[7]이 가리키는 값은 타켓인 39와 동일하기 때문에 탐색이 종료된다.이런 방식으로 target보다 현재 값이 작으면 start값을 변경하고, 크다면 end값을 변경한다. ❗파이썬 구현이분 탐색은 반복문과 재귀 2가지 방식으로 ..

❗BFS너비 우선 탐색이라는 그래프 탐색 기법으로 시작 노드에서 연결된 자식 노드를 모두 탐색 후 다시 자식 노드가 부모 노드가 되어 이 부모 노드의 자식 노드를 넓게 탐색하는 방식이다BFS를 구현하는 방식으론 큐를 이용한다. ❗동작 방식위와 같은 그래프가 있고, 1번 노드에서 시작하여 탐색하고자 한다.손으로 BFS를 풀 때는 1 -> 3 -> 2까지 탐색 후 다음 방문 노드는 3번 노드의 자식 노드인 6번과 4번이 된다.1 -> 3 -> 2 -> 6 -> 4 다음엔 2번 노드의 자식 노드인 5번을 방문하고1 -> 3 -> 2 -> 6 -> 4 -> 5 순서로 그래프 탐색을 완료할 수 있다. ❗파이썬 구현위의 케이스를 파이썬 코드로 구현한 것이다.graph = [[],[3,2],[3,1,4,5],[6,4..

❗DFS깊이 우선 탐색이라는 그래프 탐색 기법으로 시작 노드에서 가장 깊숙히 들어가서 노드를 탐색한 후 다시 상위 노드로 이동하여 다른 루트를 탐색하는 방식이다.DFS를 구현하는 방식으론 스택과 재귀 호출이 있는데 해당 포스트에선 재귀 호출로 설명하고자 한다! ❗동작 방식위와 같은 그래프가 있고, 1번 노드에서 시작하여 탐색하고자 한다.손으로 DFS를 풀 때는 1 -> 3 -> 6까지 탐색 후 더이상 나아갈 노드가 없기 때문에 3번 노드까지 거슬러 올라오게 된다.그 후 3번의 자식 노드 중 방문하지 않은 4를 방문하고 이어서 탐색하면결국 DFS의 방문 노드 순서는 1 -> 3 -> 6 -> 4 -> 2 -> 5이 된다. ❗파이썬 구현위의 케이스를 파이썬 코드로 구현한 것이다.graph = [[],[3,2..