본문 바로가기

백준30

[알고리즘] 택시 (백준 1649번) 1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 2020. 11. 3.
[알고리즘] 부분합 (백준 1806번) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 연속된 구간의 합이 S 이상이 되는 구간의 최소길이를 구하라는 문제다. '연속된 구간' 이라는 키워드에서 보면 알 수 있지만 무조건 투포인터 문제다. Solution min_length는 최소길이, sum은 list[before] ~ list[after] 까지의 구간 합이다. 반복문을 돌린다. sum이 S 이상 min_length를 현재 구간길이랑 비교해서 업데이트한다. before < after 이면 sum에서 list[before]를 뺸 후 b.. 2020. 10. 29.
[알고리즘] 내려가기 (백준 2096번) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍 문제다. 최소, 최대 값을 묻는 문제인데 이전에도 자주 풀어 본 적이 있는 유형이다. Solution 우선 max_dp와 min_dp로 나누어서 각각 최대값, 최소값을 구하는 dp 배열로 만든다. 여기서 최적화할 수 있는 방법은, 최대, 최소값을 구하기 위해서는 max_dp[i][3] 과 max_dp[i-1][3] 만 필요하면 되기 때문에 행이 2개만 있으면 된다. 그래서 max_dp, min_dp 에 필요한 원소 개수는 12개만 있으면 된다. N만큼 반복.. 2020. 10. 29.
[알고리즘] 수 묶기 (백준 1744번) 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디하게 풀 수 있는 문제이다. 수를 정렬했을 때 양수 기준으로 가장 큰 수부터 곱해나간다. 단, 1과 쌍이 지어지는 경우는 그냥 더하는게 더 수가 크기 때문에 항상 list[i] * list[i+1]와 list[i] + list[i+1] 중 어떤게 더 큰지 비교해가면서 더한다. 음수는 반대로 가장 작은 수부터 곱해야지 가장 큰 값이 나온다. EX) (-5 * -1 = 5) > (-4 * -1 = 4) Solution import java.io.Buffere.. 2020. 10. 22.

티스토리툴바