알고리즘

    알고리즘

    [BOJ / 그리디] 1202 보석 도둑

    https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 1202 보석 도둑 알고리즘 : 정렬/그리디/우선순위큐 기본적인 틀은 냅색 문제로 보이지만 가방이 여러개인 점과 한 가방안에 보석 하나만 넣을 수 있다는 점에서 차이가 있습니다. 간단히 생각해보면 우선순위큐에 모든 보석을 넣어 가장 좋은 것을 고르려 할 수 있지만, 그러면 간단한 케이스에서도 정해가 나오지 않습니다. 가방과 보석을 크기순..

    알고리즘

    [BOJ / 비트마스크 DP] 1102 발전소

    www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1102 발전소 알고리즘 : 비트마스크 DP / BFS 비트마스크를 DP배열의 iterator로 사용하는 문제입니다. dp를 이용해 현재 적용중인 상태에서 이미 들린 상태이거나 이미 결과값을 초과한 경우 가지치기를 하면 됩니다. 문제에서 해결이 안되는 경우에는 -1을 출력하라고 했으나, 모든 발전소는 다른 모든 발전소를 킬 수 있으므로 즉, 키는 비용에 음수값이 주어지는 경우가 없으므로 -1을 출력하는 경우는 모든 발전소가..

    알고리즘

    [BOJ / DP] 15990 1,2,3 더하기 5

    www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 15990 1,2,3 더하기 5 알고리즘 : DP 1차원 배열 DP로 시도하다가 점화식에 문제가 있다는 걸 발견하고 3차원 배열 DP로 바꾸었습니다. 같은 수를 두번 이상 연속해서 사용하면 안되므로 1차원 배열 DP에서 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 에서 dp[i-1]에서 +1로 끝나는 dp[i-2]를 빼고 dp[i-2]에서 dp[i-4]를 빼고 dp[i-3]에서 dp[i-6]을 빼려다 빼는 부분에서도 다시 빼야하는 경우가 있어..

    알고리즘

    [BOJ / 위상정렬] 1516 게임개발

    www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1516 게임개발 알고리즘 : 위상정렬, 우선순위큐 전체적으로 풀면서 다익스트라 느낌이 드는 문제였습니다. 다익스트라와 위성정렬 문제를 풀어본 적이 있다면 쉽게 풀이할 수 있습니다. 위상정렬로 inDegree가 0인 아이들만 우선순위 큐에서 관리하면 됩니다. #include #include #include #include #include #include #include #include..

    [2020 CPC] 2020 중앙대학교 프로그래밍 경진대회 풀이
    알고리즘

    [2020 CPC] 2020 중앙대학교 프로그래밍 경진대회 풀이

    2020 CPC 중앙대학교 프로그래밍 경진대회 풀이입니다. 웹 공부를 하느라 잠시 쉬고있던 알고리즘을 다시 시작했습니다. 곧 다가오는 2020 인하대학교 IUPC를 대비입니다. 시간내어 푸느라 아직 모든 문제를 풀이하진 못했습니다. 미풀이 문제는 푸는 대로 업데이트 하도록 하겠습니다. A. #20205 교수님 그림이 깨지는데요? www.acmicpc.net/problem/20205 20205번: 교수님 그림이 깨지는데요? N x K 줄에 걸쳐, 늘어난 단색 비트맵 이미지의 픽셀 정보를 출력한다. www.acmicpc.net 알고리즘 : 단순구현 풀이랄 것이 없습니다. 기본적인 제공문제 출력형식에 띄어쓰기 안 넣어서 실수로 틀린..ㅎㅎ #include using namespace std; ..

    알고리즘

    [BOJ / 라인스위핑] 9318 위성사진

    https://www.acmicpc.net/problem/9318 9318번: 위성 사진 문제 상근이는 위성 사진 여러장을 이용해서 지도를 만들고 있다. 위성에는 카메라가 달려있고, 카메라는 한 영역을 찍는다. 이러한 위성 사진 여러 장을 합치면, 큰 사진을 만들 수 있다. 위성 � www.acmicpc.net 9318 위성사진 알고리즘 : 세그먼트/인덱스 트리 + 라인스위핑 요즘 풀이하고 있는 라인스위핑 기초 문제입니다. 인덱스 트리 짜는 법이 헷갈려서 세그먼트 트리와 섞어서 짰습니다. 라인스위핑을 이용하여 수평선을 기점으로 구간트리를 구성하고 업데이트하여 넓이를 알아내는 방식입니다. CHECK POINT 총 나올 수 있는 구간의 수는 MAX_N * 2개(모든 사각형의 변의 높이가 같지 않을 때)이므로..

    알고리즘

    [알고스팟 / 비트마스크 DP] GRADUATION 졸업학기

    https://algospot.com/judge/problem/read/GRADUATION# algospot.com :: GRADUATION 졸업 학기 문제 정보 문제 1학년은 노는 게 남는 거란 선배의 말을 철석같이 믿고, 전공 과목은 다 수강철회하고 교양 과목은 다 F 받는 방탕한 1학년을 보냈던 태우는 이제 와서 자신의 행동을 �� algospot.com 문제 풀이 전 군대에서 처음 올리는 글입니다. VS를 쓰다 구름IDE를 쓰고 디버깅을 안하면서 하다보니코드가 많이 복잡해진 감이 있네요. 양해 부탁드립니다. 꾸준히 글은 작성하지 못하지만 문제는 꾸준히 풀도록 노력하겠습니다. D-546 ㅎㅎ GADUATION 졸업학기 알고리즘 : 비트마스크 DP (with BFS) 비트마스크를 이용한 작은 양의 데..

    알고리즘

    [BOJ / 비트마스크 DFS] 17136 색종이 붙이기

    https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 17136 색종이 붙이기 알고리즘 : 비트마스크 DFS 삼성 A형 기출문제입니다. 문제 풀이 방법은 1767 프로세서 연결하기와 매우 유사합니다. ht..

티스토리툴바