백준 문제 풀이 (152) 썸네일형 리스트형 [백준] 13164번 행복유치원 (C++) https://www.acmicpc.net/problem/13164 N이 30만이기 때문에 모든 경우를 확인할 수 없는 문제이다. 이런 각 숫자들의 차이에 따라 갈리는 문제들은 각 숫자들의 차이를 위주로 생각해야한다. 5 31 3 5 6 10 예제 문제를 예로 들어보자. 1 3 | 5 6 | 10 이렇게 막대를 새우면(그루핑하면) 정답이다. 이걸 어떻게 찾을 수 있을까? 이번엔 각 숫자들이 이웃한 숫자와 차이를 적어보자 2 2 1 4 이 숫자는 곧 각 사이에 막대를 두었을 때 없앨 수 있는 비용과 같다. 즉 여기서는 3개로 나눌 수 있으므로 막대는 2개 새울 수 있으므로, 4와 2 위치에 막대를 두면 정답을 찾을 수 있다. 1 | 3 5 6 | 10 이렇게 해도 정답은 3이므로 같은 값이면 막대를 어디에.. [백준] 7573번 고기잡이 (C++) https://www.acmicpc.net/problem/7573 슬라이딩 윈도우같은 문제인데 사실은 브루트포스이다. 초등수준 도형 지식을 요구한다. 고기를 기점으로 왼쪽 사이드에 고기가 있다고 가정하고 브루트포스하면 되는 문제다. 단, 그물이 모든 바다를 덮을 수 있는 경우를 예외처리해야한다. 난 1만 * 1만 배열은 만들어 고기를 관리했는데 이렇게하면 메모리를 많이쓴다. 다른 사람들은 이렇게 안한것같다. 하지만 메인 로직은 같기 때문에 따로 참고하진 않았다. #include#include#define MAX 10001using namespace std;int N, I, M;bool sea[MAX][MAX];vector> fishs(101);int fishing(int n, int m, int x, .. [백준] 1461번 도서관 (C++) https://www.acmicpc.net/problem/1461 문제세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.입력첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다.. [백준] 과일 탕후루 (C++) https://www.acmicpc.net/problem/30804 양 끝에서 숫자를 빼가며 Greedy 한 방법으로는 문제를 풀 수 없다. 그리고 N = 20만이기 때문에 양옆에서 빼는 모든 방법을 해보는 것은 불가능하다. 그러므로 두포인터를 활용해 범위를 계속 갱신해가며 풀어야하는 문제이다. 기본 예제로 시뮬레이션해보자. Lo는 첫번째 원소를, hi는 두번째 원소를 가리키고 있다. 이 때 탕후루의 종류는 5, 1 로 총 2개이고 길이는 2이다. 이제 hi를 1 늘려서 보자. 아직 종류가 2개이다. 범위를 더 늘렸더니 종류가 3개가 되었다. 그러므로 이제 범위를 줄여야한다. lo를 하나 늘리자 이제 정상화 되었으므로 hi를 하나 늘린다. hi가 끝까지 왔으므로 더이상 탐색하지 않아도된다. l.. [백준] 1202번 보석 도둑 (C++) https://www.acmicpc.net/problem/1202 자료구조를 너무 그냥 처음부터 넣어놓고 꺼내면서 확인하는 식으로만 사용하려는 경향이 있는 것 같다. 고쳐야돼!! 유연한 사고! 먼저 이 문제도 O(N^2)을 최적화하는 문제이다. 그래서 처음에 생각했던 풀이는 이분탐색 lower bound이다. 단순히 이분탐색만 진행했다면 O(N long N)으로 가능하지만 안타깝게도 erase연산이 들어가야하기 때문에 O(N*K)와 다름없어지기 때문에 맞는 풀이가 아니다. 그래서 이 문제는 그리디 + 우선순위큐가 된다. 우선 가방의 크기대로 정렬하고 가방의 크기에 맞으면 전부 우선순위큐에 넣고 이제 더이상 못 넣으면 최댓값을 top으로 가져오면 된다. 이 생각만 해내면 쉬운데 생각하는게 힘들었다. 아무래.. [백준 22234번] 가희와 은행 (C++) https://www.acmicpc.net/problem/22234 큐를 사용하여 시뮬레이션 하는 문제가 이전에 코딩테스트에 출제되어서 이번에 도장깨기를 하고자 풀어보았다. 큐 문제를 풀 때는 가장 중요한 것이 보통 시뮬레이션이 동반되기 때문에 문제를 정확히 파악하는 것이 중요하다.그리고 그림으로 그려가면서 어떤 지점에서 큐를 사용할지 가상으로 시뮬레이션해보는 것이 매우 중요한 것 같다. 이 문제를 시뮬레이션 해보면 위 시뮬레이션을 보자. 1, 2에서 새로운 아이디가 들어왔는데 1이 아직 안 끝났으므로 맨 뒤로 들어간 모습이다. 이것을 의사코드로 생각해보면 if 현재 고객의 상담이 끝나면: 이후 온 사람들이 있는지 검사하고 이전에 온 사람들이 있으면 큐에 삽입 그렇다면 이제 온 사람들을 관리할 큐가 하.. [백준] 1, 2, 3 더하기 4 (C++) https://www.acmicpc.net/problem/15989 DP는 언제나 너무 어렵다... 내가 바보인것도 있지만 DP 배열을 1차원으로 둘지 2차원으로 둘지 파악하는 것도 매우 까다롭다. 요즘 코딩테스트에서는 DP가 많이나오진 않는 것 같은데 그래도 연습이 필요하다. 이 문제는 1, 2, 3으로 N을 만들 수 있는지 물어보는 전형적인 DP문제이다. 당연히 1차원 배열로 풀어보려 했는데 잘 안되서 구글링을 통해 찾아봤다. 상상치도 못한 2차원 배열이 나왔다. dp[i][1] = 1로 만들 수 있는 경우의 수dp[i][2] = 2를 포함하여 만들 수 있는 경우의 수dp[i][3] = 3을 포함하여 만들 수 있는 경우의 수 이렇게 모아놓는 방식이었다. 이렇게 하는 이유는 1 + 1 + 2, 1 +.. [백준] 9017번 크로스 컨트리(C++) https://www.acmicpc.net/problem/9017 처음 봤을 땐 되게 쉬운 문제라고 생각했는데 틀렸습니다가 떠서 질문 게시판을 보니 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 이것을 대강 넘어가서 그런 것이었다..!! 그리고 점수가 낮을 수록 순위가 높은 것이었다..!! 문제를 잘 읽고 분석을 철저히 하자. #include#include#includeusing namespace std;int main(){ int T; cin >> T; for(int t = 0; t > N; vector race; map maps; for(int i = 0; i > n; maps[n].. 이전 1 2 3 4 ··· 19 다음
