백준 문제 풀이 (134) 썸네일형 리스트형 백준 6087번 레이저 통신 (C++) https://www.acmicpc.net/problem/6087 6087번: 레이저 통신크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS , 다익스트라 문제이다. 사실 다익스트라의 정확한 정의를 모르겠다. 이 문제는 최단거리이긴 하지만 무조건 최단으로 가면 안되고 조건이 추가되었고 그 조건이 분기점이 된다. 그냥 조건이 있어도 최단거리라는 조건과 배열을 통한 조건이 있다면 다익스트라 라고 하는 것일까 ? 이건 잘 모르겠다. 아무튼, 많은 틀렸습니다와 시간초과 메모리초과 날 수 있는 건 다 났던 문제였다. 왜 정답률이 .. 백준 15591번 MooTube (C++) https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 이제부터 문제를 풀 때 "맞았습니다" 를 보기 위해 집착하기 보다 어떤식으로 사고를 해야할지 생각하면서 풀기로 했다. 1. 문제 조건: 그래프가 주어지고 한 정점이 다른 정점으로 가는 비용 중 가장 적은 간선의 비용을 USADO로 결정한다. 즉, 지나온 간선 중 가장 적은 비용이 유사도이다. 2. 내 접근 먼저 한 정점에서 다른 모든 정점까지의 .. 백준 1941번 - 소문난 칠공주 (C++) https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에는 dfs 백트레킹 완전 탐색으로 풀어내려 했다. 그러나 백트레킹 완전탐색은 ㅗ ㅏ ㅜ ㅓ 같은 모양은 나타낼 수 없다. 이러한 문제를 테트로미노 문제에선 길이가 4밖에 안되었으니 위 4개의 모양만 따로 관리하면 되었으나 이 문제는 길이가 7이기 때문에 따로 관리하는 것이 불가능하다. 풀이 방법은 다음과 같다. 1. 총 25명의 학생 중 7명을 뽑는다 -> 조합으로 0번~24번 중 7개를 뽑는다.. 백준 1516번 게임 개발 (C++) https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상 정렬을 할 수 있으면 50퍼센트는 되는 문제. 건물을 미리 지어야하는데 미리 지은 건물들의 시간을 모두 더해야하는 문제이다. 위 사진은 기본 예제에서 4를 지을 조건에 2까지 추가한 것이다. 4를 짓기 위해서는 1,2,3을 지어야한다. 그렇다면, 2,3을 짓고 4를 지어야하는데 2번의 경우 20, 3번의 경우 14이다. 여기서 그냥 위상정렬대로 전입차수가 0이라고 더하면 24가될수.. 백준 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, }.. 이전 1 ··· 8 9 10 11 12 13 14 ··· 17 다음
