다락방

알고리즘DFS루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법스택 or 재귀함수를 통해 구현한다.모든경로를 방문해야 할 경우 사용에 적합하다.시간복잡도인접 행렬 : O(V^2)인접 리스트 : O(V+E)V(Vertex) : 정점, E(Edge) : 간선BFS루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법큐를 통해 구현한다.최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합하다.시간복잡도인접 행렬 : O(V^2)인접 리스트 : O(V+E)동적 계획법(Dynamic Programming)복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다.똑같은 연..

17130 토끼가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17130 17130번: 토끼가 정보섬에 올라온 이유 첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반 www.acmicpc.net #include using namespace std; int n, m, startY ,ans = 0; string s; int dp[1001][1001] = { 0, }; char _map[1001][1001]; bool check = false; void move() { for (int j = startY; ..

1003 피보나치 함수 #include using namespace std; int fibo(int num); int check_zero = 0, check_one=0; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int test_case; cin >> test_case; for (int i = 0; i > tmp; fibo(tmp); cout

동적계획법(DP : Dynamic Programming) 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다. 구현단계 문제를 하위 문제로 쪼갠다 하위 문제를 재귀적으로 해결한다 결과를 저장한다(메모이제이션, 테블레이션) 저장된 결과를 이용해 큰 문제를 해결한다. 동적 계획법 조건 최적부분구조(Optimal Substucture) 전..