silver38 [C++] 백준 1072번: 게임 (이분 탐색) https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 문제 이해하기 이 문제를 요약해보면 다음과 같습니다. 승률을 올리기 위해 최소 몇 게임을 더 이겨야 하는지 구하여라. 시간복잡도 어림하기 브루트 포스 알고리즘 X의 범위가 1,000,000,000으로 최대 10억까지므로 탐색 횟수도 이에 비례하여 아주 커질 것입니다. 따라서 브루트 포스 알고리즘은 적절하지 않습니다. DP 알고리즘 역시 X의 범위가 최대 10억까지이므로 필요한 값의 양이 너.. 2024. 3. 27. [C++] 백준 3273번: 두 수의 합 (투 포인터) 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 이해하기 문제의 요구사항은 다음과 같습니다. n개의 서로 다른 자연수 수열에서 두 수의 합이 x인 쌍의 수를 구하여라. 시간복잡도 어림하기 브루트 포스 알고리즘 모든 경우의 수를 계산하는 브루트 포스 알고리즘을 생각해봅시다. 모든 가능한 순서쌍의 개수는 n개의 원소 중 2개를 뽑는 경우의 수와 같으므로 nC2로 계산할 수 있습니다. 또는, 첫 번째 원소로 구할 수 있는 순서쌍의 개수는 n - 1개, 두.. 2024. 3. 26. [C++] 백준 13305번: 주유소 (DP, 그리디) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 이해하기 문제의 요구사항은 다음과 같습니다. 가장 왼쪽 도시에서 가장 오른쪽 도시까지 이동하는데 필요한 최소 금액을 구하여라. 각 도시는 1리터당 가격을 담고 있으며, 도시를 연결하는 간선에는 두 도시 사이의 거리가 담겨있습니다. 이를 인지하고 문제를 해결해봅시다. 시간복잡도 어림하기 브루트 포스 알고리즘 현재 도시에서 다음 도시로 넘어갈 때 가능한 기름의 양은 몇 가지 일까요? 당연히 최솟값은 다음 도시까지의 거리와 같고, 최댓값은 가장 오른.. 2024. 3. 25. [C++] 백준 14501번: 퇴사 (브루트 포스) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 이해하기 문제가 복잡해보이지만, 결론만 보면 주어진 기간 내에 얻을 수 있는 최대 이익을 구하여라. 라고 할 수 있습니다. 여기서 이익은 정해진 상담 시간이 끝나면 얻을 수 있고, 상담 중 다른 상담은 받을 수 없다는 제약이 있습니다. 이 제약을 인지한 채로 다음 단계로 넘어가겠습니다. 시간복잡도 어림하기 브루트 포스 알고리즘 여러 경우의 수 중 최댓값을 찾는 문제이므로 모든 경우의 수를 탐색하는 브루트 포스 알고리즘을 먼저 고려해보겠습니다. 상담을 진행하는 모든 경우의 수는 어떻게 구할 수 있을까요? 우선, 한 상담에 대해 상담을 하거나 상담을 하지 않는 상태를 가질 수 있으므로, 하나의 상담.. 2024. 3. 24. [C++] 백준 11659번: 구간 합 구하기4 (누적 합) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 이해하기 이번 문제는 아주 간결합니다. i번째 수부터 j번째 수까지의 합을 구하여라. 시간복잡도 어림하기 배열에서 i번째 수부터 j번째 수까지의 합을 어떻게 구할 수 있을까요? 그렇습니다. 바로 i번째부터 j번째까지 배열을 탐색하면서 합을 구하면 됩니다. 그럼 이 알고리즘의 시간복잡도는 어느 정도일까요? 한번 구해봅시다. 일단 i번째부터 j번째까지 연속적으로 탐색하는 횟수는 j - i + 1번 입니다. 이 문제의 조건을 보면, 배열에 .. 2024. 3. 23. [C++] 백준 1966번: 프린터 큐 (구현) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 이해하기 이 문제를 요약해보면 다음과 같습니다. 정해진 규칙에 따라 인쇄하는 인쇄기에서 특정 문서가 몇 번째로 인쇄되는지 구하여라. 여기서 정해진 규칙이란 1. 입력은 queue 자료구조에 따른다. 2. 출력은 기본적으로 queue 자료구조에 따라 가장 앞에 있는 문서를 내보낸다. 2-1. 만약 가장 앞에 있는 문서보다 중요도가 높은 문서가 queue 내에 존재한다면, 가장 앞의 문서를 가장 마지막으로 옮긴다. 라고 할 수 있습니다. 시간복잡도 어림하기 이 문.. 2024. 3. 22. 이전 1 2 다음
