느리게 갱신되는 세그먼트 트리 구현하면서 이해해보기(lazy propagation)

1. 문제 크기가 N인 정수의 배열 A가 주어지며 구간의 합을 구하는 문제를 M번 수행하는 문제에서 중간에 index번째 수를 value로 바꾸는 문제는 세그먼트 트리를 이용하여 해결했다. 이번엔 단순히 i번째 수를 value로 바꾸는 것이 아니라, i번째 수부터 j번째 수에 v를 더하는 경우를 생각해보자. 세그먼트 트리에서 index번째 수를 value로 바꾸는 연산은 O(logN)인데, i번째수부터 j번째 수를 모두 v로 바꾼다면 최대 O(NlogN)이다. 하지만 그냥 i번째 수부터 j번째 수를 순회해서 바꾸면 O(N)이다. 세그먼트 트리를 사용했더니 오히려 더 느리게 된다 2. 구간을 변경하는 update함수 [left,right]의 모든 수에 value를 더하는 작업을 수행해야한다면? [left,..

• format_list_bulleted 세그먼트 트리
• · 2022. 12. 11.
• textsms

조금 더 어려운 다이나믹 프로그래밍 연습하기 -퇴사1,2-

1. 문제 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 15486번: 퇴사 2 (acmicpc.net) 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 주어진 일정표에 상담기간과 해당 상담을 완료하면 얻는 이익이 주어진다. N+1일에 퇴사할려고 할때, 그 전에 최대이익을 얻도록 상담을 끝내고 싶다. 가능한 최대이익을 구하는 프로그램을 작성해본다면..? 2. 풀이 예전에 푼 수영..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 11. 7.
• textsms

이분 그래프 판별하는 알고리즘 분석

1. 문제 그래프의 정점의 집합을 둘로 분할하는데 각 집합에 속하는 정점끼리는 서로 간선이 존재하지 않도록 분할하고 싶다. 이것이 가능한지를 판별하는 프로그램을 작성해본다면? 2. DFS 알고리즘 무방향 그래프라고 가정함 어떤 정점을 방문하면서 방문한 정점에 그룹 1을 할당 인접한 정점을 순회하면서, 인접한 정점이 방문하지 않은 정점이면 그룹 -1을 할당하고 방문 하지만 인접한 정점이 이미 방문한 정점이라면, 현재 정점의 그룹(현재 그룹이 할당됨)과 이미 방문한 정점(이미 그룹이 할당됨)이 서로 같은 그룹이면 이분 그래프가 아니다 3. 예를 들어서 생각해보기 다음과 같은 그래프가 이분 그래프인지 생각해보자 임의의 정점 아무거나 하나를 선택하고 방문을 시도 방문하면서 파란색을 부여한다 현재 방문한 정점과 ..

• format_list_bulleted 이분 매칭
• · 2022. 11. 5.
• textsms

100번할 것을 1번만에 하는 나눗셈 연산 -시험 감독-

1. 문제 13458번: 시험 감독 (acmicpc.net) 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 각 시험장의 응시자 수가 주어지고, 총 감독관은 b명, 부 감독관은 c명만큼 감시가 가능하다. 모든 시험장의 응시자들을 감시할 수 있는 필요한 감독관의 최솟값을 구하는 프로그램을 작성 2. 풀이 문제 설명이 아쉽긴한데 총 감독관은 필수로 1명을 배치해야하고, 부 감독관은 0명 이상을 배치해야한다 총 감독관 1명을 배치하면, b명을 감시할 수 있으니..

• format_list_bulleted 애드 혹 알고리즘
• · 2022. 11. 3.
• textsms

투 포인터 알고리즘을 배우고 응용문제 해법 배우기

1. 개요 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 예를 들어 한 반에 학생이 40명이 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤에 학생들을 순차적으로 지목한다고 하자 2,3,4,5,6,7번 학생을 지목해야할 때, 우리는 번호로 한명씩 부르기보다는, "2번부터 7번까지의 학생"이라고 부를 수도 있다. 이처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는, '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 2. 예시 - 특정한 합을 가지는 부분 연속 수열 찾기 문제 양의 정수로만 구성된 리스트가 주어질때, 그 부분 연속 수열중에서 특정한 합을 갖는 수열의 개수를 출력하는 문제를 생각해보자. 예..

• format_list_bulleted 투 포인터 알고리즘
• · 2022. 10. 28.
• textsms

가장 긴 증가 부분수열 실제 수열을 구하는 역추적 방법

1. 기본적인 $O(n^{2})$ 알고리즘 기본 알고리즘을 다시 한번 생각해보자. 수열 s를 처음부터 순회하면서, i번째 원소를 읽었을때, 0~i번째 원소까지 최장 증가 부분수열의 길이는... i보다 작은 인덱스 j에 대하여, dp배열의 0~j까지 모두 순회해서, j번째 숫자가 i번째 숫자보다 작다면, 그러한 j번째 숫자가 만드는 최장 증가 부분수열에 i번째 숫자를 포함시키면 된다 이렇게 찾은 최장증가부분수열의 길이들의 최댓값이 i번째 원소가 들어가는 최장 증가 부분수열의 길이였다 다익스트라 알고리즘에서 최단거리를 역추적하듯이 생각해보면 아주 심플하다 역추적을 위한 배열 p를 생각해서 현재 i번째 원소에 대한 dp값이 1이라면.. 최장 길이가 1이라는 뜻이니까 자기 자신이 최장 증가 수열의 시작점이니 p..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 10. 26.
• textsms