브루트포스 문제 복기하면서 실수한 부분 체크하기1(어디서든 시작할 수 있다)

3129번: 상범이의 은밀한 메세지 암호화된 메시지랑 원본 메시지의 일부가 주어질떄, 원본 메시지를 찾는 문제 각 메시지에서 알파벳을 0~25로 치환하고  원래 메시지 + 키 = 암호화된 메시지 이기 때문에 암호화된 메시지 - 원래 메시지 = 키임을 알 수 있다. 여기서 원래 메시지의 일부분만 보여지기 때문에 암호화된 메시지랑 원래 메시지를 비교해서 가능한 모든 키를 구해야한다. 예를 들어 암호화된 psinottfn과 원래 메시지 most가 주어지는데 원래 메시지 most는 어디 부분인지 모르니까 0번부터 5번까지 most를 비교해보면서 키를 찾는다 psinottfnmost psinottfn  most ... for i in range(len(a)-len(b)+1): K = [] for..

• format_list_bulleted 브루트포스
• · 2024. 10. 26.
• textsms

탐색 범위를 줄여야하는 브루트포스 연습2 - 컴퓨터로 종이접기?

12979번: 종이 접기  종이의 크기 W,H인 종이가 주어질때 종이를 적절히 접어서 넓이가 A가 되도록 만들고 싶다. 종이를 접더라도 직사각형이 되도록 접어야하고 접고 나서도 W,H는 항상 정수가 되어야한다. 여기서 W,H가 10^9까지인데 A가 10^5까지라는 점에 주목하자. W,H로 뭔가 해보는건 어려울것 같지만 적어도 A는 1~10^5까지 다 돌아볼만하다. X*Y = A가 될려면 당연히 X,Y는 A이하여야한다. 그래서 A를 기준으로 1~A까지 돌아서 그 값을 X라고 둔다면, Y는? A가 X로 나누어 떨어질때, Y = A//X가 된다. 이러한 X,Y를 찾았다면 주어진 W,H에서 찾은 X,Y로 몇번만에 이동할 수 있는지 체크하면 된다.  W에서 X로 갈려면 가장 빠르게 갈려면 몇번만에 갈수 있을까? ..

• format_list_bulleted 브루트포스
• · 2024. 10. 25.
• textsms

탐색 범위를 줄여야하는 브루트포스 연습1 - 각 자릿수의 제곱합?

17755번: Równanie 정수 k가 주어질때 a  여기서 f(n)은 n을 10진법으로 표현했을 때 각 자릿수의 제곱합 k,a,b  이럴때는 탐색범위를 좁힐 수 있는지 생각해봐야한다  f(n)이 n을 10진법으로 표현했을 때 각 자릿수의 제곱합이므로,  $n = a_{1} * 10^{x_{1}} + a_{2} * 10^{x_{2}} + a_{3} * 10^{x_{3}} + ...$이므로  $f(n) = a_{1}^{2} + a_{2}^{2} + ....$인데 여기서 $a_{i}  그런데 n이 최대 10^18이므로 f(n)이 최대가 될려면 999999999999999999로 9가 18개 있는경우이다. 이 경우 81*18 = 1458이라서 f(n)으로 가능한 값은 1부터 1458까지이다.  그러므로 ..

• format_list_bulleted 브루트포스
• · 2024. 10. 24.
• textsms

논리식의 일부를 바꿔서 원하는 결과가 나오게 만드는 방법

31835번: 수식 고치기 (acmicpc.net) T,F,&,|으로만 이루어진 논리식에서 일부를 바꿔서 원하는 결과가 나오게 만들고 싶다. 연산은 왼쪽에서 오른쪽으로 차례대로 진행하고, 논리식을 최소로 바꿀때, 최소횟수를 구한다면 예를 들어 F & F가 주어질때 연산 결과를 T로 만들고 싶다면 T & T로 바꾸면 되니 2번이다. 단순하게 생각한다면 가능한 경우 다 조사해서 다 바꿔볼려고  할텐데..  그러자니 어떻게 바꿔야할지도 모르겠고 길이가 N  하다가 머리를 굴려보니.. &와 |으로 이루어진 연산을 생각해보면 T & T = T T & F = F F & T = F F & F = F T | T = T T | F = T F | T = T F | F = F 이렇게 되니까 a1 b1 a2 b2 a3 b3 ..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 9. 23.
• textsms

모든 집합의 합집합과 다르게 되는 일부를 골라 만든 최대 합집합

30237번: 합집합 (acmicpc.net) s1,s2,...,sn 집합이 주어질때, 이들 중 일부를 골라 만든 합집합 s와 모든 집합의 합집합 s1 ∪ s2 ∪ ... ∪ sn이  서로 다르게 되는 가장 큰 합집합 s를 구하고 싶다 집합을 기준으로 s1 넣어보고 s2는 넣지말고... sn은 넣고 등등으로 해서 s를 다 조사해보는건 $O(2^{50})$으로 어렵다 모든 집합의 합집합을 먼저 구하고 그 중에서 하나의 집합만 빼는 방법은 어떨까? 집합 합칠수록 원소가 많아질테니까... s2 ∪ s3 ∪ ... ∪ sn s1 ∪ s3 ∪  ... ∪  sn ... 이러면 O(N)정도니까 괜찮을것 같은데 [1], [3,6,10], [9], [1,3], [5,8,9]를 보면 모든 집합의 합집합은 [1,3,5,6..

• format_list_bulleted 브루트포스
• · 2024. 9. 9.
• textsms

ABC 339 D번 복기 - 4차원 visited 배열 BFS 백트래킹

1. 문제 D - Synchronized Players (atcoder.jp) D - Synchronized Players AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 하라는대로 구현하면 된다 두 플레이어 P가 움직이는데 두 플레이어는 같은 방향으로 움직이게 되어있다. 또한 한 플레이어가 해당 방향으로 움직일수 없더라도 다른 플레이어가 움직일 수 있다면 움직이는 경우로 생각한다 그래서 먼저 두 플레이어의 위치를 찾고 BFS를 수행하는 전형적인 형태 n = int(stdin.readline()) maps = ..

• format_list_bulleted Atcoder
• · 2024. 2. 5.
• textsms