나다김강니

BFS 너비 우선 탐색너비 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. -> DFS와 공통점시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘FIFO 탐색큐 자료구조 이용한다.목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.시간 복잡도 : O(V+E) V: 노드 수, E: 에지 수💡  BFS의 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화한다.visit배열을 사용하고 인접리스트를 사용하는 것은 DFS와 같다. 하지만 BFS는 스택이 아닌 큐를 사용한다.  2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기큐에서 노드를 꺼내면서 해당 노드와 인접 노드를 큐에 삽입한다.   3. 큐 자료구조에 값이..

DFS 깊이 우선 탐색깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다.시작 노드에서 출발하여 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해서 탐색을 수행한다.재귀 함수로 구현 -> 스택 오버플로를 유의해야한다.스택 자료구조 이용한다.(FILO)단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 등의 문제를 풀 때 사용한다.DFS는 한 번 방문한 노드를 다시 방문하면 안된다. 그렇기 때문에 노드 방문을 체크할 배열이 필요하다.시간 복잡도 : O(V+E) V: 노드 수, E: 에지 수💡  DFS의 핵심 이론1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화한다.(여기서는 인접리스트) 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 3. 스택 ..

병합 정렬 : O(nlogn)분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘이다.병합과정이 총 logn만큼 일어난다.각각을 병합하는 과정은 n의 시간이 걸린다.(아래 설명)💡 2개의 그룹을 병합하는 과정투 포인터 개념을 사용해서 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 배열에 추가하고 포인터를 오른쪽으로 이동시킨다.이렇게 2개의 그룹을 병합하는 과정이 시간이 N만큼 걸린다.  1517 : 버블 소트문제N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수..

삽입 정렬(Insertion Sort) : O(n2)이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬 1️⃣  현재 index에 있는 데이터 값을 선택한다.2️⃣  현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.3️⃣  삽입 위치부터 Index에 있는 위치까지 shift연산을 수행한다.4️⃣  삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산을 수행한다.5️⃣  전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.6️⃣  비교 대상이 없을 때까지 1️⃣ ~ 5️⃣ 를 반복한다.☝🏻 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.      O(..