브루트포스 문제 복기하면서 실수한 부분 체크하기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

절댓값을 풀어내는 필수 테크닉 - 모든 i,j에 대해 (i-j)|ai-bj|의 합을 빠르게 구하는 방법

28867번: Портальная пушка 최대 100000개의 원소를 가지는 배열 A,B에 대하여 $\sum_{i,j}^{}(i-j)|a_{i} - b_{j}|$를 구하는 문제 당연히 $O(N^{2})$은 안될거고 O(N)에는 풀어야하는데 $a_{i} >= b_{j}$이고 $a_{i}  따라서$(i-j)|a_{i}-b_{j}| = i(a_{i}-b_{j})-j(a_{i}-b_{j})+i(b_{j}-a_{i})-j(b_{j}-a_{i})$ 그래서 ai>=bj인 경우 i(ai-bj)와 j(ai-bj), ai  여기서 핵심은 앞에 붙은 i,j인데 얘를 고정시킨다면 투포인터를 활용해서 O(N)에 계산할 수 있다. 예를 들어 i = 0인 경우 j = 0,1,2,...증가시켜서 ai >= bj인 경우의 j를 ..

• format_list_bulleted 투 포인터 알고리즘
• · 2024. 10. 24.
• 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

주어진 점들 중 최대 맨해튼 거리(Manhattan Distance)를 빠르게 찾는 방법

https://atcoder.jp/contests/abc178/tasks/abc178_e E - Dist MaxAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp   n개의 점이 주어질때, 이들 쌍으로 만들 수 있는 가장 긴 맨해튼 거리는? n이 최대 20만이기 때문에 $O(N^2)$으로 직접 비교할 수는 없다 두 점 (xi,yi), (xj,yj)에 대하여 맨해튼 거리는 |xi - xj| + |yi - yj| = A A는 xi,xj, yi,yj 사이 대소관계에 따라 다음과 같이 풀어낼 수 있다 1) $x_{i} >= x_{j}..

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

정확히 배낭의 크기만큼 담아야하는 독특한 배낭 문제

13910번: 개업 (acmicpc.net) n그릇의 요리를 해야하는데 가지고 있는 도구 크기들이 주어질때,  주어진 도구를 사용할때는 정확히 해당 크기만큼 요리해야한다면 n그릇을 만들기 위해 최소 몇번 요리해야하는지 예를 들어 1그릇, 3그릇용 도구가 주어지면 3그릇용 도구로 2그릇을 요리하지는 않고,  1그릇용 도구만 사용하여 1그릇만 요리할 수도 있고 1그릇, 3그릇 도구를 동시에 써서 4그릇을 요리할 수도 있다 또한 4그릇을 만들어야할때, 5그릇을 만들지 않는다  배낭문제처럼 dp[i] = i그릇 요리를 만들기 위해 해야하는 최소 요리 수 0그릇 요리에는 당연히 0번이면 되니까 dp[0] = 0 i = 1,2,3,...,n에 대하여 j번째 도구를 사용할때, k = j+1,j+2,...,m-1번째 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 10. 1.
• textsms