PS 이야기 - mysetting

2:03 5/31

blog.myungwoo.kr

mobile screenshot relative

2:03

blog.myungwoo.kr

mobile screenshot

PS 이야기
https://blog.myungwoo.kr/

Problem Solving 공부를 하다

저작도구: TISTORY

최종 피드 수집: 2024-09-01 22:17

전체 (21)

1y

Bostan Mori 알고리즘

Bostan Mori 알고리즘은 2020년 8월 Alin Bostan과 Ryuhei Mori가 작성한 이 논문에 소개되어 있는 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 알고리즘이다. Bostan Mori 알고리즘

공부

0014

1y

선형점화식 빠르게 계산하기

$D_0, D_1, \cdots, D_{k-1}$과 $c_1, c_2, \cdots, c_k$가 주어졌을 때, $i \ge k$인 $D_i$를 다음과 같은 선형점화식으로 구할 수 있다고 하자.
$$D_i = \sum_{j=1}^{

공부

001

1y

다항식 나눗셈의 몫을 빠르게 구하는 방법

차수가 $n$인 다항식 $f(x) = c_0 + c_1x^1 + c_2x^2 + \cdots + c_nx^n (c_n \ne 0)$가 있다. 그리고 차수 $m$인 다항식 $g(x) = d_0 + d_1x^1 + d_2x^2 + \

공부

000

1y

Nexon Youth Programming Challenge(NYPC) 2022 본선 풀이

1214 A. 조약돌 순서
처음에 $[1, 2, 3, ..., K]$이 적혀있는 크기 $K$인 배열 $A$가 있다. $i = 1$부터 시작하여 $A_i$와 $A_{i+1}$의 값을 바꾼다. 그리고 $i$를 $1$ 증가시킨다. 만약

000

1y

Nexon Youth Programming Challenge(NYPC) 2022 Round 2-B 풀이

1. 비트문자열
특정 규칙으로 만들어지는 길이 $2^i$인 이진문자열 $S_i$가 있다. 구간 $[s, e]$가 있을 때, $S_i$의 $s$ 번째 문자부터 $e$ 번째 문자까지 문자 중에서 1의 개수를 구하는 문제다. 단, 하나

해법

00137

2y

Nexon Youth Programming Challenge(NYPC) 2022 Round 2-A 풀이

1. 사진작가
정수로 이루어진 길이 $N$인 배열 $A$가 주어진다. 이 배열의 부분배열 중에서 같은 수를 여러 개 포함하고 있지 않은 부분수열이 있다. 그러한 부분수열 중에서 길이가 가장 큰 부분수열의 길이를 구하는 문제다.

해법

008

2y

`22 현대모비스 알고리즘 경진대회 예선 후기

글을 쓰는 날짜 기준, 오늘(2022년 7월 1일) 오후 1시 30분부터 5시까지 약 3시간 30분 동안 `22 현대모비스 알고리즘 경진대회 예선에 참가했다. 문제 내용에 대한 언급은 대회 참가 전 서약 때문에 할 수 없어서 채점

잡담

003

2y

Google Code Jam 2022 Round 2 풀이 및 후기

오랜만에 풀이 및 후기 글을 적는다. Google Code Jam은 매년 꾸준히 참가해왔다. 그동안 PS 공부할 시간적 여유가 없어서, 참가만 해왔었고, 다행히 최근에는 육아휴직으로 시간이 생겨서 밀린 PS 공부를 했다. 주로 최

해법

000

2y

Hu-Tucker Algorithm

유용한 링크: MIT 강의 자료

어떤 문자열이 있고, 각 알파벳에 바이너리를 할당한다. 할당된 바이너리는 어떤 것이 다른 것의 prefix가 되면 안된다. 문자열을 알파벳에 할당된 바이너리로 표현할 때 바이너리의 크기를 최소화

공부

000

2y

Skew Heap

유용한 링크: 위키백과, Skew heap visualization, NTU 강의자료

Skew heap(혹은 self-adjusting heap)은 이진트리로 구현된 힙 자료구조다. 우리가 배운 기본적인 힙은 완전이진트리이므로

공부

000

3y

Nexon Youth Programming Challenge(NYPC) 2021 예선 풀이

1. 계단
$1$ 층부터 $M$ 층까지 총 $M$ 개의 층이 있는 건물이 있다. 건물의 $F$ 층에서 시작하여 계단을 통해 한 층을 올라가거나, 엘리베이터를 타고 원하는 층으로 이동할 수 있다. 정확히 $N$ 번 계단을 통해 층을

해법

002

3y

Z-function

길이가 $n$인 문자열 $s$가 있다. $1 \leq i \lt n$인 $i$에 대해 $z[i]$를 $i$에서 시작하는 suffix와 $s$의 가장 긴 prefix의 길이라고 정의하자. 편의상 $z[0] = 0$이다. 이러한 $z

공부

000

3y

Li Chao Tree (Dynamic Convex Hull Optimization)

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코

공부

000

3y

IOI2020 Day2 mushrooms 풀이

문제 및 채점: oj.uz

번호가 0부터 $N-1$까지 매겨진 버섯 $N$ 개가 있다. 버섯은 두 종류로 구분할 수 있는데 눈으로 구분하기 힘들다. 기계를 사용하여 임의의 버섯들을 선택하여 순서를 정해 일렬로 기계에 넣을 수

IOI2020

000

3y

IOI2020 Day2 biscuits 풀이

문제 및 채점: oj.uz

$K$ 개 종류의 비스킷이 있고, 각 종류는 번호가 1부터 $K$까지 매겨져 있다. $i$번 종류의 비스킷의 맛 점수는 $2^{i-1}$이며, $i$번 종류의 비스킷은 $a[i]$ 개 있다. 비스킷

IOI2020

000

3y

IOI2020 Day2 stations 풀이

문제 및 채점: oj.uz

$N$ 개의 정점으로 이루어진 트리가 주어진다. 각 정점에 $0$ 이상 $K$ 이하의 수를 서로 다르게 적는다. 수 $i$가 적힌 정점을 정점 $i$라고 하자. 정점 $s$에 인접한 정점에 적힌 수들

IOI2020

000

3y

IOI2020 Day1 plants 풀이

문제 및 채점: oj.uz

서로 다른 크기를 가지고 있는 식물 $N$ 개가 원으로 배치되어 있다. 편의상 $1$번 식물을 기준으로 시계 방향으로 차례대로 $N$ 번까지 번호가 매겨져 있다. $i$ 번 식물을 포함하여 시계 방향

IOI2020

000

3y

IOI2020 Day1 tickets 풀이

문제 및 채점: oj.uz

티켓은 $N$ 개의 색 중 한 가지 색을 띄며, 각 색마다 $M$ 개의 티켓이 있다. 티켓에는 수가 적혀있는데, 티켓에 적힌 수는 서로 다를 수 있다. $K$ 번의 라운드를 진행할거고 각 라운드마다

IOI2020

000

3y

IOI2020 Day1 supertrees 풀이

문제 및 채점: oj.uz

정점이 $N$ 개인 양방향 그래프가 있다. 이 그래프에서 정점 $i$와 정점 $j$ 사이의 단순 경로의 수는 $p[i][j]$이다. $p[i][i] = 1$이며, $0 \leq p[i][j] \leq

IOI2020

000

3y

Nexon Youth Programming Challenge(NYPC) 2020 예선 풀이

1. S OR T
스페이스(S)와 탭(T)을 입력한 순서가 주어졌을 때, 총 몇 칸 띄어지게 되었는지 구하는 문제다. 단, 탭 크기는 4다.

문자열을 입력받아서 S가 나오면 칸 수를 1 늘려주고, T가 나오면 칸 수를 현재 칸

해법

001