1. N-Queen 문제란? N-Queen 문제란 다음과 같이 (N * N) 체스판이 있을 때, N개의 퀸을 체스판에 놓을 수 있는 경우를 찾는 문제이다. 이 문제는 백트래킹(Back-Tracking) 알고리즘을 적용하는 전형적인 문제이다. 2. Back-Tracking 이란? 말 그대로 가능하지 않는 노드는 배제하고 뒤로 돌아가는 형태이다. 어떤 노드에 방문했을 때, 그 노드가 '유망한' 노드가 아니라면 그 전 상태로 돌아가는 것이다. 3. 풀이 코드 #include using namespace std; int n, cnt = 0; bool cols[15], incs[29], decs[28]; void nQueen(int r) { if (r > n) { cnt++; return; } for (int i..

1. 참고 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 2. 접근 방법 & 문제 풀이 문제의 입&출력을 이해하는 데에도 시간이 걸리는 문제이므로 정독하길 바란다. 간단하게 이 ..

1. 다차원 벡터 복사하기 3차원까지는 모르겠다만, 2차원 벡터는 다음과 같이 간단하게 복사할 수 있다. vector graph; graph.assign(5, vector(5, 1)); // 위의 벡터를 복사하려면... vector newGraph; newGraph.assign(graph.size(), vector(graph.size()); copy(graph.begin(), graph.end(), newGraph.begin());

C언어에서 scanf를 통해서 eof를 처리할 수 있듯이, C++에서도 입력받은 것이 eof인지 처리할 수 있다. int num; cin >> num; if (cin.eof() == true) { // Do something. }

1. 벨만-포드 알고리즘이란? 그래프에서 최단 경로를 찾는 알고리즘은 여러 개가 있기 때문에, 알고리즘이 필요할 때에는 각 상황에 맞는 적절한 최단경로 알고리즘을 선택해야한다. 널리 사용되는 최단경로 알고리즘으로는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있다. 특히, 다익스트라 알고리즘과 벨만-포드 알고리즘은 굉장히 많이 쓰이기 때문에, 다음과 같이 비교하면 좋다. 벨만-포드 알고리즘은 간선 간의 가중치가 음수일 때 사용한다. 다익스트라 알고리즘은 양수 가중치만 가능하다. 다익스트라 알고리즘은 정점을 기준으로 최단 경로는 찾고, 벨만-포드 알고리즘은 간선을 기준으로 찾는다. 2. 벨만-포드 알고리즘의 조건 벨만-포드 알고리즘을 적용하기 위한 조건은 다음과 같다. 최단 경로는 ..

1. 다익스트라 알고리즘이란? 알고리즘을 공부하다보면 그래프를 공부하는 것이 굉장히 중요하다는 것을 자주 느낄 것이다. 그 중에서도 DFS, BFS와 더불어 가장 기초적이면서도 중요하게 생각되는 것이 최단경로 알고리즘일 것이고, 그 중에서도 다익스트라 알고리즘은 한 노드에서 다른 노드로의 최단 거리를 계산하는 중요한 알고리즘이다. 2. 간단하게 구현하기 소제목이 '간단하게 구현하기'인 만큼 문제가 있는 코드라고 생각할 지도 모르겠다. 실제로 아래와 같은 구현은 시간복잡도에서 조금은 '복잡한 구현' 보다 불리한 면이 있다. 하지만 다익스트라를 처음 공부할 때, 이해를 위해서 이와 같은 방법을 꼭 알고 있는 것이 좋다고 생각한다. 이것이 '간단하게 구현하기'인 이유는 3번에서 서술하겠다. 다른 알고리즘들이 ..