백준 문제 풀이 (152) 썸네일형 리스트형 백준 5911번 - 선물 (C++) https://www.acmicpc.net/problem/5911 이 문제는 N이 1000이고 딱 하나의 물건만 할인할 수 있기 때문에 브루트포스 방식으로 모든 선물을 할인해볼 수 있다. 그래서 N * N으로 해결할 수 있다. 먼저 모든 선물을 하나씩 할인해보고 그 이후 비용이 덜 드는 순서대로 정렬하고 가능할 때 까지 선물을 보내보면 된다. 그리고 만약 여기서 할인할 수 있는 선물이 여러개가 된다면 https://www.acmicpc.net/problem/25947 이 문제가 된다. 할인할 수 있는 선물이 한개가 아니기 때문에 N * N 으로풀 수 없는 여러개의 조합이 되어버려 브루트포스는 사용할 수 없고 이 문제에선 먼저 정렬을 통해 오름차로 만들고 이후 막혔을 때 할인을 계속 해보면서 정답을 찾아간.. 백준 13904번 - 과제 (C++ / Greedy 알고리즘) https://www.acmicpc.net/problem/13904 문제를 접했을 때, 남은 일수를 먼저 할 것인가, 가장 많이 점수를 주는 과제를 수행할 것인지 잘 생각해야하는 문제이다. 가장 많은 점수를 주는 과제는 반드시 처리되어야 하지만, 최대한 나중에 밀어두고 처리해야한다. 왜냐하면 10 10005 1001 999 이라하자, 그렇다면 가장 많이 주는 과제는 10일이나 남았지만 먼저 처리해버리면 999를 주는 과제를 처리할 수 없다. 그러므로 TASK[DAYS] = DAY 일에 처리할 과제의 점수 가 들어있도록 하는 구현 방법을 사용해야한다. 이것을 떠올리기가 쉽지 않아 난이도가 있다. 보통 그리디 문제라하면 어떤 answer를 갱신하는 식으로 처리하기 때문이다. 그래서 그리디와 자주 함꼐하는.. 백준 1990번 - 소수인팰린드롬 ( C++ / 에라토스테네스의 체) https://www.acmicpc.net/problem/1990 에라토스테네스의 체를 사용하면 간편하게 풀리는 문제...... 라고생각했으나 계속 시간초과가 나서 당황했다. 에라토스테네스의 체를 사용하는 방법은 두가지가 있다. 1. 범위 내의 소수 모두 찾아내기 int main(){bool check[10000]; for(int i = 2; i * i 2. 소수 판정하기bool Eratos(int N){ if(N 소수 판정 또한 O(sqrt(N)) 으로 판단해낼 수 있다. 그렇다면 이 문제는 b가 1억까지 있기 때문에 결국 1억 * 소수 판정이 들어가서 무조건 시간초과인데 어떻게 해야할까 생각이 들었는데, 소수인 팰린드롬은 천만 이후 나오지 않는다고 한다..!!! 그래서 천만까지만 보면.. 백준 1106 호텔 (C++) https://www.acmicpc.net/problem/1106Cost, Value가 정해져 있는 다이나믹 프로그래밍 배낭문제이다.다만 이 문제는 평범한 배낭문제와 달리 중복을 허용한다. 그래서 이 문제는 일반적인 배낭 문제의 변형이다. 일반적인 식은 다음과 같다.for(int i = 1; i = cost){ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost] + value); } else{ dp[i][j] = dp[i - 1][j]; } } } i번의 행을 만들 때는 i - 1번 행을 보고 표를 갱신하게 된다. 그래서 i - 1행에는 당연히 이번 아이템이 .. 백준 1644번 - 소수의 연속합 (C++, 에라토스테네스의 체, 누적합, 투포인터) https://www.acmicpc.net/problem/1644 아주 어려운 문제는 아니나, 에라토스테네스의 체, 누적합, 투포인터라는 삼박자를 알고 있어야 풀 수 있는 문제였다. 에라토스테네스의 체 문제를 연속으로 풀다보니 대체 고대 그리스의 철학자들은 얼마나 천재인건가 가늠도 안된다. 아무튼 문제는 다음과 같은 단계로 이루어진다. 1. 에라토스테네스의 체를 사용해 소수 판별2. 누적합을 통해 각 소수의 범위 prefix 배열 처리3. 투포인터를 활용해 연속합중 N과 같은 것들 처리 https://tigerfrom2.tistory.com/433 알고리즘 - 에라토스테네스의 체(C++)최근 코딩테스트에서 소수를 판별해야하는 문제가 나왔다. 그래서 에라토스테네스의 체를 사용해야함을 바로 알았지만 아쉽.. 백준 16472번 - 고냥이(C++) https://www.acmicpc.net/problem/16472 투포인터 문제로 전형적인 정도까지는 아니지만 좋은 문제다. 두 좌표 사이의 대한 정보를 파악하는 것이 마치 누적합과도 비슷하다. #include #include using namespace std;map lettter;int main(){ int N; cin >> N; string cats; cin >> cats; int lo = 0; int hi = 1; int cnt = 1; for(char c = 'a'; c N){ lettter[cats[lo]]--; if(lettter[cats[lo]] == 0){ cnt--.. 백준 7662번 - 이중 우선순위 큐 (C++) https://www.acmicpc.net/problem/7662 이름 처럼 우선순위큐를 반드시 두개 사용해야 풀 수 있다. 1 2 3 4 가 값으로 들어온다면, 하나의 큐는 1 2 3 4 순으로다른 하나의 큐는 4 3 2 1 순으로 우선순위가 구성되어야 한다. 즉, 최대힙과 최소힙이 필요하다. 아이디어 1.언제나 최대힙의 top > 최소힙의 top 이면 되지 않을까 즉, 만약 최대힙에서 pop을 3번, 최소힙에서 pop을 1번 하게 되면 최대힙의 top은 1이고 최소, 힙의 top은 2이다. 위의 원칙을 어겼다. 이 뜻은 이미 최소힙의 top은 최대힙에서 pop되었다는 의미이기 때문이다. 하지만 이 방법은 20퍼센트에서 틀렸습니다를 받았다. 만약 모든 수가 다르다는 조건이 있었다면 맞았을 지 모르겠으나.. 백준 1474번 - 밑 줄(java, 그리디, 구현) https://www.acmicpc.net/problem/1474 무슨말인지 잘 모르겠는 문제인데 해석만하면 그렇게 어려운 문제는 아니다. 그러나 문자열을 다루는데 익숙하지 않다면 조금 어려울 수도 있다. 사전순으로 앞에 온다는 의미를 잘 해석해야하는데 나도 이것을 잘 못해서 이게 왜 실버1이지 싶었다. 사전순이란 AABBBAAABB -> AAABB 가 먼저온다. 즉, 밑줄 보다 우선순위가 높은 대문자 앞에는 밑줄이 되도록 오지 않는 것이 좋다. AAA_BBaaAA_ABBaa -> AAA_BBaa 가 먼저온다. AAA_BBaaAAABBa_a -> AAABBa_a 가 먼저온다 이제 느낌이 올것이다. 문자열을 탐색하며 먼저 소문자 앞에 밑줄들을 추가하고 만약 더 이상 소문자가 없다면 뒤쪽에 있는 대문.. 이전 1 2 3 4 5 6 ··· 19 다음
