올바른 괄호 문자열을 만드는 알고리즘

1. 올바른 괄호 문자열 1) 모든 k = 1,2,3,..,n에 대하여 $S_{1}, S_{2},...,S_{2k-1}$에 대하여 적어도 k개의 문자가 '('이다. 2) 모든 $S_{1}, S_{2},...,S_{2n}$에 대하여 정확히 n개의 문자가 '('이다. --------------------------------------------------------------------------------------------------------------------------- 단순히 개수만 맞아도 올바른 괄호 문자열이 된다? 예를 들어 S1S2S3S4로 생각해보면 S1 = '(' S1S2S3에서 적어도 2개의 문자가 '(' S1이 '('이어야하는데, 이때 S1S2S3S4는 정확히 2개의 문자가 '(..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2025. 5. 26.
• textsms

인접한 원소의 곱의 합이 최대가 되도록 수열을 만드는 방법

16209번: 수열 섞기 수열 a1,a2,...,an이 주어질때 인접한 원소들의 곱 a1a2 + a2a3+... + an-1an이 최대가 되도록 수열을 섞고 싶다 그렇게 섞은 수열 하나만 구한다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 적어도 양수는 양수끼리, 음수는 음수끼리 곱해야 한다는 것을 생각할 수 있다 또한 절댓값이 큰 것끼리 곱해야 커진다는 것도 생각할 수 있다 양수 그룹에서 큰 값들을 먼저 찾아서 a1 > a2 > .... > an이라고 한다면... a1 a..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2025. 2. 20.
• textsms

똑같은 원소를 연속해서 사용하지 않도록 최대한 쓰는 놀라운 그리디 알고리즘

25635번: 자유 이용권 i번째 놀이기구 이용권의 횟수가 A[i]로 주어진다 모든 놀이기구를 이용하고 싶은데 연속으로 같은 놀이기구를 사용하지 않는다 최대 몇번 사용가능한가? A = [1,1,3]이면 3번, 2번, 3번, 1번, 3번으로 5번 가능하다 처음에 생각하기에는 무조건 큰 값끼리 모아서 쌍으로 이용하면 된다고 생각을 했는데 A = [1,2,3,4,5]라고 한다면  5번 이용가능한거랑 4번 이용가능한거 모아서 5 4 5 4 5 4 5 4 이렇게 하면 8번 쓰는거고 5가 1번 남고 [1,2,3,0,1]에서  3,5 해서 3번이 2번 남고 [1,2,2,0,0]에서 3번 2번 가져와서 3,2,3,2 해서 [1,0,0,0,0] 해서 1번을 쓰면 된다는 식으로 n = int(input())A = list..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2025. 1. 21.
• textsms

재배열 부등식(rearrangement inequality)을 이용한 내적의 최대 최소

1. 재배열 부등식(rearrangement inequality) 실수 $x_{1}  1,2,..,n의 임의의 순열 $\sigma_{1}, \sigma_{2}, ... , \sigma_{n}$으로부터 $$x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{n}y_{1}   2. 증명 $S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}$에서 $y_{a}  $S2 = x_{1}y_{1} + x_{2}y_{2} + ... + x_{a}y_{b} + ... + x_{b}y_{a} + ... + x_{n}y_{n}$ 둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2024. 11. 22.
• textsms

기간 제한이 있는 과제들에서 최대 가치를 얻는 그리디 알고리즘

13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2024. 6. 4.
• textsms

1부터 n까지 각각 1번씩 정확히 k개의 정수만 사용해서 합을 s로 만드는 그리디 알고리즘

19177번: Klothes (acmicpc.net) 1부터 n까지의 자연수 중에서 각각 1번씩만 사용하고, 정확히 k개의 정수만 사용해서 합을 s로 만드는 방법을 찾는 문제 n이 40000까지이고 테스트케이스가 8000개이다 보니 단순한 방법보다는 O(N)정도에 하나는 해결해야  만약 s가 가능한 범위를 벗어난다면 일단 만들수가 없다. s의 최솟값은 1부터 k까지 합 s의 최댓값은 n-k+1,n-k+2,...,n까지의 합 만약 s가 (1부터 k까지 합)   반대로 이 범위 안이라면 확실하게 만들 수 있다는 것이 보장된다. (1부터 k까지의 합) = a (n-k+1,...,n까지의 합) = b라고 할 때, a,a+1,a+2,..,b-1,b까지의 모든 정수는 반드시 만들 수 있다. 어떤 정수는 안되는게 있..

• format_list_bulleted 알고리즘/그리디 알고리즘
• · 2024. 5. 29.
• textsms