알고리즘 공부방

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 알고리즘 분류: Math, 유클리드 호제법 문제 풀이 먼저 입력 값과 시간을 보면 일일이 다 확인하는 브루트포스로는 풀 수 없다는 것을 알 수 있다. n이 100이고, 최대로 입력되는 값이 10억이므로 브루트포스로는 풀 수 없음을 알 수 있다. 그러면 이 문제는 수학적으로 접근을 해야한다는 것인데, 이 문제를 수식으로 써보면, 먼저 모든 수의 나머지가 같은 경우를 간단히 생각해보면 모든 수가 나누어 떨어지면 된다..

https://www.acmicpc.net/contest/view/927 보드게임컵 www.acmicpc.net 이번 대회에서 5솔을 했다. 1시간 뒤에 들어간 것과, D번에서 진짜 바보같은 실수를 한 것 때문에 잘 못 했다. A - 노 땡스! 단순 구현 문제 AC - 1:02 소스 코드 B - 할리갈리 map 자료구조를 사용하면 쉽게 풀림 (map을 쓰지 않고, 입력받은 문자열의 앞글자 만으로도 풀림) AC - 1:04 소스 코드 C - 크레이지 타임 이 문제 또한 단순 구현 문제이다 AC - 1:18 소스 코드 D - Yacht Dice 이 문제가 이번 대회의 문제점이었다. 문제 자체는 그냥 단순 구현 문제였다. 하지만 바보같이 i와 j를 바꿔쓴 탓에 계속 WA를 받고 있엇다. 이것을 발견하기까지 1..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 유형: DFS, DP 문제 풀이 이 문제는 dfs로 돌리면서, 오른쪽 끝점까지 갔던 경로를 dp로 저장하면서 푸는 문제이다. 예를 들어 (3,3)에서 (10,10)으로 가는 경로가 3이라 했었을 때 (1,1)에서 출발하여 (3,3)에 도착하면, (10,10)까지 가지 않아도 경로를 알 수 있게 되는 것이다. 전체 코드 import java.io.*; import java.util.*; public..

백준을 시작한지 223일 만에 플레5 달성했다!

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 유형: 이분탐색, Union-Find 문제 설명 먼저 설명하기전에 c++ 입출력 억까를 당했다.. 문제를 설명하면 먼저 입력에 주어진 배열을 저장한다. 그리고 k개의 자연수가 주어졌을 때, 이분탐색의 응용중 하나인 Upper Bound를 사용하여, k다음으로 큰 수를 배열에서 찾고, 출력해준다. 그리고 출력한 수는 다시 쓸 수 없으므로 똑..

https://www.acmicpc.net/problem/26598 26598번: 색종이와 공예 첫째 줄에 색종이 공예품의 세로 길이 $N$, 가로 길이 $M$이 공백을 두고 주어진다. $(1 \leq N,M \leq 1\,000)$ 다음 $N$개의 줄에 걸쳐 알파벳 대문자로 이루어진 길이가 $M$인 문자열이 주어진다. 상하좌 www.acmicpc.net 문제 유형: 그래프 이론, 에드 훅 문제 풀이 간단한 그래프 탐색 문제이다. 탐색을 시작한 좌표와 같은 문자만 탐색을 하며, 탐색이 끝났을 때, 탐색했던 가장 작은 x좌표와 y좌표, 가장 큰 x좌표와 y좌표를 구하고, 이것을 이용해 사각형의 넓이를 구해, 탐색하며 알파벳을 개수 카운트 한 것과 같은지 판별해주면 되는 문제이다. 전체 코드 import j..

https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 문제 유형: 그리디, 우선순위 큐 문제 풀이 입력이 최대 1000000이기에 O(nlogn)풀이로 풀 수 있다. 그렇기에 우선순위 큐를 써 그리디하게 가장 작은 것 두개를 곱하고 다시 넣고, 큐 사이즈가 1이 될때까지 반복한다. (오버플로우 조심하자..) import java.io.*; import java.util.*; public class Main {..

https://www.acmicpc.net/problem/16456 16456번: 하와와 대학생쨩 하와이로 가는 거시와요~ 첫째 줄에 하와이 열도의 섬의 개수 n(1 ≤ n ≤ 50,000)이 주어지는 거시와요 하와와. 하와와! 답이 커질 수 있으니 1,000,000,009로 나눈 나머지를 출력해 주시는 거시와요! www.acmicpc.net 문제 유형: DP 문제 풀이 이렇게 노가다로 dp[i] = dp[i - 3] + dp[i - 1]의 점화식을 발견해 풀었다. 전체 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws NumberFormatException, IO..