정수들이 섞여있는 수열에서 연속하는 정수 수열을 O(N)에 분리하기

11232번: Shuffles (acmicpc.net)  주어진 수열이 최소 몇번의 shuffle로 이루어진 수열인지 구하는 문제 셔플방법은 수열에서 어떤 특정 지점에서 두 부분으로 나누고 두 부분을 순서를 유지한채 섞는 것이다. 1 2 3 4 5라면..  1 2 3 4 5로 나누고  1 4 2 5 3 처럼 섞는 것 주어진 수열에서 어떤 특정 지점 k에서 나뉘었다고 한다면, 2개의 부분 수열 1,2,3,...,k k+1,k+2,...,n으로 나뉘고 이것이 섞일 것이다. 이렇게 섞인 수열에서 또 한번 나누면 최대 4개의 부분 수열 1,2,3,..,k1 k1,k1+1,...k k+1,k+2,..k2 k2+1,k2+2,...,n으로 구해진다. 여기서 또 한번 나누면 최대 8개의 부분 수열을 얻을 수 있다. ...

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 5. 12.
• textsms

무방향 연결그래프에서 정점의 성질 관찰하기

18668번: Find the Vertex (acmicpc.net)   무방향 연결그래프가 주어지고, self-loop나 multiple edge가 없다. 정점의 번호가 1번부터 n번까지 되어있고, 시작정점 s번에서 다른 정점까지의 거리를 3으로 나눈 나머지가 배열로 주어진다. 여기서 s가 무엇인지 찾는 문제 n,m 제한이 50만이다보니, 하나하나 해보기는 어렵다. 일단 거리 배열에서 0인 값인 정점 번호가 일단 정답 후보가 될 것이다. 시작정점 s에서 거리가 3,6,9,... 3의 배수여도 0이기 때문에 정답이 아닌 정점이 있을 수도 있다. 또 하나 알 수 있는 점은, 시작정점 s라면 인접한 정점까지 거리는 무조건 1이다.   물론 위 그림과 같이 s에서 인접한 3개 정점과 똑같이 인접한 어떤 정점 A..

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

부분문자열 필수 트릭 - doubling cyclic substring trick

24597번: Reversibly Cyclic Strings (acmicpc.net)  문자열 s의 cyclic substring이라는 것은 s를 rotate했을때 부분문자열 t를 말한다. 'fatcat'에서 'atf'는 fatcat에서 왼쪽으로 1칸 rotate하면 atcatf인데 여기에 부분문자열로 있다 만약 s의 모든 부분문자열 t에 대하여 t를 뒤집은 것이 s의 cyclic substring이라면 s를 'Internally Reversibly Cyclic'이라고 정의한다. 주어진 s가 Internally Reversibly Cyclic인지 판단하는 문제  어떤 부분 문자열 t가 s의 cyclic substring이라는 것을 어떻게 알 수 있을까? 한칸 한칸씩 roate해서 판단해봐야할까? fatc..

• format_list_bulleted 문자열 알고리즘
• · 2024. 5. 9.
• textsms

적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률은?(교란순열의 수렴)

13531번: Secret Santa (acmicpc.net)  n명의 사람이 모자에 이름을 쓰고, 한번 섞은 다음에 다시 가져가는데 적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률을 구하는 문제 https://deepdata.tistory.com/946 자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기1. 문제 1947번: 선물 전달 (acmicpc.net) 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 풀이 PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가deepdata.tistory.com 1 - n명의 사람이 모두 자기 자신 것을 가져가지 않는 확률 = 적어도 1명 이..

• format_list_bulleted 조합론
• · 2024. 5. 8.
• textsms

슬라이딩 윈도우를 이용한 최댓값 찾기(sliding window maximum, Deque Range Maximum Trick)

1. 문제 배열 A에서 길이가 K인 모든 연속하는 부분배열내에서 최댓값을 찾는 문제 [1,2,3,1,4,5]이고 K = 3인 경우를 생각해보자. [1,2,3]에서 최댓값은 3 [2,3,1]에서 최댓값은 3 [3,1,4]에서 최댓값은 4 [1,4,5]에서 최댓값은 5 배열의 크기가 작으면 매우 쉬운 문제지만, 배열의 크기가 크면 상당히 어려운 문제다. 투포인터로 구간의 시작과 끝을 잡고 첫 구간에서는 어떻게 O(K)로 최댓값을 찾아 놓은 다음.. 다음 구간으로 이동할텐데, 시작과 끝의 위치를 아니까, 시작 쪽의 원소를 버릴거고 끝의 원소를 추가할거고... 그런다고 하더라도 최댓값이 뭔지를 어떻게 알지? 운 좋게 시작과 끝에 최댓값이 있다고 하더라도... 구간 중간에 최댓값이 있는거라면 어쨌든 매 구간마다 ..

• format_list_bulleted 슬라이딩 윈도우
• · 2024. 5. 8.
• textsms

돌 무더기에서 팰린드롬(palindrome)인 정수 개수만큼 가져갈 때 이기는 방법

31648번: Palindrome Game (acmicpc.net)   돌 무더기에 s개의 돌이 있는데, A,B가 양의 정수 x개만큼 돌을 가져간다. 여기서 x는 palindrome이어야 한다.  palindrome은 앞에서 읽어도 뒤에서 읽어도 같은 수이다. 예를 들어 1, 121, 9009는 palindrome이다. 앞에 0을 붙이는 것은 허용하지 않는다. 예를 들어 990은 palindrome이 아니다. s가 주어질때, 최선을 다해 게임하는 둘에 대해 선공이 이기는지 후공이 이기는지 판단 -----------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 게임이론
• · 2024. 5. 6.
• textsms