본문 바로가기

알고리즘90

BOJ 11780 - 플로이드2 플로이드 와샬 알고리즘을 사용하는 문제. #include #include #include using namespace std; typedef unsigned long long ll; const int INF = 1e9; int dist[101][101]; int via[101][101]; int ks[101][101]; void reconstruct(int i, int j, vector& path) { //i->j 경유없이 가는 경우면 if (via[i][j] == -1) { path.push_back(i+1); path.push_back(j+1); return; } //i->j 경유점이 있다면 int w = via[i][j]; //w에 경유점 담아주고 reconstruct(i, w, path); pat.. 2019. 7. 29.
BOJ 9663 - N QUEEN 저번에 마구잡이로 풀어봤지만 백트래킹 연습으로 한 번 더 풀어봤다. 1번줄부터 n번 줄까지 퀸을 배치하는데, x좌표가 중복되지 않게 뽑는 것을 백트래킹 해주면서 대각선에 다른 퀸이 배치돼있는지 검사해줬다. #include #include #include #include using namespace std; int n; bool isValid(vector& picked) { //대각선 검사만 해주면 된다. |(y'-y)| == |(x'-x)| 인경우 return false if (picked.empty()) return true; for (int i = 0; i < picked.size()-1; i++) { // {i, picked[i]} : 퀸의 위치 (y,x) for (int j = i + 1; j <.. 2019. 7. 6.
BOJ 15649 - N과 M (1~12) N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다. 기본적으로 백트래킹을 이용해서 재귀로 구현함. 9~12같은 경우 중복을 제거해줘야 하는데, 이건 set로 해결하였다. #include #include #include using namespace std; void printPicked(vector& picked) { for (int n : picked) printf("%d ", n + 1); printf("\n"); } int n, m; void pick(vector& picked, vector& isUsed, int k) { if (k == m) { printPicked(picked); return; } for (int next = 0; next < n; next++) { if (!isUsed[nex.. 2019. 7. 6.
07 - 쿼드 트리 QUADTREE 1. 흑백 그림의 string 형태 표현에 대한 규칙설명, string 형태 표현 입력으로 주어졌을 때 그림을 상하반전했을 때의 결과에 대한 string 형태 표현을 출력으로 하는 문제. 2,3. 문제에서 트리를 그림으로 굳이 보여준 것에 의문을 갖고 생각해보니 주어진 입력을 트리로 구성만 한다면 x의 자식은 항상 4개고 w,b의 자식은 항상 없으니 루트트리부터 3,4,1,2번째 자식 순회하면 ㅆ가능하다고 생각함. 4. 처음엔 재귀로 트리를 구성하려 했지만 내 수준이 너무 떨어져서인지 구현할 수 없었음. string의 최대 길이가 1000이므로 for문으로 돌려도 가능하겠다 싶어서 구현해봄. 1) 첫 인덱스부터 for문을 돌린다면 자식노드로 사용된 노드는 다음에 부모 노드로 사용될 수 있지만, 부모 노드.. 2019. 6. 30.

티스토리툴바