15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다. 출력 시 오름차순으로 정렬하여야 합니다. 2. 접근 방법 순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 순열 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: prin..
15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net 해당 문제는 제곱수를 구하는 문제입니다. 이 사실을 알면 굉장히 쉽게 풀 수 있습니다. 다만, 저는 몰랐구요 ㅎ... 정답을 찾아놓고 최적화 하는 것을 좋아해서 맨 처음에 그냥 완전탐색으로 for문 두 번 돌렸습니다. 작은 숫자들은 무난하게 되더군요. 다만 제출했더니 바로 메모리가 터집니다 ㅎㅎ.. 사실 예상했던 부분인지라 좀 더 살펴보았습니다. 보다보니 규칙이 보이더군요. 3, 5, 7, 9, 11 ~ 이런 식으로 숫자가 2씩 증가하면서 백기의 숫자가..
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가 통과될 ..
19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 해당 문제는 이원연립방정식의 해를 구하는 문제입니다. 해당 문제도 완전탐색 알고리즘을 활용하면 손쉽게 풀 수 있습니다. 물론, 직접 방정식을 푸는 식을 사용한다면 더욱 최적화를 할 수 있습니다. 두 가지 방법 모두 사용해 보겠습니다. # Python : 일반적인 완전탐색을 활용한 방법입니다 def solution(a: int, b: int, c: int, d:..
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..
데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복 기법으로 특정한 값을 찾아내는 알고리즘 이진 탐색 알고리즘 동작 원리 Up&Down 게임과 흡사하다 정렬된 배열의 가장 중간 인덱스를 지정한다 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료한다 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다 값이 있는 부분과 값이 없는 부분으로 분리한다 값이 있는 부분에서 다시 1단계부터 반복한다 장점 ( 주 사용처) 사전 검색, 도서관 도서 검색, 대규모 시스템에 대한 리소스 사항 파악 등 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가지게 된다 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용 데이터의..
모든 값을 대입하는 방법 컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다 암호학에서는 Brute Force Attack이라고 한다 이는 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법을 말한다 쉽게 말해, 암호를 모르는 0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 했을 때, 이 자물쇠의 비밀번호를 풀기 위해서 0000부터 9999까지의 모든 경우의 수를 대입하여 푸는 방법이다 Brute Force Algorithm의 의미 무차별 대입 방법을 나타내는 알고리즘 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법 Brute Force Algorithm이 사용될 때 프로세스 속도를 ..
탐욕스러운, 욕심 많은 Greedy Algorithm은 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식 문제 해결 절차 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복 마시멜로 실험 지금 마시멜로를 받겠다고 하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다. greedy는 지금 당장에 최선인 선택을 하기 때문에 지금을 선택하여 1개를 받지만, 전체적으로 보면 ..
