두부의 코딩일기

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net ✅ 골드 Ⅲ 🔶 풀이 알고리즘 분류에는 자료 구조, 정렬, 우선순위 큐라고 적혀있는데 다 필요 없다. 그냥 그리디 알고리즘으로 해결할 수 있다. 마감일까지 남은 일수와 과제 점수 두 개를 입력받을 때 마감 기한 중에 가장 긴 날짜를 구한 후에 거꾸로 계산하면 된다. 예제에서는 가장 길게 남은 마감 기한은 6일이므로 6일차부터 1일차로 순서대로 내려가면 된다. 6일차: 점수 5점짜리 과제만 있음. 5일차: 과제 없음 4일차: 60, 40, 1..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net ✅ 실버 Ⅴ 🔶 풀이 편의점 카운터에서 일한다. 2원과 5원만 이용해서 최소한의 동전으로 거스름돈을 주면 된다. 해당 문제에 알고리즘 분류는 dp, 그리드 알고리즘 두 가지 방법으로 다 풀어봤다. 1️⃣ dp Bottom-Up 방법을 사용. 우리가 알 수 있는 작은 문제는 5원까지. 1원 = X 2원 = 1개 3원 = X 4원 = 2개 5원 = 1 6원부터 시작하면 시작하면 된다. dp[6] = Math.min(dp[6-2], dp[6-5]) → Math.min(dp[4], dp[1]) → 2 와 Integer.MA..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net ✅ 골드 Ⅱ 🔶 풀이 베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오. (1, 1) 부터 상, 하, 좌, 우로 움직일 수 있고 불이 켜져 있는 곳만 이동할 수 있다. 출력에서 조심해야 할 건 베시가 이동할 수 있는 방의 개수가 아니라 불을 켤 수 있는 방의 최대 개수다. 질문 게시판 보니까 실수하시는 분들이 정말 많았다. 상하좌우로 이동하..

https://www.acmicpc.net/problem/15736 15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net ✅ 실버 Ⅳ 🔶 풀이 완전 탐색으로 풀면 범위가 너무 넓어서 시간 초과가 발생한다. 규칙을 찾아서 해결해줘야되는 문제. 1은 약수가 1개, 한 번 뒤집힘 2는 약수가 2개, 두 번 뒤집힘 = 그대로 청색 4는 약수가 3개, 세 번 뒤집힘 6은 약수가 4개, 네 번 뒤집힘 = 그대로 청색 9는 약수가 3개, 세 번 뒤집힘 루트 N이 정수일 때만 백기 상태로 뒤집히는 것을 알 수 있다. 따..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net ✅ 골드Ⅱ 🔶 풀이 브루트 포스 형식으로 알고리즘을 진행했더니 속도와 메모리면에서 전혀 효율적이지 못 했다. 구글링을 해보니까 Disjoint-Set (Union-Find) 알고리즘으로 해결한 분을 봤고, 그 분의 코드와 해설을 가져와봤다. ✔️ 예제 2번 게이트 수: 4개 비행기 수: 6개 비행기 도착 순서: 2 → 2 → 3 → 3 → 4 → 4 첫번째 비행기..

https://www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net ✅ 골드 Ⅰ 🔶 풀이 배달해야하는 곳은 총 2곳이고, 같은 방향으로 연속해서 이동할 수 없음. 단순 bfs를 돌리면서 신경써야할 건 총 두 가지였다. 1️⃣ 같은 방향으로 연속해서 이동할 수 없다. 2️⃣ 현재까지 배달한 곳 1️⃣번의 경우에는 아래와 같은 방법으로 쉽게 해결할 수 있다. // 같은 방향으로 연속해서 움직일 수 없음 if (cur.d == d) continue; 2️⃣번의 경우에 필자는 배달해..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 임의의 버튼이 고장났을 경우 채널 N으로 이동하기 위해서 눌러야하는 버튼의 최소값. 완전탐색 브루트포스 문제. 1️⃣ 지금 보고 있는 채널은 100번 2️⃣ 고장난 버튼이 없을 수도 있다. 3️⃣ 완전탐색의 범위는 0 - 999,999 필자는 주로 StringTokenizer을 사용하는데 2️⃣번 예외에서 고장난 버튼이 0개면 Null Point 에러가 발생한..

https://www.acmicpc.net/problem/5107 5107번: 마니또 N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와 www.acmicpc.net ✅ 실버Ⅰ 🔶 풀이 A에서 출발해서 B, C, ··· 를 지나서 다시 A로 돌아오는 경우가 몇 개나 발생하는가. 1️⃣ 선행을 베푸는 사람과 선행을 받는 사람은 결코 중복되지 않는다. 2️⃣ 이름의 길이는 10글자가 넘지 않고 테스트 케이스마다 사람은 3명에서 20명이다. 해당 문제에서는 딱히 신경써야할 조건은 없다. 1️⃣번 조건을 봤을 때 HashMap을 사용하면 될 것 같다고 생각했다. Hash..

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net ✅ 골드 Ⅱ 🔶 풀이 보드에 적힌 숫자만큼 동,서,남,북 4방향으로 이동하면서 최대 몇 번의 동전을 움직일 수 있는지 구하는 문제. dfs와 dp를 이용하는 문제. 1️⃣ 동전이 구멍에 빠지거나 보드의 바깥으로 나가면 게임 종료 2️⃣ 동전을 무한번 움직일 수 있을 경우 -1을 출력 게임이 종료되는 조건은 위와 같다. 1️⃣번 조건은 dfs, bfs를 한 번이라도 풀어봤다면 쉽게 해결할 수 있다...

https://www.acmicpc.net/problem/15831 15831번: 준표의 조약돌 첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조 www.acmicpc.net ✅ 골드 Ⅲ 🔶 풀이 해당 문제는 그냥 느낌대로 풀고 봤더니 알고리즘 분류가 두 포인터라고 한다. 1️⃣ 검은 조약돌의 개수를 B개 이하로 줍고 싶다. 2️⃣ 하얀 조약돌의 개수를 W개 이상으로 줍고 싶다. 위 조건을 충족되는 가장 긴 구간의 산책로 길이를 구하면 된다. 예제 1번을 통해서 어떻게 진행되는지 살펴보겠다. 10 1 2 WBBWWBWWBW 우선 시작점과 도착점을 모두 0으..