Python15 너비 우선 탐색 그래프를 완전 탐색하는 방법 중 하나. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.기능: 그래프 완전 탐색특징: FIFO 탐색, Queue 자료구조 이용시간 복잡도 (노드 수: V, 엣지 수: E): O(V+E)선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다. BFS라고 부른다.핵심 이론(1) BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기방문했던 노드를 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 리스트가 필요하다. 그래프를 인접 리스트로 표현한다. DFS와의 차이점으로는 스택이 아닌 큐를 사용한다는 점.(2) 큐에.. 2026. 3. 21. 백트래킹 문제를 해결하는 탐색 기법이다. 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도하는 알고리즘이다.재귀 함수로 구현가지치기로 성능 향상시간 복잡도 (N: 분기 수, d: 탐색 깊이) - O(N^d)백트래킹은 일반적으로 재귀 함수 형태로 구현하며 깊이 우선 탐색 개념과 구현 방식이 유사하다. 가장 큰 특징은 가지치기로 유효하지 않은 경로를 조기에 배제하여 탐색 범위를 줄이고 성능을 높일 수 있다.차이점은 DFS가 모든 노드를 탐색하는 것을 목적으로 하는 반면, 백트래킹은 조건을 만족하는 해를 찾기 위해 불필요한 경로는 조기에 차단하며 효율적으로 탐색한다는 점이다. 백트래킹을 활용할 수 있는 대표적인 문.. 2026. 3. 6. 깊이우선탐색; DFS (Depth-First-Search) DFS: depth-first search그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘.시간 복잡도는 - 노드 개수 (V), 에지 개수 (E)기능: 그래프 완전 탐색특징재귀 함수로 표현스택 자료구조 이용시간 복잡도: O(V+E)재귀 함수를 이용하므로 stack overflow에 유의해야 한다. 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등에 활용할 수 있다.깊이 우선 탐색의 핵심 이론DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 리스트가 필요하다. 그래프는 인접 리스트로 표현한다. 그리고 DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용해서 설명한다.사.. 2026. 2. 23. 정렬 - 퀵 정렬, 병합 정렬, 기수 정렬 퀵 정렬기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘.기준값을 어떻게 선정하는지가 시간 복잡도에 많은 영향을 미치는데, 평균적인 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)가 된다.기준값은 pivot이라고 부른다.퀵 정렬의 핵심 이론pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬한다. 퀵 정렬 과정데이터를 분할하는 pivot을 설정한다. (가장 오른쪽 끝)pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리한다.start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한.. 2026. 2. 13. 선택 정렬, 삽입 정렬 선택 정렬최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법.구현 방법이 복잡하고, 시간 복잡도도 O(n^2)로 효율적이지 않아 많이 사용하지 않는다.핵심 이론최솟값/최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것. 선택 정렬 과정남은 정렬 부분에서 최솟값/최댓값을 찾는다.남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬 부분의 범위를 축소한다.전체 데이터 크기만큼 index가 커질 때까지, 남은 정렬 부분이 없을 때까지 반복한다.삽입 정렬이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식.핵심 이론선택 데이터를 현재 정렬된 데이터 범위.. 2026. 2. 7. 버블 정렬 버블정렬: 데이터의 인접 요소끼리 비교하고 swap 연산을 수행하며 정렬하는 방식선택정렬: 대상에서 가장 크거나 작은 데이터를 찾아 선택하는 과정을 반복하면서 정렬하는 방식삽입정렬: 대상을 선택하여 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식퀵정렬: pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식병합정렬: 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식기수정렬: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식버블 정렬시간 복잡도는 O(n^2)로 다른 정렬 알고리즘보다 속도가 느린 편.버블 정렬 과정비교 연산이 필요한 루프 범위 설정인접한 데이터 값 비교swap 조건에 부합하면 swap 연산을 수행루프 범위가 끝날 때까지 2~3 반복정렬된 .. 2026. 1. 29. 이전 1 2 3 다음
