개발(Dev) 이야기/Algorithm

[BOJ] N과M (1)_15649.cpp

//15649_N과M(1).cpp #include using namespace std; bool check[10]; int a[10]; void solve(int idx, int n, int m) { if (idx == m) { for (int i = 0; i < m; i++) { cout M; solve(0, N, M); return 0; }

DFS(Depth-First Search)와 BFS(Breadth-First Search)

DFS (깊이 우선 검색) inorder preorder post order DFS는 위 그림과 같이 깊이를 먼저 고려하여 탐색하는 과정이다. STACK을 이용해서 구현이 가능하다. BFS(넓이 우선 검색) Level 단위로 검색 QUEUE를 이용해서 구현

Dijkstra Algorithm

다익스트라 알고리즘(Dijkstra Algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 기본 로직은 출발점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다. 위와 같은 그래프가 있다고 가정하며 출발점은 1번 정점이다. 이 중에서 경로가 가장 짧은 정점을 고르면 2, 3번 점이 된다. 2번 점부터 확인해보면, 2번 점의 최단 거리를 가지고 있는 현재 최단거리 (INF)와 1번 점의 최단거리(0) + 1~2번의 가중치(4) 값 중 가장작은 값으로 갱신한다. 코드로 만들면 다음과 같다. --> dist[2] = min(dist[2],dist[1]+adj[1][2]) 따라서 min(INF, 4)이..