15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net 해당 문제는 제곱수를 구하는 문제입니다. 이 사실을 알면 굉장히 쉽게 풀 수 있습니다. 다만, 저는 몰랐구요 ㅎ... 정답을 찾아놓고 최적화 하는 것을 좋아해서 맨 처음에 그냥 완전탐색으로 for문 두 번 돌렸습니다. 작은 숫자들은 무난하게 되더군요. 다만 제출했더니 바로 메모리가 터집니다 ㅎㅎ.. 사실 예상했던 부분인지라 좀 더 살펴보았습니다. 보다보니 규칙이 보이더군요. 3, 5, 7, 9, 11 ~ 이런 식으로 숫자가 2씩 증가하면서 백기의 숫자가..
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..
1816번: 암호 키 현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다. 현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 www.acmicpc.net 백준 - 1816번 문제입니다. 해당 문제는 숫자가 주어지고 해당 숫자가 1,000,000 보다 큰 소인수로 이루어져 있다면 "YES"를 출력하고 아니면 "NO"를 출력하는 문제입니다. 다양한 방법으로 최적화가 가능하지만, 해당 문제의도에 맞게 가능한 모든 경우의 수를 넣는 방식인 완전탐색으로 풀어보겠습니다. 시간과 메모리가 충분하다면, 그 어떤 문제도 해결할 수 있는 아주 강력한 방법입니다. # Python for _ in range(int(input())): num ..
데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복 기법으로 특정한 값을 찾아내는 알고리즘 이진 탐색 알고리즘 동작 원리 Up&Down 게임과 흡사하다 정렬된 배열의 가장 중간 인덱스를 지정한다 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료한다 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다 값이 있는 부분과 값이 없는 부분으로 분리한다 값이 있는 부분에서 다시 1단계부터 반복한다 장점 ( 주 사용처) 사전 검색, 도서관 도서 검색, 대규모 시스템에 대한 리소스 사항 파악 등 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가지게 된다 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용 데이터의..
모든 값을 대입하는 방법 컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다 암호학에서는 Brute Force Attack이라고 한다 이는 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법을 말한다 쉽게 말해, 암호를 모르는 0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 했을 때, 이 자물쇠의 비밀번호를 풀기 위해서 0000부터 9999까지의 모든 경우의 수를 대입하여 푸는 방법이다 Brute Force Algorithm의 의미 무차별 대입 방법을 나타내는 알고리즘 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법 Brute Force Algorithm이 사용될 때 프로세스 속도를 ..
