D.JOUNG

문제 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Silver 2 이분 탐색 문제 풀이 문제의 내용을 요약하자면, 주어진 K개의 랜선을 잘라 N개 이상의 (동일한 길이의) 랜선을 만들어야 하는데, 그 때 만든 랜선의 길이가 가장 긴 경우의 길이를 구하는 문제이다. 예제의 경우 길이가 차례대로 802, 743, 457, 539 인 네 개의 랜선이 주..

문제 : https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Silver 3 구현 문제 풀이 수열을 구성해 출력하는 종류의 문제를 푸는 방법은 일반적으로 두 가지다. 하나는 수열 크기 만큼의 배열을 구성해 각 인덱스에 알맞는 수를 채워넣은 후 배열을 출력하는 것이고, 다른 하나는 수열의 각 인덱스 자리마다의 규칙을 파악해 수열의 앞 숫자부터 계산하여 출력하는 것이다. 해당 문제에서도 잘 ..

문제 : https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 512 MB Silver 2 문자열, 슬라이딩 윈도우 문제 풀이 슬라이딩 윈도우란 '두 포인트' 알고리즘응 응용한 알고리즘으로, 두 포인터 사이의 구간을 지정하고 해당 구간을 n칸씩 옮겨가며 문제를 해결하는 방식이다. 어떤 조건을 만족하는 연속된 구간의 개수를 구할 때 유용하게 사용할 수 있으며, 두 포인터와 마찬가..

문제 : https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 256 MB Gold 4 정렬, 이분탐색, 두 포인터 문제 풀이 시간 제한이 2초이고, 주어지는 수의 개수가 최대 2000개다. 단순히 반복문만을 이용해 문제를 풀이할 경우 시간복잡도가 n의 3승 이상으로 늘어나기 때문에, 시간을 단축할 수 있는 방법을 찾아봐야 한다. 나는 모든 수의 조합을 검토할 수 있지만, 시간 복잡도를 n의 2승 내에 풀 수 있는 '두 포인터'..

문제 : https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Gold 5 기하학 / 다각형의 넓이 문제 풀이 다각형의 각 꼭짓점 좌표가 순서대로 주어지기 때문에 첫 번째 점에서 각 점으로 선을 이어 만들어지는 삼각형들의 넓이를 모두 합해주면 된다. 흔히 신발끈 공식이라고 불리는 방법이다. 신발끈 공식을 이용하면 일반 다각형과 오목 다각형의 넓이 까지 수월하게 구할 수 있다. 그 원리는 아래 그림과 같다. 일반 다..

문제 : https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 0.25초 512 MB Gold 3 기하학 / 선분 교차 판정 문제 시간 제한이 0.25초이므로 사실 상 계산 공식을 통해 한 번에 답을 도출하라는 뜻이다. 처음에는 풀이법이 금방 생각나서 이게 왜 골드 3 짜리 문제인지 의문이었지만, CCW 알고리즘을 사용하지 않고는 기울기를 구하는 과정에서 소수점 오차까지 고려해야하기 때문인 것 같았다. CCW 알고리즘을 사용..

문제 : https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 128 MB Gold 5 수학 / 브루트포스 문제 풀이 최대공약수(G)와 최소공배수(L)이 주어졌을 때, 역으로 두 수 a, b를 구해야하는 문제다. 또한, a, b의 쌍이 여러개일 경우 a+b의 값이 최소가 되는 쌍을 찾아야 한다. 다 재쳐두고 먼저 G과 L에 대한 공식과 규칙들을 정리해봤다. - G * L = a * b - a = G ..

문제 : https://www.acmicpc.net/problem/1614 1614번: 영식이의 손가락 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3 위와같이 세면 총 15를 셀 수 있다. 2번째 손가락을 3번 이용했으니 더 이상 사용할 수 없다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Silver 3 수학 / 많은 조건 분기 문제 풀이 영식이는 엄지손가락->새끼손가락->엄지손가락 순서로 세며, 왼쪽 손을 사용하기 때문에 엄지 손가락이 1번, 새끼 손가락이 5번, 그리고 다시 엄지 손가락이 9번째, 그 후 다시 새끼 손가락이 13번째 카운트가 된다. 13번 손가락을 셀 동안, 엄지와 소지는 두 번씩만 세지는 것에 검지, ..

문제 : https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 32 MB Silver 5 수학 / 두 포인터 문제 풀이 자연수 N의 범위가 1부터 10,000,000 까지이기 때문에, 연속된 자연수로 이루어진 집합의 수는 nx(n-1)/2 = 49,999,995,000,000 이며, o(n)의 값이 2초 안에 처리할 수 있는 연산량을 훌쩍 넘어간다. 따라서 반복을 줄일 수 있는 ..

문제 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 256 MB Gold 3 수학 / 누적합 문제 풀이 누적합 알고리즘을 응용해서 푸는 문제다. 하지만 시간 제한이 1초이므로 단순히 누적합 배열만 가지고 계산하려고 하면 시간 초과를 뱉어낸다. 또한 입력받는 수 A의 범위가 0