문제 캔디 분배 https://www.acmicpc.net/problem/3955 각 봉지에 $K$개의 사탕이 들어있을 때, $y$봉지를 사서 $X$명에게 $x$개씩 나누어주고 1개가 남도록 하는 최소의 양의 정수 $y$를 구하는 문제. (단, $y \le 10^9$이며 $x > 0, y > 0$) 복잡도 분석 time comple...

문제 줄 세우기 https://www.acmicpc.net/problem/2252 $N$명의 학생들을 키 순서대로 줄을 세워야 합니다. 두 학생의 키를 비교한 $M$개의 결과가 주어질 때, 이 조건을 만족하는 줄 세우기 결과를 출력하는 문제입니다. 복잡도 분석 time complexity : $O(N + M)$ 정점의 개수...

문제 BOJ 14565 역원 구하기 정수 $N, A$가 주어졌을 때, 집합 $Z_N = {0, 1, \dots, N-1}$에서 다음을 구하는 문제다. 덧셈에 대한 역원 $b$: $(A+b) \bmod N = 0$ 곱셈에 대한 역원 $c$: $(A \cdot c) \bmod N = 1$ 단, 곱셈 역원은 항상 존재하지 않을 수 있으므로,...

think 260331 먼 옛날에는 돌아오지 않을 사람을 그리워하면서… 그러면서도 열심히 배우고 나에게 답답한 상황이 와도 인내하던 시절이 있었다. 왜 그렇게 살았지? 대부분의 사람이 진실을 보는 눈이 없다. 학교 신문에 쓰인 기사를 본다. 세상이 이렇게 돌아가는데 모두들 좋은 소리. 시덥잖은 이야기. 스스로 배웠다고 자신만만한 사람들의 글 수준...

think 260330 지나간 일도 씁쓸한 일들도 별 의미가 없다. 누군가에겐 그냥 남을 소비하고 재미있는 일이었을지 모르지만 나는 그런 일은 없었다. 내 평생 당당하게 살았다고 자부할수 있다. 누군가 보기에 웃기다고 할지 모르지만… 정말 시간이 흐르고 내 이야기를 다 풀어낸다면 그런 사람도 이해할 날이 올지도 모르겠다 최근에는 그냥 계속 공부를...

문제 배달 https://www.acmicpc.net/problem/1175 $N \times M$ 격자에서 두 개의 선물(‘C’)을 모두 방문하는 최소 시간 탐색. 제약: 같은 방향으로 두 번 연속 이동 불가. 복잡도 분석 time complexity : $O(N \cdot M \cdot 5 \cdot 4)$ space comp...

문제 BOJ 1131 숫자 각 숫자 $N$에 대해 $S_K(N)$ = (각 자리 숫자의 $K$제곱 합)으로 정의하고, 수열 $N, S_K(N), S_K(S_K(N)), \dots$ 에서 등장하는 값들의 최솟값을 $m(N)$이라 하자. 주어진 구간 $[A, B]$에 대해 $\sum_{N=A}^{B} m(N)$ 을 구한다. (입력: $A, B, K$,...

문제 가장 긴 증가하는 부분 수열 5 (https://www.acmicpc.net/problem/14003) 최대 100만 개의 원소를 가진 수열에서 LIS의 길이와 실제 수열을 출력하는 문제. 복잡도 분석 time complexity : $O(N \log N)$ LIS 길이를 구하는 과정: $N \times \log N$ ...

문제 동물원 (https://www.acmicpc.net/problem/1309) 2xN 크기의 격자에 사자를 배치하되, 가로/세로로 인접하지 않게 배치하는 모든 경우의 수를 구하는 문제. (사자가 0마리인 경우 포함) 복잡도 분석 time complexity : $O(N)$ - 각 행마다 3가지 상태를 상수 시간 연산으로 결정하며 $N$번 반...

문제 가장 긴 증가하는 부분 수열 2 (https://www.acmicpc.net/problem/12015) $N = 1,000,000$인 수열에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 출력하는 문제. 복잡도 분석 time complexity : $O(N \log N)$ - $N$개의 원소에 대해 각각 이진 탐색(Lower Bound)...