완전탐색

[백준 16637] 괄호 추가하기 (C++)

16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 꿀 조건 1. 괄호 안에는 연산자 하나만 들어갈 수 있다. 꿀 조건 2. 중첩된 괄호는 사용할 수 없고, 항상 올바른 수식만 주어진다. 모든 괄호 안에는 정직하게 정수1, 연산자, 정수2 의 형태로 구성되어있다. 이 점을 활용해서 백트래킹을 사용한 브루트 포스로 현재 연산자를 둘러싸는 괄호를 추가하는 경우, 그냥 넘어가는 경우 모두에 대해서 수식의 값을 확인하면 답을 구할 수 있다. 현재 연산자가 괄호로 둘러싸일 경우, 바로 다음 연산자(현재인덱스+2..

[프로그래머스 level2] 피로도 (C++)

현재 피로도에 따라서 최대로 탐험할 수 있는 던전의 수를 구하는 문제이다. 던전 탐험에 필요한 피로도가 2차원 배열로 주어지고, 던전 탐험 순서에 따라서 탐험할 수 있는 던전의 개수가 달라질 수 있으므로 백트래킹을 사용한 완전 탐색으로 구현했다. 매 dfs 호출마다 지금까지 탐험한 던전의 최대 갯수를 갱신해준다. (cnt는 매개변수로 가지고 있다.) answer = max(answer, cnt); 현재 던전에서 다음 던전으로 이동하는 부분이다. 주의할 점은 다음 던전으로 이동하기 위해서 현재 피로도가 다음 던전에 필요한 피로도보다 많아야 한다는 점이다. for(int i = 0; i < dungeons.size(); i++){ if(visited[i]) continue; if(nowHp < dungeon..

[백준 1339] 단어수학 (C++)

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 브루트 포스 - 순열 (연습) 7달 전에 그리디를 사용해서 풀었었는데 이번엔 백트래킹 완전탐색을 이용해서 풀었다. 모든 단어를 입력받고 단어에 사용된 알파벳(최대 10개)를 중복 없이 걸러내기 위해서 중복을 허용하지 않는 자료구조인 set을 사용했다. 10개의 알파벳에 9~0까지의 숫자를 매칭해주고 모두 매칭이 된 경우 (cnt == 알파벳의 개수) 최대 10개의 단어를 매핑테이블(table[27])을 이용해 모두 숫자로 바꾸고 각각을 더해주었다. 매칭은 ..