세그먼트 트리 세그먼트 트리란? 배열에서, 구간에 대한 쿼리를 실현할 때 사용될 수 있는 자료구조 특히, 구간에 대해 값을 변경하는 쿼리가 있을 경우 복잡도에서 효과적 예시 상황 배열 $A$가 있고, 여기서 아래 2가지 연산을 수행할 수 있는 문제를 생각해보자. 구간 $l$, $r$ ($l...

문제 링크 : https://www.acmicpc.net/problem/1395 1395 - 스위치 본문 준규네 집에는 총 $N$개의 스위치가 있고 이를 편하게 $1$번부터 $N$번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다. 준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 $A$번...

분리 집합 / 유니온 파인드 분리 집합이란? 각 정점을 그룹화시켜서 관리할 때 사용되는 자료구조 + 알고리즘 - 그룹화한다는 것은, 문제 조건에 의해 관계를 만드는 경우이기도 하고, subproblem을 푼 이후 중복연산을 하지 않도록 관계를 기록하는 경우로도 사용 가능하다 분리 집합은 각 정점이 같은 그룹에 속해있는지 아닌...

무려 1년이 넘는 시간동안 contest를 하지 않았었다. 애초에 PS 자체를 안하기도 했고, 할 시간도 없었고 해서.. 가장 최근에 참여한 contest가 Round 764 (Div. 3) 이다. 무려 작년 1월 개최된 contest다. 현재 rate는 1385, Expert를 찍어봤다고 얘기하기도 무안한 점수다. ( 정리할 필요성도 못 느낄 정도...

최장 증가 부분 수열 LIS란? “Longest Increasing Subsequence”의 약자로, 배열의 원소들 중 일부만 골랐을 때, 그 수열의 원소들이 이전의 원소보다 크다는 조건을 만족하면서 그 길이가 가장 큰 수열을 만족하도록 하는 수열을 찾는 알고리즘이다. 쉽게 얘기하면, 부분수열을 골랐을 때 수열이 모든 부분에서 증가하는 모...

문제 링크 : https://www.acmicpc.net/problem/3955 3955 - 캔디 분배 본문 창영이는 선영이가 사탕을 공평하게 나누어주지 않으면 친구들을 때릴정도로 사탕을 좋아한다. 따라서, 선영이는 다음 파티에 사용할 사탕을 구매하기 전에 고민을 하기 시작했다. 만약 파티에 $K$명이 참가한다면, 공정하게 나누어주려면...

문제 링크 : https://www.acmicpc.net/problem/11030 11030 - SUPER HATS 본문 양의 정수 $a, b$에 대해서, $a$의 $b$ 초지수승은 $a ↑↑ b$와 같이 나타낸다. 초지수승의 정의는 다음과 같다. [a ↑↑ 1 = a] [a ↑↑ (k + 1) = a ^ {(a ↑↑ k)}] 따라서...

문제 링크 : https://www.acmicpc.net/problem/25568 25568 - 피라미드 본문  $3$가지 색상의 블록으로 이루어진 블록 피라미드가 있다. 피라미드는 $N$행으로 이루어져 있고, $i$ ($1\leq i \leq N)$행은 $i$개의 블록으로 이루어져 있다. 또한, $i$행의 $j$번째 블록을 $(i,...

문제 링크 : https://www.acmicpc.net/problem/16129 16129 - 뚜루루 뚜루 본문 최근 아기 석환이라는 노래가 큰 인기를 끌고 있다. 이 노래는 귀여운 아기 석환 캐릭터가 등장하는 동영상과 중독성 있는 뚜루루 뚜루 후렴구로 전국 각지의 학생들과 직장인들의 마음을 사로잡았다. 강남의 직장인 gs12117 역...

CCW 알고리즘 LCS란? “Counter ClockWise”의 약자로, “평면에 놓인 3개의 점에 대한 방향관계를 구하는 방법” 중 하나이다. CCW는 ‘반시계 방향’이라는 뜻을 가지고 있는데, 알고리즘의 반환값이 “점들의 관계가 반시계 방향이어야 양수를 반환”하기 때문이라고 생각한다. 알고리즘 해법 이 단계에서는 CCW가 무엇인지...