본문 바로가기

Algorithm💻/study2

[Algorithm] DFS, BFS DFS (Depth-First-Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘을 말한다. 스택 자료 구조(혹은 재귀 함수)를 이용한다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼낸다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. DFS 동작 예시 [Step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접 노드부터) 시작 노드 : 1 [Step 1] 시작 노드인 '1'을 스택에 삽입하고 방문 처리한다. [Step 2] 스택의 최상단 노드인 '1'에 방문하지 않.. 2022. 11. 15.

[Algorithm] 다이나믹 프로그래밍 현재 코딩테스트 준비를 하는 과정에서 다이나믹 프로그래밍에 관련된 문제를 풀다가 한번 정리를 해보는 것이 좋다고 생각이 들었다. 이에, 다이나믹 프로그래밍(Dynamic Programming)기법이라고 하는 동적 계획법에 대해 정리해보고자 한다. Dynamic Programming, 동적 계획법 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 해결하고자 하는 문제들의 중복 여부를 확인해볼 것 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장함 탑다운(Top-Down) 방식 다이나믹 프로그래밍으로 해결할 수 .. 2022. 11. 11.

이전 1 다음

티스토리툴바