백준

[백준/BOJ 알고리즘] 17845 수강 과목 C++

https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 0-1 Knapsack 문제이다. 링크 에서 0-1 Knapsack에 대해 알아볼 수 있다. (필자가 작성한 글임) bottom-up 방식으로 DP를 구성하면 된다. O(NK)의 시간복잡도를 갖는다. #include #include #define MAX_N 10001 #define MAX_K 1001 using namespace std; ..

[백준/BOJ 알고리즘] 10830 행렬 제곱 C++

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주어진 행렬 A에 대하여 입력 B만큼 제곱한 행렬을 출력하는 문제이다. B는 100,000,000,000 이하의 값을 갖는다. 즉, A를 B번 제곱하는 방식으로는 해결할 수 없다. 분할정복 을 통해 문제를 해결할 수 있다. A의 거듭제곱은 다음과 같이 나타낼 수 있다. 분할정복을 통해 100,000,000,000번 제곱한 값을 찾는다면, 약 36~7번의 연산으로 찾을 수 있다. 최종적으로 시간복잡도는 다음과 같..

[백준/BOJ 알고리즘] 16236 아기상어 C++

> www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 아기 상어가 바다에서 엄마 상어 없이 얼마나 물고기를 잡아먹으며 버틸 수 있는가.. 하는 문제이다. 뚜루뚜두둡. 더 이상 먹을 물고기가 없을 때까지의 시간을 계산하여 출력하면 된다! 문제 조건이 생각보다 까다롭고 이해하기 어려워서 좀 헤맸던 문제이다... 처음엔 좌표와 비용을 갖는 이중pair(?) 자료형을 큐에 넣고 작업했는데, 시간초과가 나서 비용 정보를 갖는 배열을 생성해서 해결했다. 문제의..

[백준/BOJ 알고리즘] 1039 교환 C++

> www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 원래 이 문제를 풀 생각은 없었는데, 한 친구가 못 풀겠다고 같이 풀자고해서 풀게 되었다. 기존 그래프 탐색 문제와는 좀 다른 느낌이어서 나름 재밌게 풀었다. 문제의 핵심 N은 최대 999,999 의 값을 갖는다. 즉 최대 6자리 자연수라는 것. K가 10보다 작으니, 전부 구해도 된다. K번 연산을 한 동안 나온 최대값이 아닌, K번째 연산을 했을 때 나올 수 있는 최대값을 구해야한다. 큐를 이용하여 구현했는데, 큐에 담기게 될 것은, 각 자리의 숫자가 아닌 i (0 k) b..

[백준/BOJ 알고리즘] 2573 빙산 C++

> www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 오랜만에 알고리즘 풀다가 마음대로 안되서 화가 났던 문제이다..... 그래도 맞아서 기분 좋다. 기본적인 그래프 탐색을 통해 해결할 수 있는 문제이다. 난 DFS를 통해 구현했다. 문제의 핵심 빙산 높이가 담긴 배열의 가장자리는 모두 0 이므로, 탐색대상에서 제외해야한다. 각 빙산의 높이가 1년마다 얼만큼 녹을 지 상하좌우의 빙산을 탐색하여 모든 빙산의 녹는 정도를 구한 후에 빙산을 녹여야한다. 빙..

[백준/BOJ 알고리즘] 3190 뱀 C++

> https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 설명이 잘 돼 있어 재밌게 풀었던 문제이다. 좌표를 나타내기 위해 pair를 사용하였다. 뱀이 차지하고 있는 공간(?)의 좌표를 큐에 담도록 한다. 기본적으로 뱀이 이동할 때 머리가 한칸 전진하고, 꼬리가 따라온다. 사과를 먹었다면 머리만 전진한다고 생각하면 이해가 쉽다. 머리가 한칸 전진 : 새로운 좌표를 큐의 front에 PUSH 꼬리가 따라옴 : 큐의 end 값을 POP 사과를 먹을 때 뱀..