Algorithm 개념 정리 썸네일형 리스트형 Topological Sorting(위상 정렬)의 개념, 구현 방법 DAG (Directed Acyclic Graph) 사이클이 없는 방향 그래프 ex) 작업들의 우선순위, 학과 선수과목, 라면 끓이기 Topological Sorting(위상 정렬) DAG에서 모든 정점을 순서대로 정렬 정렬 기준: 모든 간선(Vi, Vj)에 대해 Vi가 Vj보다 앞에 위치 위상 정렬 구현 1) 진입 간선이 0인 노드부터 순서대로 탐색하는 방법 #include #include #include using namespace std; int n, m; // n: 노드, n: 정점 int s, e; // s: 시작지점 e: 끝지점 vector adjArray; vector inDeg; // 진입간선의 수 queue q; // 진입간선이 0인 노드를 저장하는 큐 vector A; // 결과값 저장.. 더보기 BFS/DFS 알고리즘 개념 정리 DFS (Depth-First Search) 깊이 우선 탐색 : 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수 이용 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 2. 인접 노드 스택에 넣고 방문 처리 2-1) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 2-2) 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 BFS (Breadth-First Search) 너비 우선 탐색 : 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조 이용 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문.. 더보기 브루트 포스(Brute Force) 브루트 포스(Brute Force)란? 난폭한(Brute) 힘(Force) 모든 경우의 수를 무식하게 탐색하여 요구 조건에 충족되는 결과만을 가져오는 알고리즘으로, 전체 탐색, 완전 탐색이라고도 불린다. 브루트 포스(Brute Force)의 장점 알고리즘을 설계하고 구현하기 쉽다. 브루트 포스(Brute Force)의 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 사용이 매우 비효율적이다. 브루트 포스(Brute Force) 알고리즘 구현 방법 1. for/while loop 이용 2. 재귀 함수 이용 브루트 포스(Brute Force) 문제 2022.07.25 - [Algorithm 문제 풀이/python] - [python] 백준 2309번 일곱 난쟁이 [python] 백준 2309번 일곱 .. 더보기 다이나믹 프로그래밍 Dynamic Programming 다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행 시간 호율성을 비약적으로 향상시키는 방법 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 구조 2. 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결할 수 있는 문제 다이나믹 프로그래밍 구현 방식 TopDown(탑다운) & BottomUp(보텀업) TopDown(탑다운, 하향식) 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 큰 문제의 답까.. 더보기 이전 1 다음
