[펜윅 트리] 펜윅 트리(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가 난다. 가방을 하나씩 잡고 검사..

맨 처음 원했던 스타일은 다음과 같았다. top top top right right right main html은 위와같이 짰다. 가장 먼저 생각한 난관은 grid_left_section 클래스 안에있는 글자를 돌리는 부분이었다. 하지만 transform을 활용하면 가볍게 구현할 수 있을 것 같아 별로 크게 신경쓰지 않았다. 분명 span이 찌그러질 것 같아서 span의 width는 max-content를 줬다. 근데... grid_left_section 안에있는 span을 rotateZ로 돌려도.. width가 전혀 줄어들지 않았다... 혹시나 하는 마음에 grid_right 컨테이너의 너비를 더 줘도 요지부동이었다. 너무 화가난 나머지 개발자 도구를 키고 알아보기로 했다. 수상한 점을 눈치채셨나요? ..