[펜윅 트리] 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(BIT, Binary Indexed Tree)라고도 불린다. 펜윅 트리는 구간 트리에서 부분합에 대한 질의를 더 효율적으로 하기 위해 만들어졌다. 부분합을 통해 구간합을 구할 수도 있으므로 구간합에 대한 질의도 답할 수 있다. 단순히 부분합만 구한다고 하면 당연히 트리구조를 사용할 이유가 없지만, 원소를 변경할 때는 트리구조의 장점이 들어난다. 배열로만 부분합을 구현했다면, 배열의 원소가 바뀔때마다 O(N)의 연산을 해줘야한다. 하지만 펜윅트리는 이를 O(logN)만큼만 걸리게 함으로써 속도를 올린다. 펜윅 트리는 기존 구간트리에서 각 노드에 대해 right에 해당하는 자식 노드들을 죄다 지운 형태다. 이유는 부분합 자체가 배열의 ..

구간 트리(segment tree)는 이미 존재하는 자료들(정렬되지 않음)을 전 처리한 후, 특정 구간에 대한 질의(query)를 효율적으로 답하는 자료구조이다. 물론 작성하려는 부분은 컴퓨터 공학에서 다루는 구간 트리 와는 구현 방식을 비슷하지만 엄밀히 따지면 다른 자료구조로 그저 알고리즘 대회에서 사용되는 구간 트리를 다룰 것이다. 특정 구간에 대한 질의는 그 형식이 다양하다. 예를 들어 특정 구간에 대한 합이 될 수도 있고, 특정 구간에 대한 최솟값 혹은 최댓값이 될 수도 있다. 이를 배열에서 구현하게 되면 특정 구간을 순회하면서 답을 내야 하기 때문에 질문 하나에 대해 O(N)의 시간이 걸리게 된다. 구간 트리는 이진트리로 구현하며, 루트 노드는 모든 구간 [0, n-1]을 의미하고 left는 [..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 로직 자체는 떠올리기 쉬웠다. i번째 비행기가 1~gi 까지 도킹할 수 있을 때, gi부터 차례대로 보면서 자리가 남아있으면 채우면 된다. 즉, 도킹할 수 있는 구간중 게이트 번호가 가장 큰 수를 먼저 고르면 가장 많은 비행기를 도킹할 수 있다. 만약 그렇지 않으려면, 다른 순서로 도킹하는 방법이 위 방법보다 더 많은 비행기를 도킹시킬 수 있음을 보이면 된다. 도..

1. Lower Bound lower_bound는 이름에서 알 수 있듯, 하한선을 의미한다. 레퍼런스에 있는 std::lower_bound는 찾고자 하는 value와 같거나 더 큰 값을 찾는다고 되어있다. Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found. 즉, value 이상인 값이 처음으로 나오는 위치를 찾는 것이다. 다음은 lower_bound를 구현한 코드이다. #include using namespace std; int a[10] = {1, 1, ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 해답이 너무 뻔했다. 왼쪽에서 오른쪽으로 가는 경로는 여러개 있다. 문제는 한번 지나간 점은 다시 지날 수 없다는 것인데, 이 점이 핵심이 된다. 경로가 서로 겹쳐질 수 없기 때문이다. 따라서 경로를 하나의 실로 표현을 하자면, 위부터 차곡차곡 쌓아나가야 경로를 최대한 많이 만들 수 있다. 하나라도 겹쳐지는 순간 미래에 경로를 만들 때 문제가 될 수 있기 때문이다. 결론적으로 시작점을 맨 위부터 아래방..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전www.acmicpc.net도저히 어떻게 풀어야할지 감을 못잡았다. 찾아보니 페이지 교체 알고리즘과 관련이 있다는 것을 알았다.  Belady algorithm페이지 교체 알고리즘이란 메모리에 페이지를 효율적으로 올리기 위해 나왔다.페이지를 메모리에 올리는데 비용이 많이 들기 때문이다.   물론 메모리에 몇 종류의 페이지를 올려놓고, 같은 페이지가 나오면 메모리에서 가져다 쓰면 된다.문제는 메모리에 올라와 있는 페이지 말고 새로..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 이 문제의 핵심은 무게들의 합으로 만들 수 없는 무게들 중 가장 작은 값을 원한다는 것이다. 즉, 굳이 모든 무게들의 조합을 구하지 않아도 됨을 암시하고 있다. 작은 무게들의 조합부터 따져야하기 때문에 무게를 기준으로 추들을 먼저 정렬하자. 먼저 누적합으로 접근해보자. 0번째 추부터 k번째 추까지 만들 수 있는 무게의 조합들을 0부터 k까지의 합으로 알 수 있을까? 그럼 0번째 추의 무게가 1, 1번째 추의..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 냅색이긴 한데.. 느낌이 달랐다. 이 문제의 핵심은 가방 하나에 넣을 수 있는 보석들 중, 가장 가치가 높은 보석을 넣어야한다는 것이다. 먼저 떠올린 해법은 가방 하나에 보석 전체를 순회하면서 가장 가치가 높은 것을 넣는 것이었지만, 이는 O(N*K)이고 N과 K는 둘다 300,000이 최대이므로 TLE가 난다. 가방을 하나씩 잡고 검사..

오늘도 어김없이 시원하게 틀렸다. 이 문제의 특징은 각 자리의 숫자를 재배치 할 수 없다는 점이다. 애초에 재비치해서 가장 큰 숫자를 물어볼리가.. 한참을 고민한끝에 다음 해법을 생각했다. K개를 지워서 만들어지는 숫자는 N-K자리 숫자다. 서두에 말했듯 각 자리의 숫자는 재배치 할 수 없다. 따라서 가장 높은 자리의 숫자는 주어진 N자리 숫자의 특정 구간에서의 최댓값이다. 예시로 14315에서 2개의 숫자를 지운다고 해보자. 그럼 최종적으로 만들 숫자는 3자리 숫자이다. 따라서 백의자리 수에 들어갈 숫자는 앞 3개인 1, 4, 3 중 최댓값인 4이다. 왜 나머지 2개인 1, 5는 안되냐면, 둘중 하나라도 선택하면, 문제의 특징 때문에 3자리 수를 다 못채우기 때문이다. 십의 자리는 백의 자리로 선택한 ..

이 문제의 핵심은 최소의 강의실로 모든 강의를 처리해야한다는 것. 처음에는 다음의 알고리즘을 생각했다. [주어진 것] 강의실 배열 : 배열의 요소 하나는 강의실 하나를 의미하며, 들어있는 값은 강의실이 끝나는 시간을 의미함. 강의 배열 : 입력으로 주어지는 강의의 배열 1. 입력받은 강의들을 강의가 끝나는 순서대로 정렬한다. 2. 맨 처음 강의실 배열에는 아무것도 없을테니, 0번째 강의의 끝나는 시간을 넣어놓는다. 3. 1번 강의부터 차례대로 다음 규칙에 맞춰 강의실 배열을 모두 돈다. 3-1. 강의실 배열 요소의 값들 중, 주어진 강의의 시작시간보다 작거나 같은 것이 있다면, 주어진 강의의 끝나는 시간으로 바꾼다. 3-2. 강의실 배열의 요소들을 전부 돌았으나, 3-1을 만족시키는 강의실이 없다면, 강..