본문 바로가기

📊알고리즘/BOJ101

[그리디 #5] BOJ 14916 - 거스름돈 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 접근 방법 간단한 그리디 문제이다. 5원과 2원 뿐이기 때문에 5원을 빼야하는 경우와 2원을 빼야하는 경우를 잘 생각해보자. 5원이 빠질 경우는 5원을 뺐을때, 나머지가 5으로 나누어떨어지거나 2로 나누어떨어지만 5원으로 결정. 2원이 빠질 경우는 2원을 뺐을때, 나머지가 2로 나누어 떨어지면 2원으로 결정. 코드 #include #include #include using namespace std; int n; int rest; int cnt; int main() { ios::sync_with_stdio(false).. 2024. 2. 9.
[그리디 #4] BOJ 1744 - 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1차 시도 큰 수끼리 곱하면 된다고 막연하게 생각했다. 근데 예제를 보면 예외가 몇 개 포함되어 있다. 1. 1일 때는 곱하면 안된다. 2. 0일 때는 음수랑만 곱한다. 그런데 반례를 찾을 수 있었다. 5 -3 -2 -1 1 2 답: 8 출처: 맨 아래 블로그 큰 음수끼리 곱해야 가장 커진다는 점을 간과했다. 접근방법 그래서 전체적인 프로세스를 구상했다. 준비 1. 양수, 0, 음수를 각각의 v.. 2024. 2. 7.
BOJ 2170 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 1차 시도 "중복되는 곳을 어떻게 저장했다가 사용할 것인가" 가 이 문제의 핵심이라고 생각했다. 그래서 배열을 만들어 할당된 곳을 체크하면서 길이를 측정하려고 하였다. 근데 문제는 크기였다. 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000) 라는 조건 때문에 배열 선언이 불가능해서 불가능하다고 판단 2차 시도 배열로 체크하는게 .. 2024. 2. 5.
[그리디 #3] 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 접근 방법 예제를 보면 쉽게 해결할 수 있는 문제이다. 최종적으로 모든 카드의 합이 최소가 되어야 한다. 최소가 되기 위해선 당연하게 가장 작은 카드 2개를 선택하면 된다. 매우 간단하게 해결할 수 있는 그리디 문제이다. #include #include #include using namespace std; vector v; int n, m; int main().. 2024. 2. 5.
[그리디 #2] BOJ1541 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 첫번째 시도 덧셈을 먼저 진행 후, 나중에 뺄셈을 진행해야 한다고 생각해서 operands, operations Vector를 두 개 만들어 덧셈->뺄셈 순서로 진행하는 방법을 생각했지만 매우 비효율적인 방법으로 생각되어 다른 방법을 생각함 두번째 시도 뺄셈이 나오면 뒷부분의 +는 -로 바꾸어 계산하는 방법을 생각함. 그런데 -의 경우, 부호를 바꾸면 +가 되기 때문에 이를 고려해야 한다고 .. 2023. 11. 12.
[그리디 #1] BOJ 11501 주식 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 그리디를 오늘부터 제대로 시작해보려고 한다. 먼저 이 문제를 고르게되었다. 그리디 알고리즘이 '현재에서 가장 Best인 항목을 선택' 하기에 이번에도 이를 적용하려고 하였다. 첫번째 시도 고수익을 얻기 위해선 무조건 최고점일 때 판매를 해야한다. 최고점을 구하는 함수를 만들어 이를 사용하였다. 테스트 케이스 중 1 1 3 1 2 의 경우, MAX가 3이기 때문에 고점을 고정하여 진행하.. 2023. 11. 10.

티스토리툴바