live the life you love

www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 다익스트라 문제를 풀려고 했는데, 백트래킹으로 풀었다. 처음에는 문제의 설명이 조금 헷갈렸는데, 고려해야할 조건은 다음과 같았다. 가진 돈을 목적지까지 도착하기 전에 전부 사용하지 않기 목적지에 도착했다면 지금까지 지나온 노드 중 가장 비용이 큰 값이 어떤 것인가? 목적지에 도착하는 길이 2개 이상인 경우 가장 비용이 큰 값 중 최소가 정답 위의 조건들을 백트래킹에 맞게 풀어주..

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 연습하기 위해 내장 함수를 사용하지 않고 직접 함수를 구현해서 문제를 풀었다 N과 M(3)는 중복순열을 구하는 문제이다. 순열을 구하는 것과 크게 차이는 없고 중복된 값을 따로 체크하지 않기 때문에 따로 체크할 부분은 없다. 소스코드 n, m = map(int, input().split()) result = [] def dfs(count): if count == m: print(*result) re..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 백트래킹을 연습하기 위해 약 1달전, 2월 4일에 풀었을 때 틀렸던 문제를 다시 풀어보았다. 그때 트렐로에 남겨둔 메시지는 이랬었다. 두가지..

순열, 조합은 정말정말 많이 나오는데 cpp의 stl 라이브러리 중 next_permutation으로 구할 수 있다. 하지만 next_permutation은 N이 20만 넘어가도 터질 위험에 처한다.. 시간복잡도가 크기 때문이다. N이 10 언저리일때 쓰면 좋다. 재귀를 사용하여 DFS탐색을 통해 순열, 조합을 구하는 것이 가장 안전하고 깔끔하다.순열 구하기#include #include #include #define MAX 5 using namespace std; vectorarr; vectorresult; int visit[MAX]; /* 순열 구하기 */ void prt_permu() { for (int i = 0; i < result.size(); i++) { cout