CS/Algorithm
[BOJ] 백준 4811 알약 - Python/Java
문제 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 해설 DP를 통해 문제를 해결할 때 고민하는 부분은 크게 세 가지입니다. 1. 현재 상황은 이전의 상황에서 어떻게 변하는가? 2. 상황의 변화를 표현하기 위해 필요한 변수는 몇 개인가? 3. DP 테이블의 초기화는 어떻게 해야하는가? 이 문제를 위 관점에서 정의해보겠습니다. 문제에서 주어진 각 시점에서 선택할 수 있는 변화는 '완전한 알약 하나를 먹거나', '반절짜리 알약 하나를 먹거나' 두 가지입니다. 따..
CS/Algorithm
[BOJ] 백준 1719 택배 - Python/Java
문제 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 해설 이 문제는 기본적으로 다익스트라 알고리즘을 이용해서 풀 수 있는데요. 문제에서 요구하는 X 지점에서 Y 지점을 최단거리로 이동할 때 첫번째로 방문하는 지점을 구하기 위해서는 필연적으로 이동하는 '경로' 역시 저장해줘야 하는 문제입니다. 한편, 다익스트라 알고리즘에서 경로를 저장하는 법은 Dictionary나 Map을 이용하면 쉽게 구현할 수 있습니다. 기본적으로 각 지점의 이전 지점만을 저장하기 때문에 1:1로 매핑이 될 수밖에 없기 때문인데요...
CS/Algorithm
[BOJ] 백준 11000 강의실 배정 - Python/Java
문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 해설 그리디(Greedy)하게 풀 수 있는 간단한 문제이지만 약간의 고민해야 할 부분이 있는 문제라고 생각합니다. 기본적으로 이 문제는 '어떤 강의실을 차지하고 있는 수업이 끝나면, 해당 강의실을 재사용할 수 있다'는 점을 생각해야 하는데요. 이를 바탕으로 시작 시간이 빠른 수업을 먼저 강의실에 배정하는 전략을 세울 수 있습니다. 그렇게 하면 수업의 시작 시간과 사용 중인 강의실의 종료 시간을 비교해서 종료 시간보다 크거나 같은 수업은 강의실을 추가로 사용하지 않을 수 있기 때문이죠. 하지만 이렇게 그리디..
CS/Algorithm
[BOJ] 백준 22116 창영이와 퇴근 - Python/Java
문제 https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 해설 이 문제는 시작점부터 도착점까지 이동하면서 경로상의 최대 경사의 최소값을 찾는 문제로 BFS와 이분탐색을 이용하여 해결할 수 있습니다. BFS는 그래프의 최단 경로를 구할 때도 사용할 수 있지만, 이 문제에서는 모든 경로를 완전 탐색하는데도 사용할 수 있는데요. 현재 지점을 기준으로 네 방향을 바라보고, 네 방향 중에서 현재 임계값(최대 경사로 정한 값)보다 경사가 작거나 같고, 방문하지 않았다면 그 곳을 이동 가능한 영역으로 보기 때문입니다. 다시 말해서, 간단한 BFS 구현을 생각해보면 상하좌우의 네..
CS/Algorithm
[BOJ] 백준 16235 나무 재테크 - Python/Java
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 해설 이 문제에서 구현해야 하는 내용은 그렇게 어렵지 않습니다. 봄, 여름, 가을, 계절에 해야하는 일들을 그대로 코드로 구현하면 되는데요. 우선 땅이 가진 양분 정보, 나무들의 정보, 추가되는 양분의 정보를 각각 저장하는 자료구조가 필요합니다. 저같은 경우 파이썬에서는 모두 리스트로 입력을 받았고, 자바에서는 나무들의 정보는 우선순위큐를 이용했고 나머지는 배열을 이용해서 받..
CS/Algorithm
[BOJ] 백준 1759 암호 만들기 - Python/Java
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해설 주어진 문자열의 길이가 최대 15밖에 되지 않기 때문에 모든 경우를 완전탐색할 수 있는 문제입니다. 다시 말해서, 각 문자를 비밀번호에 포함/미포함으로 완전 탐색을 해도 2^15번만에 모든 경우를 탐색할 수 있는 것이죠. 구체적으로 문제의 조건을 들여다보겠습니다. 문제에서는 비밀번호가 "1) 사전식으로 오름차순 정렬되어 있다. 2) 자음의 개수는 2자 이상이다. 3) 모음의 개수는 1자 이상이다...
CS/Algorithm
[BOJ] 백준 1405 미친 로봇 - Python/Java
https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 해설 깊이 우선 탐색을 이용해서 방문했던 곳을 다시 방문하지 않는 조건으로 모든 지점을 완전 탐색하는 문제입니다. 깊이 우선 탐색을 이용해서 네 방향으로 N번 이동하게 될 때, 가능한 총 경우의 수는 4^N입니다. 따라서 문제에서 주어진 N
CS/Algorithm
[BOJ] 백준 10942 펠린드롬? - Python/Java
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 해설 이 문제를 풀 때 가장 중요한 포인트는 두 가지라고 생각합니다. 1. 문제에서 주어진 각 숫자 자체는 팰린드롬 수가 아니어도 된다는 것 2. DP 메모이제이션의 순서를 고민해봐야 한다는 것 - 먼저 이 문제에서 팰린드롬인지를 확인할 때는 입력으로 주어진 개별 숫자가 팰린드롬인지의 여부는 관계가 없습니다. 즉, 입력이 123, 123 이렇게 두 수가 들어왔다고 하면, 123 / 123은 팰린드롬이 되는 것입니다. 저는 맨 처음에 각..
CS/Algorithm
[BOJ] 백준 2668 숫자고르기 - Python/Java
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 해설 깊이 우선 탐색을 이용해서 싸이클을 판별하는 문제입니다. 아래와 같이 입력이 주어졌다고 해보겠습니다. 1 2 3 4 5 6 7 3 1 1 5 5 4 6 그러면 윗줄의 각 번호를 하나의 노드라고 생각하고, 아랫줄의 각 번호를 해당 노드에서 도착할 수 있는 노드라고 이해할 수 있습니다. 이 때, 1번 노드에서 출발한다고 하면 1 → 3 → 1 과 같은 싸이클이 만들어지는데요. 싸이클..
CS/Algorithm
[BOJ] 백준 11578 팀원 모집 - Python/Java
https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 해설 조합을 이용한 완전탐색, 그리고 비트마스킹을 이용해서 풀이한 문제입니다. 맨 처음에 각 친구가 알고 있는 문제를 비트로 표현한 후, 이를 배열(prob)에 담아주는데요. 예를 들어 1번 친구가 3, 4, 5번 문제를 알고 있다면 0b11100(2) = 4+8+12 = 24 라는 숫자가 배열의 1번 인덱스에 들어가게 됩니다. 그러면 결과적으로 각 배열의 값은 해당 친구가 풀 수 ..
