본문 바로가기

GOLD23

[백준/C++] #2293 동전1 (DP) 문제https://www.acmicpc.net/problem/2293구상나는 보통 문제를 보고 '어떻게 접근해야 할지 모르겠다...! 혹은 재귀인가..?'라는 생각이 들면 dp로 접근해본다. 이 문제도 그러했다. 오랫만에 dp를 풀어서 그런지 좀 머리를 싸맸는데, 동전의 구성이 같은데, 순서만 다른 것은 같은 경우라는 조건을 보고 동전의 가치를 큰 기준으로 잡고 가야겠다는 생각이 들었다. 글로 쓰기가 어려워서 그림으로 대체한다.  알고리즘이전에 구한 값을 이용하여 다음 값을 구하기에 dp(dynamic programming)를 이용했다. 풀이 + 코드#include #include #include #define endl "\n"using namespace std;int N, K;vector coins;v.. 2024. 7. 22.
[백준/C++] #20366 같이 눈사람 만들래? (Two Pointer) 문제https://www.acmicpc.net/problem/20366구상N개의 눈덩이를 가지고, 4개의 눈덩이를 골라, 2개의 눈사람을 만드는데, 두 눈사람의 높이의 차가 최소가 되도록 하여 최소인 높이 차를 출력하는 문제였다. 지금보면 진짜 바보같지만, 처음에는 진짜 내가 이걸 1초만에 생각해낸게 신기할 정도로 쉬워보이는 풀이 (결과적으로 틀린 풀이) 를 생각해냈다.  무엇이었냐 하면, 눈사람의 지름이 a, b, c, d라 하면, (a+b) - (c+d)의 값이 가장 작으면 되니까, (a-c)-(d-b)의 최소값을 구하면 되겠다 생각해서 눈사람의 지름 오름차순으로 정렬하고, 인접한 배열의 값끼리의 차를 구한 배열을 만들어서, 그걸 또 정렬해서(인덱스 값과 함께 pair로. 인접한것 고르면 안되니까),.. 2024. 7. 22.
[백준/C++] #16472 고냥이 (Two Pointer) 사실 어렵거나 함정이 있는 문제는 아니었는데... 그냥 문제 이름이 너무 귀여워서 포스팅한닷문제https://www.acmicpc.net/problem/16472구상최대 N개의 종류의 알파벳을 가진 연속된 문자열의 최대 길이를 구하는 문제였다. "연속된" 문자열의 길이라고 하니까 투 포인터로 접근할 수 있겠다 싶었다. 문자열의 인덱스값을 가리키는 lett와 right를 0부터 쭉쭉 나아가면서 left~right까지 사용하는 알파벳을 확인하면서 값 갱신하면 될듯했다.  알고리즘두개의 포인터를 이용하여 문제를 푸니까 Two pointer!! 풀이 + 코드1. 사용하는 알파벳이 N개 미만이거나 N개라면, 값 비교후 갱신하고, right ++, 개수 확인2. 사용하는 알파벳이 N개 초과라면, left++, 개수.. 2024. 7. 22.
[백준/C++] #11000 강의실 배정 (Greedy) 문제https://www.acmicpc.net/problem/11000  구상가장 처음에 왼쪽 그림처럼 2차원 배열을 만들어서 1번 강의실부터 시간들 채워나가며 몇번 강의실까지 사용하는지 알고자 했는데, S와 T의 범위가 10^9로 굉장히 커서 시간 복잡도에서 문제가 생겼다.  그래서 오른쪽 그림과 같은 구상을 했는데, 먼저, 주어진 S와 T를 배열에 넣고, S(시작 시간)기준으로 정렬한다. 그리고, 끝시간은 최소힙에 하나씩 넣고 시작시간과 비교해 시작시간이 최소힙에 있는 끝시간보다 같거나 크면 힙의 top값을 pop하고, 현재 강의 시간의 끝 시간을 최소힙에 넣는다. 남아있는 강의들 중에서 시작 시간이 가장 빠른 강의가 이미 배정된 강의 중에서 가장 끝시간이 빠른 강의 뒤에 올 수 있는지 판단하는 것이.. 2024. 7. 15.

티스토리툴바