본문 바로가기

백준 문제 풀이

 (148)
백준 1655번 가운데를 말해요 (C++) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 이해는 쉬운데 어떻게 해야할지 감이 안잡히는 문제이다. 게다가 제한시간이 무려 0.1초다. 무조건 O(N)으로 풀어내야한다. 아이디어는 다음과 같다. 1 2 3 4 5 가 있다고 하자 그렇다면 여기서 1,2,3 은 최대힙 4,5는 최소힙으로 구성한다. 그렇다면 언제나 최대힙의 top이 정답이된다. 이것이 가능하려면 여기서 규칙이 생긴다. 1. 최대힙의 개수는 언제나 최소힙과 ..
백준 9084번 동전(C++) https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제를 풀 때 dfs bfs 백트레킹 완전탐색으로 많이 풀다보니 TLE가 많이 발생한다는 느낌이 들었다. 이번 아레나에서도 아마 출력은 다 맞았을탠데 시간초과가 나서 문제를 풀지 못했다. DP라는 것도 알고 있었는데 못풀다니 기분이 너무 안좋았다. 그래서 DP를 열심히 풀어보고 있다. 그런데 DP는 구글링 안하면 풀수가… ㅠㅠㅠ 언젠가 온전히 내 힘으로 풀기를 고대한다. 이 문제는..
백준 6593번 상범 빌딩(C++) https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 기본적인 bfs + 이동 카운트 문제이다. 아마도 q에서 직접 지나온 칸 수를 갖고 있는 방법과 다른 배열을 선언해서 갖고 있는 방식이 될 것 같은데 나는 후자를 선택하였다. 3차원 bfs는 처음이었는데 2차원 bfs와 다를게 없었다. #include #include using namespace std; int L, R, C; char building[31][31][31]; int cnt[31][31]..
백준 1766번 문제집 (C++) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬문제이다. 줄세우기 문제와 유사하지만 중요한 건 이번에는 이왕이면 더 작은 수 부터 해야하기 때문에 bfs 방식만을 사용해서 우선순위큐를 만들어줘야한다. 정답 코드 #include #include #include using namespace std; int N, M; vector graph[32001]; bool check[32001] = { false, }..
백준 2252번 줄세우기 (C++) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬의 예제 문제이다. 예제 1번을 보자. 3 → 2 1 → 3 2 → 3 위상정렬을 적용해보면 1번은 없고 2번은 3번이 3번은 1번과 2번이 먼저 와야한다. 그러므로 진입차수가 0인 1이 들어오고 진입차수가 다음으로 0이되는 2번이 오고 그다음 3번이 온다. 위상정렬의 특성상, 진입차수가 0인 것이 2개이면 dfs bfs 방법에 따라 순서가 바뀔 ..
백준 14391번 종이 조각 (C++) https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 문제를 처음 봤을 때, N과 M이 겨우 5밖에 안되기 때문에 브루트포스를 하면 해결 할 수 있을 것이라는 확신이 들었다. 그러나 모든 가로 세로를 조합하며 종이를 자르는 것이 내 실력으로 할 수 없었다. 이것도 연습을 해야할 것 같다. 예제들은 모두 N자리 혹은 M 자리로만 해결하면 되는 예제만 줘서 마치 애드혹으로 보일 수 있는데 당연하지만 조합을 해야 풀 수 있는 문제이다. 계속 풀지 못하다..
백준 1043번 - 거짓말(C++) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 처음 봤을 땐 브루트포스로 전부 확인하는 형식으로 풀었는데 3%에서 틀렸습니다가 발생했다. 그래프 문제라고는 상상을 못했다. 정확히는 유니온 파인드 문제였다. 유니온 파인드 알고리즘은 정확히 공부한 적이 없는데 이번에 공부할 수 있었다. 1. 먼저 각 진실을 알고 있는 자들의 유니온(집합) 번호를 0번으로 지정한다. 2. 파티를 열고 파티를 들어온 1번 사람들과 이후 사람들을 합쳐준다. 3. 이후 각 파티를..
백준 1253번 좋다(C++) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 처음 봤을 때는 N이 그렇게까지 크진 않아서 그리디하게 풀이 가능하지 않을까 했는데 "두 개" 의 숫자로 나타낼 수 있음이 핵심이다. 투포인터로 풀어야하는 문제이다. 1. 먼저 숫자를 정렬한다. 2. lo = 0 hi = n - 1로 설정하고 찾는 수 보다 크면 hi-- 작으면 lo++ 하며 범위를 좁힌다. 3. 예외 케이스는 0 0 1이다. 0 0 1 의 경우 그냥 투포인터로 잡아놓으면 3을 내놓는다. 0은 0, 1로 나타..

티스토리툴바