본문 바로가기

컴퓨터 과학(CS)/알고리즘

 (4)
[알고리즘] 그래프 탐색: DFS, BFS 그래프 탐색 알고리즘 중 가장 기본이 되는 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)에 대해 알아보겠습니다. 트리 구조에서 탐색이 어떻게 이루어지는 지를 통해 소개하겠습니다. 동작 설명을 위해 트리 구조에서 하는 것일 뿐 그래프 종류와 관련없이 사용 가능합니다.DFS(깊이 우선 탐색)이란?DFS는 그래프의 한 노드에서 시작해 가능한 깊이까지 탐색을 진행한 뒤, 더 이상 갈 수 없을 때 다음 경로를 탐색하는 방식입니다. 재귀나 스택을 사용하여 구현할 수 있으며, 후입선출(LIFO) 구조를 따릅니다.DFS의 동작 방식시작 노드를 방문하고, 방문 처리를 합니다.방문하지 않은 인접 노드가 있다면 그 노드로 이동합니다.더 이상 방문할 노드가 없으면 이전 노드로 돌아갑니다. DFS를 통해 트리를 구성한다면..
[알고리즘] 재귀(Recursion) 재귀란?재귀는 자기 자신을 호출하는 프로그래밍 기법입니다. 큰 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘이라 할 수 있습니다.재귀 함수는 호출될 때 스택 구조를 사용합니다.각 함수 호출로 인해 콜 스택에 쌓이고, 함수가 종료되면 제거됩니다.재귀의 기본 구조재귀 함수가 자기 자신을 무한히 호출하면 콜 스택이 계속 쌓이게 됩니다. 결국에는 멈추는 지점이 필요합니다. 이 지점을 기저 조건(Base Case)라 부릅니다.재귀 함수를 구성하는 데 필수적인 구성 요소는 다음과 같습니다. 기저 조건(Base Case):재귀 호출을 멈추는 조건입니다.기저 조건을 명확히 정의하지 않으면 무한 루프에 빠질 수 있습니다.재귀 호출(Recursive Call):자기 자신을 다시 호출하는 부분입니다.아래는 재귀 함수..
[알고리즘] 위상정렬(Topology Sort) c++ 위상정렬(Topology Sort)이란?위상정렬은 사이클이 없는 방향 그래프(DAG)에서 작업의 순서(조건)가 정해져 있는 경우 전체 작업들의 순서를 정렬하는 알고리즘이다. 방탈출 게임을 예시로 설명하겠다.위 그래프를 보면 1번문 열쇠3을 얻기 위해서는 1번문 열쇠1, 열쇠2가 필요하다. 1번문을 열기 위해서는 1번문 열쇠1, 열쇠2, 열쇠3이 모두 필요하다. 탈출을 하기 위해서는 1번 문을 통과해야 하고, 탈출 열쇠를 얻어야 한다. 탈출 시나리오는 다음과 같다. 1. 시작 2. 열쇠1 또는 열쇠2를 얻는다. 3. 남은 열쇠1 또는 열쇠2를 얻는다. 4. 열쇠1과 열쇠2를 통해 열쇠3을 얻는다. 5. 열쇠1, 열쇠2, 열쇠3을 이용해 1번 문을 통과한다. 6. 탈출 열쇠를 얻는다. 7. 탈출 이렇듯 열쇠..
[알고리즘] LCA(최소 공통 조상) (c++) LCA(Lowest Common Ancestor)란?LCA 알고리즘은 임의의 두 정점(u, v)에서 가장 가까운 공통 조상을 찾는 알고리즘이다.  아래 예시를 보면 쉽게 이해할 수 있을 것이다. 위와 같은 트리가 있을때 14, 16 정점의 LCA는 정점 1이다. 정점 14의 조상 정점들은 순서대로 9, 5, 2, 1이 있다. 정점 16의 조상 정점들은 순서대로 12 7, 3, 1이 있다.정점 14, 16이 함께 공유하는 가장 가까운 조상은 정점 1이 된다. 정점 8, 14의 LCA를 구하면 정점 2가 된다. 정점 8의 조상 정점들은 순서대로 4, 2, 1이 있다. 정점 14의 조상 정점들은 순서대로 9, 5, 2, 1이 있다.정점 8, 14이 함께 공유하는 가장 가까운 조상은 정점 2가 된다. 이번엔 정..

티스토리툴바