두부의 코딩일기

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 dp[날짜][지각 횟수][연속으로 결석한 횟수] 를 기준으로 dp 배열을 생성했다. 개근상을 받을 수 있는 조건은 총 6가지다. 1. 0번 지각, 0번 연속 결석 → dp[N][0][0] 2. 0번 지각, 1번 연속 결석 → dp[N][0][1] 3. 0번 지각, 2번 연속 결석 → dp[N][0][2] 4. 1번 지각, 0번 연속 결석 → dp[N][1][0] 5. 1번 지각, 1번 연..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 해당 문제는 완전 탐색으로 진행하면 시간 초과가 발생한다. 때문에 정렬과 우선순위 큐를 이용해서 해결할 수 있다. 위 그림은 예제 1번을 보기 좋게 표현했다. 수업이 끝난 직후에 다음 수업을 시작할 수 있다고 했으므로 강의실 2개를 사용한다. 우선, 시작 시간을 기준으로 오름차순 정렬을 해줘야된다. 마감 시간을 기준으로 오름차순 정렬하게 되면 아래와 같은 상황에서 반례가 발생한다. 4 1 2 1 4 2 6 4 5 1. (1..

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net ✅ 플레티넘 Ⅴ 🔶 풀이 경찰차 A (1, 1) 과 경찰차 B (N, N) 이 있다. 순서대로 사건이 일어났을 때, 경찰차가 이동하는 최소 거리의 합을 구하라. 해당 문제도 dp다. 하지만 점화식을 찾는 dp는 아니고, dfs를 이용해서 문제를 해결해나가면 된다. dp[one][two] 는 "경찰차 A의 위치가 one번째 사건이고, 경찰차 B의 위치는 two번째 사건에 위치..

https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net ✅ 플래티넘 Ⅴ 🔶 풀이 내가 선택한 플래티넘 문제는 개인적으로 가장 어려워하는 dp.. 음의 차이를 나타내는 힘든 정도의 최솟값을 구하라. 문제의 이해를 돕기 위해 편의상 상덕이를 A, 희원이를 B로 하겠다. dp 배열은 각자 마지막으로 부른 음을 기준으로 힘든 정도의 최솟값을 저장해줬다. 현재 상태: dp[A가 마지막으로 부른 음][B가 마지막으로 부른 음]; A가 다음으로 부를 경우: dp[n..

https://www.acmicpc.net/problem/25379 25379번: 피하자 음이 아닌 정수로 이루어진 길이 N의 배열 A = [A1, A2, · · · , AN]가 있다. 배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장 www.acmicpc.net 🔶 풀이 알고리즘은 정말 둘 중 하나다. 엄청 잘 풀리거나 끝까지 막히거나..😭 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 만들어라. 즉, 모든 짝수 혹은 홀수를 왼쪽 혹은 오른쪽으로 이동시켜라. 필자는 짝수를 선택해서 왼쪽 혹은 오른쪽 끝으로 이동시켰다. i번째 정수가 짝수라고 가정했을 때, 왼쪽 끝으로 이동할 경우에는 i, 오른쪽 끝으로 이동할 경우에는 N -..

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net · · · (이하 생략) 🔶 풀이 필자는 해당 문제를 아래와 같은 순서대로 풀었다. 1. 박스 정보를 가까운 순으로 정렬하기. : 거리가 먼 박스를 싣고 이동하면 중간에 옮길 수 있는 상자를 놓칠 수 있다. 따라서, 받는 마을이 가까운 순으로 정렬해 주고, 보내는 마을을 가까운 순으로 정렬해 주면 된다. public static class Box implements Compar..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 🔶 풀이 한 번의 이동에서 옮길 수 있는 물품들의 최대값을 구하시오. 가능한 최대 중량을 찾기 위해서는 bfs로만 풀 수 없고, 이진 탐색을 이용해야한다. 1. 입력하는 과정에서 min, max 값을 선언해주고, 다리는 양방향이므로 arrList에 두 번씩 입력해준다. for (int i=0; i

https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 🔶 풀이 11명 선수의 포지션 별 능력이 입력된다. 포지션 별로 중복되지 않은 선수 11명을 뽑아서 최대 점수를 구하라. 완전 탐색으로 진행하게 되면 경우의 수는 11! (39,916,800)로 시간 초과가 발생할 수 있다. 때문에 백트래킹을 사용해서 시간 복잡도를 줄여야한다. 위 문제에서 능력치가 0인 경우에는 해당 포지션에 설 수 없다고 했다. 또한, 이미 선발된 선수가 또 다시 선발될 수 없으므로 selected[] 배..

https://www.acmicpc.net/problem/2412 2412번: 암벽 등반 어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동 www.acmicpc.net 🔶 풀이 BFS로 충분히 해결할 수 있는 문제. (0, 0)에서 시작해서 (x, T)까지 올라가면 된다. 우선 입력값을 y값을 기준으로 배열을 만들어서 입력해줬다. rock = new ArrayList[200001]; // T의 최대값: 2,000,000 for (int i=0; i

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 🔶 풀이 불특정한 도시 A에서 출발해서 한 바퀴를 돌고 도시 A로 다시 돌아왔을 때 최소 비용을 구하는 문제. 시간 제한이 적기 때문에 dp와 비트마스크를 활용해야함. 비트마스크(Bit Mask) 알고리즘 장점 및 연산자 사용 방법 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여 정수의 이진수 표현을 자료 구조로 쓰는 기법 ✅ 이진..