본문 바로가기

Algorithm/Brute Force

 (122)
(C++) - 백준(BOJ) 15661번 : 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net backtracking을 이용한 brute force였습니다. 📕 풀이방법 최대 20명입니다. 팀은 두 개로 나뉘므로 한쪽의 인원이 정해진다면 나머지는 자동으로 정해집니다. 따라서 20C1 ~ 20C10로 팀을 뽑아서 능력치를 확인하면 됩니다. 20C10는 184756이므로 시간제한 2억안에 수행가능합니다. 📔 입력 및 초기화 각 인원의 능력치 정보를 ..
(C++) - 백준(BOJ) 18428번 : 감시피하기 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net backtracking 이용한 brute force 문제였습니다. 📕 풀이방법 n과 m의 응용문제였습니다. 📔 입력 및 초기화 board라는 2차원 배열 변수에 적절히 입력받습니다. 입력 도중 'T', 'X', 'S'가 나온 곳의 행,열 좌표를 각자 다른 vector 변수에 저장합니다. 📔 풀이과정 1. dfs를 수행합니다. 3개의 장애물을 조합의 형태로 board를 바꿔줍니다. 순서 상..
(C++) - 백준(BOJ) 14888번 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net backtracking하며 brute force로 푼 문제였습니다. 📕 풀이방법 1. 연산자를 사용할 수 있으면 해당 연산자를 사용하고 개수를 하나 빼줍니다. 연산을 하고 난 이후에는 사용한 개수를 반납해줍니다(더합니다) 2. 호출할 수 있는 모든 함수를 호출해도 n이 11이하이기 때문에 4^10밖에 안되므로 최적화 없이 간단히 해결할 수 있..
(C++) - 백준(BOJ) 15811번 : 복면산?! https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, www.acmicpc.net brute force 문제였습니다. 📕 풀이방법 1. 입력을 받고 나온 알파벳 종류의 개수를 세봅니다. 2. 숫자로 표현하려면 나오는 알파벳의 종류가 10개 이하여야 합니다. 그보다 초과하는 종류에 대해서는 서로 다른 한 자리 수의 번호를 매길 수 없기 때문입니다. 따라서 초과한다면 NO를 출력하고 종료합니다. 3. 나온 알파벳들을 겹치..
(C++) - 백준(BOJ) 10372번 : Alarm Clock https://www.acmicpc.net/problem/10372 10372번: Alarm Clock Output five characters in “hh:mm” format — the time shown on the clock in Alice’s dream. The time must be correct: 0 ≤ hh < 24 and 0 ≤ mm < 60. If there are many possible correct times, output any of them. If there is none, output “Impossible www.acmicpc.net brute force 문제였습니다. 📕 풀이방법 1. 0은 그림을 확인해보시면 6개의 획입니다. 1은 5, 2는 5... 이런식으로 9까지 획을 ..
(C++) - 백준(BOJ) 1446번 : 지름길 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net brute force로 풀었습니다. 풀이방법 1. 인접리스트로 지름길의 출발점, 도착점 그리고 길이정보들을 간선과 해당 비용으로 생각해 저장합니다. 저장할 때 주의할 점이 두 가지 있습니다. 도착점 - 출발점 사이의 거리가 길이정보 이하라면 사실상 지름길이 아니므로 볼 필요가 없습니다. 배보다 배꼽이 더 큰 상황이죠 두 번째로는 예시에 나와있듯이 도착지점이 d를 넘어가는 경우에도 간선정..
(C++) - 백준(BOJ) 21735번 : 눈덩이 굴리기 https://www.acmicpc.net/problem/21735 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net 백트래킹 문제였습니다. 풀이방법 1. idx번째 눈덩이를 골랐을 때 대회시간과 고르기 직전의 size를 dfs함수의 인자로 설정합니다. 2. idx번째 위치에서 다음 위치는 idx+1 또는 idx+2이므로 max(idx + 1, cnt + 1, size + idx+1번째 눈덩이 크기, idx + 2, cnt + 1, size + idx+2번째 눈덩이 크기)가 idx번째 위치에서..
(C++) - 백준(BOJ) 2003번 : 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 누적합 이후 brute force로 답을 찾는 문제였습니다. 풀이방법 연속된 수의 합들이 m이되는 것들의 개수를 구하면 되므로 누적합을 먼저 구해줘야합니다. 1. 1부터 시작해 누적되어 i까지의 합을 구한 값을 sum이라는 배열의 i번째에 저장합니다. 2. sum[j] - sum[i] == m인 개수를 세준 후 출력합니다. Code #include usin..

티스토리툴바