연속하는 구간을 한번 뒤집어야할때 켜져있는 원소들의 합의 최댓값을 구하는 놀라운 방법

25634번: 전구 상태 뒤집기  전구의 밝기들이 배열로 주어지고, 초기에 켜져있는지, 꺼져있는지가 주어진다. 연속하는 구간내의 모든 전구들의 상태를 뒤집으면 켜진 전구는 꺼지고, 꺼진 전구는 켜진다. 이 연산을 정확히 1번 해야할때, 전구 밝기들의 합의 최댓값을 구한다. ---------------------------------------------------------------------------------------------------------------------------------------------------- n이 최대 20만인데, 연속하는 구간의 상태를 뒤집어야한다? 구간 dp로 하자니 O(N^2)일텐데  그리고 연산을 무조건 1번은 해야한다는거까지 굉장히 어렵다 처음 상태에서..

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

문자를 하나만 바꾸거나, 처음부터 연속된 k개를 바꿔서 전부 같은 문자로 바꾸는 다이나믹 프로그래밍

2806번: DNA 발견 A나 B로 이루어진 문자열에서 첫번째 연산은 하나의 문자를 A는 B로, B는 A로 바꾸는 것이다. 두번째 연산은 처음부터 연속된 K(1  예를 들어 ABBA라면, B 2개를 각각 A로 바꾸면 AAAA가 되고 처음부터 3개의 문자 ABB를 뒤집어서 BAA로 바꾸고, BAAA에서 첫번째 문자 B를 A로 바꾸면 2회만에 AAAA로 된다. 이러한 두 연산으로 모든 문자를 A로 바꾸고 싶다 가능한 최소 연산 횟수는? ----------------------------------------------------------------------------------------------------------------------------------------------------------..

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

이항계수를 구하는 알고리즘 기초1 - 파스칼의 삼각형

1. 파스칼의 삼각형 이항계수에 대한 성질 $$nCr = n-1Cr-1 + n-1Cr$$ 을 이용하여 이항계수 값들을 미리 테이블에 저장해놓는다 시간복잡도는 $O(n^2)$ n과 r이 10000이상이면 사용하기 힘들지만 충분히 작다면 사용하지 않을 이유가 없을 정도로 충분히 빠르다 2. 알고리즘 2-1) 행의 수 t를 입력받는다 2-2) 1부터 t+1까지 모든 행에 대해 0으로 초기화한 2차원 배열 생성 ------------------- 만약 행의 수가 아니고 최대 1000Cr까지 구하고 싶다면??? 1001개의 행을 받아야한다는 점을 기억해야한다 ------------------- 2-3) 각 행의 맨 처음과 맨 끝은 1로 만들고 2-4) 나머지는 $nCr = n-1Cr-1 + n-1Cr$을 이용하여 ..

• format_list_bulleted 알고리즘 일반
• · 2022. 8. 15.
• textsms

다이나믹프로그래밍 - 어떻게하면 완전탐색도 더 효율적으로 할 수 있을까?

1. 문제 N개의 block이 일렬로 있고 0부터 N-1까지 숫자가 붙어있다. 사이가 안좋은 개구리가 하나의 block위에 함께 있는데 이들이 서로 최대한 멀리 떨어지려고 한다. 만약 J와 K, J= s_h: s_h = h first += 1 else: break 현재 s-1에 첫번째 개구리가 시작할건데 blocks의 s부터 오른쪽으로 순회를 해서 h라고 두는거임 만약 h가 시작높이 s_h보다 크거나 같으면 점프할 수 있고 현재 개구리 높이 s_h를 h로 두고 first에 1을 더해서 개구리 위치를 갱신한다 근데 점프를 못하는 순간 더 이상 오른쪽으로는 못간다는 소리이므로 반복문을 탈출 s_h = blocks[s] #second frog for ind,h in enumerate(blocks[s::-1])..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 6. 23.
• textsms