Algorithm

[백준 2295번] 세 수의 합 (C++)

https://www.acmicpc.net/problem/2295 본 게시글은 바킹독님의 [바킹독의 실전 알고리즘] 0x13강 - 이분탐색을 참고하여 작성되었습니다. 세 수의 합 문제는 이분탐색으로 해결할 수 있습니다. 가능한 방법은 3가지가 있습니다. 4중 for문 이용하여 모든 경우의 수를 확인하는 방법, 시간 복잡도는 O(N4) 가능한 세 수의 합을 구하고, 각 합이 집합 U 안에 존재하는지 확인하는 방법, 시간 복잡도는 O(N3logN) sum[i] + a[j] = a[k]를 만족하는 a[k]의 최댓값을 구하는 방법, 시간 복잡도는 O(N2logN) (단, sum은 두 수의 합을 저장한 배열) N이 최대 1,000이기 때문에 O(N2logN) 알고리즘을 이용하여 해결할 수 있습니다. solutio..

[백준 1700번] 멀티탭 스케줄링 (C++)

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 멀티탭 스케줄링 문제는 그리디 알고리즘으로 해결할 수 있습니다. 콘센트에 꼽혀 있는 기기 중, 앞으로 사용하지 않거나, 가장 나중에 사용할 기기를 선택하여 현재 사용할 기기와 교체해주면됩니다. 증명은 어렵지만, 믿음으로 푼 문제입니다. 알고리즘의 기본 틀은 아래와 같습니다. 멀티탭의 구멍 개수가 기기의 총 사용횟수보다 작은 경우 0을 출력한다. 플러그를 뽑지 않아도 꽂을 수 있는 최대한의 개수를 ..

[백준 2170번] 선 긋기 (C++)

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x n; for(int i = 0; i < n; i++) cin ..

[백준 1744번] 수 묶기 (C++)

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수 묶기 문제에서 큰 값과 큰 값을 곱해주면, 합이 최대가 되도록 해줄 수 있습니다. 하지만, 입력으로 0 이하의 숫자들도 주어질 수 있습니다. 따라서 양수와 0 이하의 숫자를 구분할 필요가 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 양수와 음수를 구분하여 각각의 배열에 저장한다. 양수 배열(p)과 음수 배열(m)을 정렬한다. 양수 배열 p[i + 1]이 양수이면, p[i], p[i + ..

[백준 11501번] 주식 (C++)

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 주식 문제에서는 매일 3가지 행동 중 한 행동을 할 수 있습니다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안 한다. 아래와 같은 동작을 생각해볼 수 있습니다. (단, stock[d]는 d일의 주식 가격) stock[d] stock[d+1]이면, 주식을 판다. stock[d] == stock[d+..

[백준 2457번] 공주님의 정원 (C++)

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 공주님의 정원 문제는 회의실 배정과 유사한 문제로, 그리디 알고리즘을 이용하여 해결할 수 있습니다. 현재 피어 있는 꽃이 지기 전에 피고, 그 중 가장 늦게 지는 꽃을 선택하면 꽃을 최소의 개수로 선택할 수 있습니다. ⚠️ 주의할 점 빨리 피는 순으로 꽃을 정렬해야합니다. 현재 피어 있는 꽃이 지기 전에 피는 꽃이 없는 경우 0을 출력해야합니다. 3월 2일 이전에 피는 꽃이 없..

[백준 12865번] 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 평범한 배낭 문제에서 가치가 높은 물건부터 선택하면 최대 가치를 만들 수 있는가? 아닙니다. 아래의 예시를 보면, 무게가 1000인 물건을 먼저 넣으면 가치를 최대로 만들 수 없습니다. 7 1000 1000 10 500 1 100 9 100 8 90 8 80 6 70 4 평범한 배낭 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 ..

[백준 1026번] 보물 (C++)

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net S의 값을 가장 작게 만들기 위해서는 B의 i번째로 큰 값과 A의 i번째로 작은 값을 곱해주면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int a[51], b[51]; bool cmp(int x, int y){return x > y;} int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >..