전체 글 썸네일형 리스트형 BOJ 10070 - 벽 (D5) 사용 알고리즘 segment tree + lazy propagation 풀이 뭔가 쉬워보이긴 한데 해보면 바로 해결되지는 않는 그런 문제이다. 세그먼트 트리의 각 노드는 그 노드가 담당하는 구간의 수 범위를 저장한다. 이제 얘를 어떻게 업데이트하고 전파할지가 문제이다. 업데이트할 노드의 원래 수 범위가 [L,R]이고 업데이트할 값이 X라 하자. 일단 이 노드가 업데이트할 구간에 완전히 포함되는 경우를 보자. op = 1의 경우는 L = max(L,X), R = max(R,X)로 하면 된다. 마찬가지로 op = 2는 L = min(L,X), R = min(R,X)로 하면 된다. 업데이트할 구간에 걸치면, 자식 노드들을 봐야하는데 이때 원래 자식 노드들의 [L,R]과 현재 노드의 [L,R]을 비교해서 자식 .. 더보기 BOJ 14701 - 셔틀버스 (P3) 사용 알고리즘 Lazy propagation + binary search 풀이 학생들이 어떻게 이동하는지를 관찰해보자. 중앙을 기준으로 왼쪽에 있는 학생들은 무조건 1번 쪽으로 이동하고 오른쪽에 있는 학생들은 무조건 N번 쪽으로 이동할 것이다. 그리고 한 학생이 빠지게 되면 중간이 비고 2개의 연속된 그룹이 생기는데, 이 그룹끼리는 절대 서로 영향을 주지 않는다. (즉 한쪽 그룹에서 학생이 빠졌는데 다른 그룹의 학생이 이동하는 일은 없다는 뜻이다) 따라서 한명이 일단 빠졌다고 하자. 이 한명이 어떤 형태로 빠지는지는 N이 홀수인 경우와 짝수인 경우로 나눠 관찰하면 쉽게 찾을 수 있다. 이제 필요한 관찰은 다음과 같다. 1. 어떤 학생이 빠질 때 학생들의 번호는 항상 순서대로 유지된다. 2. 어떤 학생이 .. 더보기 BOJ 16682 - 삼원색 (D5) 최근에 세그먼트 트리 문제를 많이 푸는데, 그 이유는 nypc 2-A에서 세그먼트 트리에 당했기 때문이다. 사용 알고리즘 Segment Tree + 좌표압축 + 포함배제 풀이 앞으로는 Cyan, Magenta, Yellow, Red, Green, Blue, Black을 각각 C, M, Y, R, G, B, K라 부를 것이다. 일단 문제를 봤을 때, 색깔을 고려하지 않으면 떠오르는 문제가 하나 있다. https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,.. 더보기 BOJ 25639 - 수열과 최대 상승 쿼리 (P1) 20240816 추가) 지금 보니 이 문제는 그냥 금광세그 기초 문제이다. 아래에 적혀있는 풀이는 금광 세그를 자력솔(!)한 것이다. 사용 알고리즘Segment Tree 풀이세그먼트 트리의 각 노드에는 3개의 값을 관리한다.(1) 담당하는 구간의 최댓값 (N_max)(2) 담당하는 구간의 최솟값 (N_min)(3) 담당하는 구간의 최대 상승 값 (N_up) (1), (2)는 G1짜리 간단한 문제이므로 생략한다. (3)을 어떻게 처리할지를 생각해야 하는데, 리프 노드면 구간이 1이므로 그냥 0이다.그럼 구간 크기가 2 이상인 노드의 최대 상승 값은 어떻게 구할까? 바로 max(R_max - L_min, R_up, L_up)이다. 이때 L은 현재 노드의 왼쪽 자식에서의 값이고 R은 오른쪽 자식에서의 값이다.. 더보기 합세그 이분탐색 보호되어 있는 글입니다. 더보기 sum_{i=1}^n floor(n/i) O(sqrt(n)) 계산 보호되어 있는 글입니다. 더보기 solve G5~G1 (1) G5~G1 문제를 각각 1개씩 랜덤으로 풀어보기로 했다. 아래에 나오는 체감 티어는 주관이므로 신뢰하지 말자. (티어 옆에 +는 보통 그 티어의 난이도보다 어려웠단 뜻이고, -는 쉬웠단 뜻이다.) Gold 5 : Ordinary Ordinals (BOJ 24930) 풀이 : 수학(+분할정복 거듭제곱) 풀이 시간 : 약 10분 체감 티어 : Gold 5 문제를 이쁘게 정리하면 An=2An−1+1 이 나온다. (단, A_0 = 2, A_1 = 4) 이제 점화식을 일반식으로 바꾸면 An=2n−1A1+2n−1−1 이다. 2^(n-1)은 분할정복으로 O(logN)에 빠르게 구할 수 있으므로 O(logN)에 답을 구할 수 있다. using n.. 더보기 제3회 한국항공대학교 프로그래밍 경진대회(KAUPC) 오픈콘 풀이 백준 풀다가 할 게 없어서 대회가 있길래 참여했다. 체감 난이도 : A 더보기 이전 1 ··· 7 8 9 10 11 12 13 다음 목록 더보기
