19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 1. 문제 요약 N개의 식재료가 주어지고, 해당 식재료를 이용하여 영양성분을 만족하는 최저 비용 조합을 구하라 2. 접근 방법 재귀함수를 이용하여 모든 조합을 구한다. 영양성분을 만족하는 조합들 중 최저 비용을 계산한다. 3. 파이썬 def solution(index:int, used:list): global C, USED if index == N: p, f, s, v, c = 0, 0, 0, 0, 0 for i in used: p += PFSVC[i-1][0]..
2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 1. 문제 요약 재료의 개수 N, 그 재료의 맛 S, B가 주어진다. S는 곱, B는 덧셈으로 맛이 변한다. 재료를 적절하게 조합하여 S와 B의 차가 가장 작은 경우의 맛을 출력하라. 2. 접근 방법 재귀함수를 이용하여 조합을 구해줍니다. 재료를 사용하거나, 사용하지 않거나로 구분하여 진행합니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth:int, used:..
1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 이번 문제는 체커입니다. 여러 개의 체커들의 좌표가 주어지고, 해당 체커들이 모일 수 있는 가장 적은 비용을 구하는 문제입니다. 다만, 여러 개의 체커들이 모두 모인 경우만 구하는 것이 아니라 1개 모였을 때, 2개 모였을 때, 3개 ~, 4개 ~ 이런 식으로 구해야 합니다. 해당 문제는 완전탐색으로 해결할 수 있습니다. // 슈도 코드 // 1. 각 체커들이 모일 좌표를 선정한다. // 2. 선정한 좌표와 각 체커들의 거리를 계산하여 저장한다. (i..
2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 이번 문제는 숫자 야구입니다. 주어진 힌트를 통해 가능한 숫자들의 개수를 출력하는 문제입니다. 해당 문제도 완전탐색을 이용하여 풀어보도록 하겠습니다. // 슈도 코드 (Java 기준) // 1. 주어진 입력을 받는다 int[][] hint; // hint에 각 회차별 힌트들을 저장한다. int count = 0; // 가능한 숫자의 횟수를 받을 변수 // 2. 1 ~ 999 중 각 자릿수가 서로 다른 경우 hint와 비교한다. // 3. 모든 hint가 통과될 ..
14568번: 2017 연세대학교 프로그래밍 경시대회 규칙에 맞게 사탕을 분배하는 경우의 수를 출력한다. 택희, 영훈이, 남규가 받은 사탕의 수를 각각 A, B, C개라고 할 때, 서로 다른 (A, B, C) 순서쌍의 수를 세면 된다. 만일 규칙에 맞게 사탕을 분 www.acmicpc.net 해당 문제는 규칙에 맞게 사탕을 나눌 수 있는 경우의 수를 계산하는 문제입니다. 문제 조건을 보면 시간과 메모리가 충분하므로 완전탐색으로 구현하면 손쉽게 풀 수 있습니다. # Python N = int(input()) count = 0 for A in range(2, N - 1, 2): for B in range(1, N - A): C = N - A - B if C - B >= 2: count += 1 print(c..
1816번: 암호 키 현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다. 현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 www.acmicpc.net 백준 - 1816번 문제입니다. 해당 문제는 숫자가 주어지고 해당 숫자가 1,000,000 보다 큰 소인수로 이루어져 있다면 "YES"를 출력하고 아니면 "NO"를 출력하는 문제입니다. 다양한 방법으로 최적화가 가능하지만, 해당 문제의도에 맞게 가능한 모든 경우의 수를 넣는 방식인 완전탐색으로 풀어보겠습니다. 시간과 메모리가 충분하다면, 그 어떤 문제도 해결할 수 있는 아주 강력한 방법입니다. # Python for _ in range(int(input())): num ..
모든 값을 대입하는 방법 컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다 암호학에서는 Brute Force Attack이라고 한다 이는 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법을 말한다 쉽게 말해, 암호를 모르는 0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 했을 때, 이 자물쇠의 비밀번호를 풀기 위해서 0000부터 9999까지의 모든 경우의 수를 대입하여 푸는 방법이다 Brute Force Algorithm의 의미 무차별 대입 방법을 나타내는 알고리즘 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법 Brute Force Algorithm이 사용될 때 프로세스 속도를 ..
