2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제 이해 & 기본 개념 n개의 점으로 이루어진 다각형의 넓이를 구하는 문제 신발끈 공식을 이용하면 쉽게 풀 수 있다. 중요 포인트 N이 최대 10,000까지, 각 좌표의 절댓값이 최대 100,000이므로 Long 타입을 선택해야 한다. 신발끈 공식에서는 좌표를 이어지도록 나열하는 것이 중요한데, 해당 문제에서는 다각형을 이루는 순서대로 입력이 들어온다. 만약, 순서가 랜덤이라면 하나의 다각형으로 고정 되지 않기에 문제가 성립되지 않는다. 스페셜 저지면 가능하겠지만, 일반 문제이기 때문에..
1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 이해 & 기본 개념 아래 3가지 방법을 통해 입력 받은 수를 1로 만드는 것 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 최소 횟수를 구해야하는 문제 3으로 나누는게 1을 빼는 것보다 수가 훨씬 작아지므로 자칫하면 그리디 문제로 오해할 수 있다. ex) n = 10 10 -> 9 -> 3 -> 1 10 -> 5 -> 4 -> 2 -> 1 이처럼 가능한 큰 수로 나누는 것보다 1을 먼저 빼는 경우가 최소 횟수가 될 수도 있기 때문에 dp를 이용한다. 최종 풀이 파란색이 처음 계산 되는 부분 빨간색이 중복 계산 되는 ..
11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 이해 & 기본 개념 수열에서 증가하는 부분 (이어질 필요 x)에서 가장 합이 큰 경우를 찾아야하는 문제 중요 포인트 모든 경우의 수를 보는 방법도 있긴 하겠지만, 중복된 연산이 많이 발생 중복된 연산을 줄이기 위해 dp를 사용하면 간단하게 풀 수 있음 최종 풀이 점화식 dp[i] = max(dp[i], dp[j] + a[i]) i는 현재 위치, j는 이전에 선택된 원소의 위치 dp[i]는 i까지의 최..
16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 문제 이해 & 기본 개념 그래프와 방문 순서가 주어진다. 해당 그래프에서 입력받은 순서가 dfs로 방문 가능한지를 체크하는 문제 해당 문제는 방문 순서에 대한 기준을 두지 않았다. 즉, 어떤 순서로 방문을 해도 dfs로 방문 가능한 순서이기만 하면 된다. 중요 포인트 n이 10만까지 들어오므로, dfs를 완전히 수행하면 시간 초과 dfs로 접근하되, 수행 시간을 줄여아한다. 최종 풀이 dfs의 경우 여러 자식들 중 어떤 자식을 ..
4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 문제 이해 & 기본 개념 s = a ^ n을 만족하는 최대의 n을 구해야하는 문제이므로, a의 길이가 가장 작은 경우를 찾아야하는 문제이다. 해당 문제는 kmp 알고리즘 중에서 최대 접두부 테이블을 이용하여 풀 수 있는데, 예시로 "ababab" 에 대한 최대 접두부 테이블은 아래와 같다. a b a b a b 0 0 1 2 3 4 테이블을 잘 보면 처음 ab에선 0 0이고 그 이후부턴 1 2 3 4로 계속 이어지는 것을 볼 ..
