Problem Solving
[백준] 11660번 구간 합 구하기 5(feat. 누적 합, 다이나믹 프로그래밍)
[백준] 11660번 구간 합 구하기 5(feat. 누적 합, 다이나믹 프로그래밍)
2023.01.12https://www.acmicpc.net/problem/11660 문제 접근 첫 번째 단계 문제의 조건을 정리하면 아래와 같다. N*N개의 수가 N*N 크기의 표에 채워져 있고, (x1, y1) 부터 (x2, y2) 까지 합을 구하는 프로그램을 작성해야 한다. (x, y)는 x행 y열을 의미한다. 그리고 입력 조건을 보면, 합을 구해야 하는 연산의 횟수가 M의 범위가 (1
[백준] 1904번 01타일(feat. 다이나믹 프로그래밍, 메모리 제한)
[백준] 1904번 01타일(feat. 다이나믹 프로그래밍, 메모리 제한)
2023.01.03https://www.acmicpc.net/problem/1904 문제 접근 첫번째 단계 문제의 조건을 정리하면 아래와 같다. 0과 1 타일이 있는데, 0타일은 00 이런식으로 두개씩 사용가능하다. 1타일은 낱개로 사용이 가능하다. N이 주어졌을 때, N크기의 2진수열을 만든다면, 만들 수 있는 수열의 갯수를 구하는 것이다. 예를 들어, n = 1일 때는 1만 단독으로 사용이 가능할 것이다. n = 2 일 때는 00 or 11 이렇게 구성이 가능할 것이다. 이번에는 n = 3일 때를 생각해보자. 세칸이 있는데, 해당 3칸을 1칸과 2칸으로 나누어 생각해본다면, n = 1일때와 n = 2 일때를 포함하고 있는 것을 파악할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다.(최적 부분 구조) n = 3일..
[백준] 18353번 병사 배치하기(feat. 다이나믹 프로그래밍, LIS알고리즘)
[백준] 18353번 병사 배치하기(feat. 다이나믹 프로그래밍, LIS알고리즘)
2022.09.14첫번째 단계 문제를 살펴보자. N명의 병사가 무작위로 나열되어 있고, 각 병사는 특정한 값의 전투력을 보유하고 있다. 우리는 병사를 배치할 건데, 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치할 것이다. 다시말해, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 그리고, 배치 과정에는 특정 위치에 있는 병사를 열외시키는 방법으로 이용해야 한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 해야한다. 1. 큰 문제를 작은 문제로 나눌 수 있다.(최적 부분 구조) 이 문제는, 이 문제는 병사들을 전투력을 기준으로 내림차순으로 정렬시키면서, 가장 많은 병사가 남아있도록 해야한다. 특정 병사를 열외할지 말지로 문제를 쪼갤 수 있다. 따라서, 이 문제는 최적 부분 구조를 만족한다. ..
[백준] 14501번 퇴사(feat. 다이나믹 프로그래밍)
[백준] 14501번 퇴사(feat. 다이나믹 프로그래밍)
2022.09.06https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 접근 첫번째 단계 문제를 살펴보자. 특정 날짜의 상담을 진행하면, 해당 날짜의 상담을 진행하는데 소요되는 기간에는 다른 상담은 진행할 수 없다. 그리고 주어진 기간동안 최대한 상담 수익이 많이 나도록 상담을 진행하고, 최대 수익을 도출하는 문제이다. 1. 큰 문제를 작은 문제로 나눌 수 있다.(최적 부분 구조) 이 문제는, 특정 기간의 최대 수익을 도출하는 문제이지만, 특정 상담을 진행 할지, 말지를 구하는 문제로 작게 나눌 수 있다. 따라서, 이 문제는 최적 부분 구조를 만족한다. 2. 작은 문제에서 구한 정답은 그것을 포함하..
[백준] 1300번 K번째 수(feat. 이분 탐색 Lower-Bound)
[백준] 1300번 K번째 수(feat. 이분 탐색 Lower-Bound)
2022.05.10https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 접근 이 문제에서 주어진 N의 범위는 10^5, K의 범위는 min(10^9, N^2) 이기 때문에, 이분 탐색을 이용해야 할 것으로 예상된다. 이 문제를 간단하게 요약하면, A[i][j] = i*j 이고, 크기는 N*N 2차원 행렬을 1차원 배열 B로 만들 때, B[K]의 값은 무엇인지 구하는 문제이다. (단 인덱스는 1부터 시작한다. 라고 문제에 제시되어있음..
[백준] 2110번 공유기 설치 (feat.Binary Search)이분 탐색
[백준] 2110번 공유기 설치 (feat.Binary Search)이분 탐색
2022.05.05https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 문제에서 주어진 x의 좌표 범위를 봤을 때, 이분탐색으로 문제풀이를 접근해야 한다고 생각한다. 그렇다면 어떤 것을 이분탐색 해야할까? 문제의 핵심은, 공유기 사이의 좌표 간 거리중에 C개의 공유기를 설치할 수 있는 최대거리를 구하는 것이다. 즉, 공유기 사이의 거리로 가능한 최소와 최대를 정하여 해당 범위를 이분탐색 해야한다. 특정 거리를 ..