oVeron

완전 탐색(bruteforce)이란, 말 그대로 가능한 모든 경우의 수를 탐색한 후 답을 구하는 것을 말한다. 예를 들어, bool형 n*m 이차원 배열을 입력받았을 때 true의 수를 구해본다 가정하자. 이를 구하기 위해서는 당연히 배열의 모든 원소를 확인해야 한다. n*m 배열의 모든 원소를 탐색해서 true의 수를 구하면 될 것이다. 이때의 시간복잡도는 O(nm)이 된다. 모든 경우의 수를 탐색해야 하기 때문에 for, while과 같은 반복문을 많이 쓰게 된다. 이를 간소화하기 위해 재귀함수를 응용하는 때가 많다. 현재 위치에서 가능한 경우의 수를 모두 탐색하여, 해당 경우의 수에 대한 재귀함수를 호출하는 식이다. bruteforce의 대표적인 예로 순열 만들기가 있다. https://www.ac..

알고리즘/algorithm 2023. 3. 22. 13:35

https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 백트래킹 구현 문제. 수식의 출력, 수식 계산을 유의해서 구현하자. #define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N; char arithSymbols[10]; vector mathExpre; void printExpre() { cout

알고리즘/baekjoon 2023. 3. 9. 17:15

https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net DFS + 백트래킹. 확률 계산과 방문 처리만 잘 하면 되었던 문제였다. #define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N; double percent[4]; int dir[2][4] = { ..

알고리즘/baekjoon 2023. 3. 9. 11:10

https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net DFS를 돌리되, 방문 처리를 적절히 하며 백트래킹을 하는 것에 유의하자. #define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int R, C, K; char MAP[6..

알고리즘/baekjoon 2023. 3. 9. 09:55