문제 링크 : https://www.acmicpc.net/problem/17386 17386 - 선분 교차 1 본문 2차원 좌표 평면 위의 두 선분 $L_1, L_2$가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. $L_1$의 양 끝 점은 ($x_1, y_1$), ($x_2, y_2$), $L_2$의 양 끝 점은 ($x_3, y...

문제 링크 : https://www.acmicpc.net/problem/13460 13460 - 구슬 탈출 2 본문 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는...

문제 링크 : https://www.acmicpc.net/problem/4355 4355 - 서로소 본문 양의 정수 $n$이 주어졌을 때, $n$보다 작은 양의 정수 중에서 $n$과 서로소인 수 개수를 구하는 프로그램을 작성하시오. 두 정수 $a$와 $b$가 서로소가 되려면 $x > 1, y > 0, z > 0$이면서, ...

문제 링크 : https://www.acmicpc.net/problem/16214 16214 - N과 M 본문 임의의 자연수 $N$과 $M$이 주어져 있다. $A^B$를 $A$의 $B$승이라고 할 때, 수열 $N$, $N^N$, $N^{(N^N)}$, $N^{(N^{(N^N)})}$, … 의 수들을 $M$으로 나눈 나머지는 수열의 어느 지...

문제 링크 : https://www.acmicpc.net/problem/13970 13970 - Power towers 본문 Suppose that we have a non empty list of positive integers: $[x_1, x_2, \cdots, x_N]$. The power tower corresponding to...

문제 링크 : https://www.acmicpc.net/problem/22940 22940 - 선형 연립 방정식 본문 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 즉, 다음과 같은 식을 의미한다. [A_1x_1 + A_2x_2 + \cdots + A_nx_n = B] 선형 연립 방정식...

문제 링크 : https://www.acmicpc.net/problem/2247 2247 - 실질적 약수 본문 두 자연수 $A$와 $B$가 있을 때, $A = BC$를 만족하는 자연수 $C$를 $A$의 약수라고 한다. 모든 자연수 $N$은 1과 자기 자신($N$)을 약수로 갖게 된다. 실질적 약수(actual divisor)라는 것이 ...

문제 링크 : https://www.acmicpc.net/problem/1006 11689 - GCD(n, k) = 1 본문 자연수 $n$이 주어졌을 때, $\text{GCD}(n, k) = 1$을 만족하는 자연수 $1 \leq k \leq n$ 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 $n$ ($1 \leq n...

최장 공통 부분 문자열 LCS란? “Longest Common Subsequence”의 약자로, 두 문자열의 공통 부분 문자열 중 그 길이가 가장 긴 것을 말한다. LCS 알고리즘이라고 하면 일반적으로 그 공통된 부분 문자열을 찾는 과정을 말한다. 부분 문자열이라고 해서 찾는 문자열이 꼭 붙어있을 필요는 없고, 문자들이 각각 떨어져있어도 된...

배낭 채우기 알고리즘 냅색이란? 한 여행가가 가지고 가는 배낭이 있다. 배낭에 담을 수 있는 무게의 최댓값은 W이다. 여행가는 여행을 가기 위해 필요한 짐들을 배낭에 넣어 가지고 갈 계획을 세우고 있다. 각 짐들은 일정한 무게와 가치를 지니고 있다. 여행자는 이 짐들을 배낭에 최대한 넣어 가치의 합이 최대가 되도록 짐을 싸려고 한다....