공부일기장

https://www.acmicpc.net/problem/25963 25963번: 계단 만들기 (Small) 때는 2013년, 잼민이 지수는 마인크래프트 게임을 열심히 하고 있다. 지수가 하는 마인크래프트에서는 점프는 한 칸밖에 되지 않으며, 신기하게도 두 칸 이상부터 즉사 낙하 데미지가 들어간다! www.acmicpc.net 적당히 재밌어보여서 시도한 문제. 접근 방법 너비 N의 마인크래프트 월드에서, 모든 인접한 칸의 차가 1 이하가 되도록 만드는 문제이다. 그리디하게 접근하고 싶었으나, 잘 떠오르지 않아서 문제 분류를 보니 dp문제였다. dp문제이므로 완전탐색으로 풀 수 있는 방법을 먼저 생각했다. 특정 블럭을 다른 위치로 옮긴다고 생각하지말고, 해당 위치에서 양 옆칸의 높이차를 맞추기 위해 블럭을..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net MST 복습문제 - 삼성 A형 기출문제 접근 방법 최대 10*10의 격자칸에 섬이 존재하고, 섬을 다리로 잇는 최소 비용을 구한다. 문제를 보았을때 접근 방법은 누구나 비슷하게 쉽게 떠올릴 수 있을 것 같고, 구현이 조금 많이 어려웠다. 1. 각 섬에 dfs/bfs로 번호를 붙인다. 2. 각 섬에서 섬으로 이동하는 dist를 구한다. 3. MST를 계산한다. 각 섬에 번호를 ..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net MST 응용 문제 접근 방법 처음에는 가중치를 구하는 방법만 다른 MST 문제인 줄 알고 그냥 풀었다. 그러나 좌표들 사이의 가중치를 구하려면 O(N^2)의 시간과 공간이 필요한데, N이 10만이라서 다시 생각했다. 대충 정렬을 활용해야 한다는 것은 쉽게 떠올렸으나, 어떻게 사용해야 할지 감이 안왔다. 그래서 풀이를 보았다. 이 곳에 설명이 상세하게 되어있다. 아래..

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 최소신장트리, 데이크스트라 알고리즘을 까먹어서 복습하는 문제. 접근 방법 일반적인 최소신장트리를 구하는 문제이다. 나는 kruskal 알고리즘을 통해 구하는 것을 선호한다. 다른 점이라면 정점 대신 좌표로 되어있어 구현이 조금 복잡하고, 헷갈리기 쉽다. 이미 통로가 존재하는 경우에는 두 좌표를 unionParent 해주면 된다. 아마 안해주어도 시간복잡도상 문제가 전혀 ..

https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 비슷한 문제를 푼 기억때문에 날로 먹은 문제 접근 방법 20*20 배열을 뒤집으며 최솟값을 찾는 문제. 완전탐색으로 할 경우 40개의 상태를 가지므로 2^40 = 1조이고, 이는 죽었다 깨어나도 정해가 아니다. 비겁하지만 알고리즘 분류를 보니 비트마스킹이 포함되어 있었다. 나는 비트마스킹 문제중에 불 끄기 문제를 며칠동안 붙잡다가 풀이를 보았을때의 생생한 충격이 아직 남아있었다. 구현이나 복잡..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 배낭문제를 dp로 풀 때의 응용 버전 접근 방법 추의 무게들이 주어지면, 조합하여 만들 수 있는 무게인지 확인하는 것이 기본적인 배낭문제이다. 이 문제는 구슬의 무게를 확인하기 위해 추를 양 쪽에 올릴 수 있다. 추를 올리거나, 올리지 않거나, 반대쪽에 올리는 3가지의 경우를 나누어서 풀면 된다. dp[idx][sum] = 무게의 합이 sum이고 idx번째 추를 올릴때, 가능한 무게를 조합하기 내 ..

https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 오늘 공부안하고 잠만 늘어지게 잤으니 마지막 양심을 위해 붙잡은 백준 한문제. 만만해 보이는 dp를 골랐으나..OTL 접근 방법 한 10분정도 고민하다 떠올렸다. 최대 10개의 층 밖에 없으므로 각 층마다 색의 개수만 정해주면, 가짓수는 조합으로 구할 수 있다. dp[floor][r][g][b] = floor층에서 각 장난감을 r, g, b개 가지고 있을때 나머지를 조합하는 경우의 수 위의 점화식을 ..

https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 알고리즘 복습하던 중 배낭문제를 푸는 방법이 희미해져서 찾아서 푼 배낭문제. 0-1 Knapsack은 그리디가 정해지만, Fractional Knapsack 문제는 푸는 방법이 다양하다. 난 그중에서도 dp를 사랑하므로 dp로 접근했는데, 상당히 어려운 문제였다.. 접근 방법 배낭문제의 기본형인 12865번 문제 - 평범한 배낭 과 비슷하게 접근하였다. 배..

https://www.acmicpc.net/problem/6988 6988번: 타일 밟기 첫째 줄에는 타일의 개수 N이 주어진다. N은 3 이상 3,000 이하이다. 둘째 줄에는 N개의 타일에 적힌 자연수들이 증가하는 순서로 빈칸을 사이에 두고 주어진다. 타일에 적힌 자연수들은 각각 1,000,0 www.acmicpc.net 목에 칼이들어와도 하루 한문제 백준풀기를 실천하자. 장르는 내가 젤 좋아하는(풀면 기분좋은) dp문제. 정올문제는 언제나 어렵다.. 초등학생들이 이걸 푼다고?.. 접근 방법 숫자가 3000개 뿐이고, 두 숫자의 관계를 이용하여 2차원 dp로 풀면 어떻게든 풀릴 것 같다는 감이 왔다. 두 개의 숫자를 짝을지어주면, 숫자의 차이와 시작 지점을 지정할 수 있다. num1과 num2를 고르..

https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 간단한 dp문제를 풀고싶어서 찾은 문제. 접근 방법 동전의 개수가 무제한이므로, 목표금액 M원에서부터 N개의 동전 종류만큼 숫자를 빼가면서 0원이 될때까지 찾는 아주 간단한 발상? 그렇게 하면 dp[n]을 n원을 만드는 방법으로 설정할 수 있다. 그러나 이렇게 하니까 정답이 조금 이상했다. 왜냐하면 주어진 금액을 만족하는 동전의 조합을 구하는 것인데, 동전의 순열을 구하는 값..