알고리즘 문제풀이

백준 14002번 - 가장 긴 증가하는 부분 수열 4 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 10668 4186 3187 40.301% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 둘째 줄에는 가장 긴 증가하는..

백준 11049번 - 행렬 곱셈 순서 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 12013 5537 3943 44.219% 문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6..

백준 13549번 - 숨바꼭질 3 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512 MB 19622 5890 3680 26.760% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진..

백준 1082번 - 방 번호 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 1417 341 272 26.129% 문제 이번에 VIP 회장으로 새로 부임한 백은진은 빅뱅의 위대함을 세계에 널리 알리기 위해서 사무실을 하나 임대했다. 빅뱅은 위대하기 때문에, 사무실의 번호도 되도록이면 커야 한다고 생각한다. 따라서 지금 가지고 있는 돈 전부를 가지고 방 번호를 만들려고 한다. 1층에 있는 문방구에서는 숫자를 판다. 각 숫자의 가격은 서로 다를 수 있기 때문에, 현재 가지고 있는 돈을 이용해서 만들 수 있는 가장 큰 숫자를 만들려고 한다. 예를 들어, 문방구에서 파는 숫자가 0, 1, 2이고, 각 숫자의 가격이 6, 7, 8이고, 백은진이 현재 가지고 있는 돈이 21이라면, 백은진이..

정의 Counter-Clockwise 알고리즘은, 벡터의 외적을 통해서 한 정점을 기준으로 나머지 2개의 정점의 위치 관계를 파악하는 알고리즘이다. 벡터의 외적? ${\vec{a}}$ x ${\vec{b}}$ 는 다음과 같이 정의된다. ( ${\mid{\vec{a}} \mid}$ ${\mid{\vec{b}} \mid}$ ${\sin\theta}$) $\vec{v}$, [v는 a,b의 법선벡터, $\theta$는 a벡터에서 b벡터까지 반시계 방향으로 잰 각의 크기] 각의 크기 $\theta$는 180도인 $\pi$ 이하의 각도. (약 더 큰 각도라면 각의 변환을 통해서 ${0 \leq \theta \leq \pi}$ 내로 변환을 해주어야한다.) 또한 벡터의 평행이동을 활용하면 세 점의 좌표를 통해서 바로 ..

백준 2166번 - 다각형의 면적 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 11944 3025 2067 23.451% 문제 2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. 출력 첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다. 예제 입력 1 4 0 0 0 10 10 10 10 0 예제 출력 1 100.0 출처 www.acmicpc.net/problem/2166..