BOJ 썸네일형 리스트형 2월 PS (1) 푼 것들 중 의미있는(?) 것을 정리했다.1. 아니메컵 1쿨딱히 시간을 재고 풀진 않았다. M은 이상한 풀이밖에 생각이 안나서 에디토리얼을 보고 풀었다. A (BOJ 27310. :chino_shock:)23년에 푼 문제다.길이, 콜론 개수, 언더바 개수를 세고 그대로 계산하면 된다. B (BOJ 27311. 치노의 라떼 아트 (Easy))일단 #의 min x, max x, min y, max y를 가지고 정사각형을 이루는지 확인하자. 그리고 그 내부만 본다고 하자. 배열을 90도씩 돌려가면서 확인하면 일반성을 잃지 않고 '.'이 왼쪽 위에 있다고 가정할 수 있다. 이를 기준으로 (1) '.'이 정사각형을 이루는지, (2) 왼쪽 위에 '.'이 있는지를 확인하면 된다. C (BOJ 27312. 운영진에게 .. 더보기 BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5) PS를 진짜 제대로 하겠다는 마음가짐으로 역겨운 것도 다 풀기로 했다. 하이퍼 시리즈는 유명하다... 차원이 말도 안되게 큰 문제들이다. 얘는 이 문제를 11차원으로 늘린 문제이다. 그럼 그냥 11차원 prefix sum을 박으면 되느냐? 아쉽게도 아니다. prefix sum table을 채우는 원리는 포함-배제 원리이다. 이는 중복하여 더하고 빼는 구간들을 처리하는 것이다. 그래서 11차원 prefix sum을 채우려고 식을 세워보면 무려 2^11(=2048)개의 값을 더하고 빼는 형태가 나온다. 그래서 table을 채우는데에는 총 O(2^11 * nmopqrstuvw)가 나와 전체 서브태스크를 풀 수 없다. (아마 섭태3까지는 풀릴 것 같다.) 다행히도 얘를 O(11 * nmopqrstuvw)에 채울.. 더보기 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.. 더보기 BOJ 14181 - 함수와 쿼리 (D3) CHT 처음 배울때 봤다가 이게 왜 CHT지 하고 탈주했다. http://boj.kr/14181 14181번: 함수와 쿼리 첫째 줄에 배열 a의 크기 n (1 ≤ n ≤ 105)가 주어지고, 둘째 줄에 배열 a[1], a[2], ..., a[n]이 주어진다. (0 ≤ a[i] ≤ 104) 다음 줄에는 쿼리의 개수 m (1 ≤ m ≤ 105)가 주어지고, 다음 m개의 줄에는 쿼리 www.acmicpc.net 풀이) Li-chao + Segment Tree 점화식을 세우기 영 쉽지 않아 보인다. 그러므로 정의에 따라 점화식을 관찰하자. f(1,j)=a[j] f(2,j)=min(f(1,j),f(1,j−1))+a[j] =min(2∗a[j],a[j−1]+a[j]).. 더보기 BOJ 1739 - 도로 정비하기 티어: D5 (체감 D5) 알고리즘: 2-SAT 여기서는 가로 도로를 행, 세로 도로를 열로 표기한다. 어떤 버스가 (a,b)에서 (c,d)로 갈려면 다음 2가지 중 하나를 이용해야 한다. (도로를 최대 2개밖에 이용하지 못하기 때문) 1. a행, d열을 이용한다. 2. c행, b열을 이용한다. 일단 a≠c, b≠d라고 가정하고 예제 1의 테스트케이스 1을 보자. 위 그림은 테스트케이스 1번에서 (1,1)에서 (6,6)으로 가는 버스를 나타낸 것이다. 빨간색 경로는 1행과 6열을 이용해서 (1,1)에서 (6,6)으로 간다. 파란색 경로는 1열과 6행을 이용해서 (1,1)에서 (6,6)으로 간다. 위를 통해 (a,b)에서 (c,d)로 갈려면 a행, d열을 이용하거나 c행, b열을 이용해야 함을 알 수 있다.. 더보기 이전 1 다음
