서로 순열이 되는 경우를 찾는 트릭(정렬해서 비교하기)

1501번: 영어 읽기 영어 단어의 첫글자와 끝글자가 서로 같고 그 사이의 글자가 순서가 뒤섞인채로 구성이 같으면 같은 단어로 취급한다 abcde는 acbde, abdce,... 등과 같다 단어 사전과 문장들이 주어질때 각 문장을 해석하는 방법의 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------- 영어 단어가 bakers, brakes, breaks,...등이 주어질때 먼저 bakers를 보면 bakers, bkaers, bekras, berkas, bearks,... 등이 서로 같은 단어들이다...

  • format_list_bulleted 애드 혹 알고리즘
  • · 2025. 3. 5.
  • textsms

4개 원소를 골라서 짝지어서 쌍을 만들어 크기 비교하는 놀라운 방법

20366번: 같이 눈사람 만들래? n개의 눈덩이가 있는데, 2개의 눈덩이를 합쳐서 1개의 눈사람을 만들 수 있다 n개중 4개의 눈덩이를 골라 2개의 눈사람을 만들려고 한다 이때 눈덩이 크기의 합이 눈사람의 크기라고 할때, 두 눈사람의 크기 차이가 최소가 되도록 하려고 한다 최솟값을 구하면? -------------------------------------------------------------------------------------------------------------------------------------------------------- n이 최대 600인데 이중 4개를 고르면 600C4로 못해도 600*599*598*597 정도에 근사하는 정도? 아무튼 10^8을 가뿐하게 넘는다..

  • format_list_bulleted 정렬 알고리즘
  • · 2025. 3. 4.
  • textsms

두 팀중 적어도 한 팀이 소수만큼 점수를 얻을 확률

1344번: 축구  90분간 이루어지는 축구 경기를 5분 간격으로 나눈다. 처음 간격은 처음 5분, 두번째 간격은 그 다음 5분... 각 간격에서 A,B팀이 각각 득점할 확률이 주어진다 각 간격에서 A,B팀은 각각 많아야 한골씩 득점할 수 있다 경기가 끝났을 때 적어도 한 팀이 소수로 득점할 확률은? ------------------------------------------------------------------------------------------------------------------------------------ 5분씩 간격이 나눠지고 전체 경기 시간은 90분이므로 총 18간격씩 이루어진다 각 간격에서 두 팀은 독립적으로 최대 1골씩 넣을 수 있다 dp[i][a][b] = i번째 간..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2025. 3. 2.
  • textsms

스택으로 쌓아놓은 수열에서 조건을 만족하는 값들이 언제부터 다 나오는가?

17162번: 가희의 수열놀이 (Small) 여러개의 쿼리가 주어지는데,  1. 스택의 맨 뒤에 숫자를 추가 2. 스택이 비어있지 않으면 맨 뒤의 원소를 제거 3. 맨 뒤에서부터 최소 몇개의 수를 선택해야, 이들을 mod로 나누었을때 0,1,2,..,mod-1이 최소 1개 이상 나타나는가? 예를 들어 [2,3]인 경우 4로 나누면 나머지는 [2,3]인데, 여기서 0,1이 없으므로 -1 [2,3,1,4]인 경우 4로 나누면 나머지는 [2,3,1,0]인데 여기서 0,1,2,3이 모두 나왔으므로 4 -----------------------------------------------------------------------------------------------------------------------..

  • format_list_bulleted 자료구조(스택,큐,해시맵)
  • · 2025. 2. 27.
  • textsms

구간의 시작과 끝중 하나를 선택할 수 있는 다이나믹 프로그래밍

1823번: 수확  왼쪽부터 오른쪽으로 n개의 벼가 있는데, 매번 맨 왼쪽 혹은 맨 오른쪽 중 하나를 수확할 수 있다 k번째 수확할때 그 벼의 가치가 A[i]라면, A[i] * k의 이익을 얻는다 n개의 벼를 모두 수확할 때 얻는 최대 이익은? --------------------------------------------------------------------------------------------------------------------------------------------------- dp[i][j]를 [i,j] 구간에서 벼를 수확할 때 얻는 최대 이익이라고 정의 i번째 벼를 수확하거나, j번째 벼를 수확할 수 있다 [i,j] 구간에 벼가 있다면 0 ~ i-1의 벼랑 j+1 ~ n-1..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2025. 2. 26.
  • textsms
카탈란 수(Catalan numbers) 공부하기

카탈란 수(Catalan numbers) 공부하기

1. 카탈란 수 n = 0,1,2,3,...에 대하여 다음과 같은 수열 1,1,2,5,14,42,132,429,1430,4862,16796,58786,.... 0이상의 n에 대하여 카탈란 수 Cn는 다음과 같은 재귀적 관계를 만족한다. C0=1,Cn=n∑i=1Ci−1Cn−i 이는 다음과 같이 정리할 수 있고 C0=1,Cn=2(2n−1)n+1Cn−1 점화식을 풀면 다음과 같이 일반항을 도출할 수 있다. C_{n} = \frac{1}{n+1} * \binom{2n}{n}  2. 응용 1) Dyck word n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 하나씩 셌을때 Y의 개수가 ..

  • format_list_bulleted 조합론
  • · 2025. 2. 25.
  • textsms