Algorithm
[BOJ] 백준 11000 강의실 배정 - Python/Java
문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 해설 그리디(Greedy)하게 풀 수 있는 간단한 문제이지만 약간의 고민해야 할 부분이 있는 문제라고 생각합니다. 기본적으로 이 문제는 '어떤 강의실을 차지하고 있는 수업이 끝나면, 해당 강의실을 재사용할 수 있다'는 점을 생각해야 하는데요. 이를 바탕으로 시작 시간이 빠른 수업을 먼저 강의실에 배정하는 전략을 세울 수 있습니다. 그렇게 하면 수업의 시작 시간과 사용 중인 강의실의 종료 시간을 비교해서 종료 시간보다 크거나 같은 수업은 강의실을 추가로 사용하지 않을 수 있기 때문이죠. 하지만 이렇게 그리디..
Algorithm
[BOJ] 백준 22116 창영이와 퇴근 - Python/Java
문제 https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 해설 이 문제는 시작점부터 도착점까지 이동하면서 경로상의 최대 경사의 최소값을 찾는 문제로 BFS와 이분탐색을 이용하여 해결할 수 있습니다. BFS는 그래프의 최단 경로를 구할 때도 사용할 수 있지만, 이 문제에서는 모든 경로를 완전 탐색하는데도 사용할 수 있는데요. 현재 지점을 기준으로 네 방향을 바라보고, 네 방향 중에서 현재 임계값(최대 경사로 정한 값)보다 경사가 작거나 같고, 방문하지 않았다면 그 곳을 이동 가능한 영역으로 보기 때문입니다. 다시 말해서, 간단한 BFS 구현을 생각해보면 상하좌우의 네..
Algorithm
[BOJ] 백준 16235 나무 재테크 - Python/Java
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 해설 이 문제에서 구현해야 하는 내용은 그렇게 어렵지 않습니다. 봄, 여름, 가을, 계절에 해야하는 일들을 그대로 코드로 구현하면 되는데요. 우선 땅이 가진 양분 정보, 나무들의 정보, 추가되는 양분의 정보를 각각 저장하는 자료구조가 필요합니다. 저같은 경우 파이썬에서는 모두 리스트로 입력을 받았고, 자바에서는 나무들의 정보는 우선순위큐를 이용했고 나머지는 배열을 이용해서 받..
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자 이상이다...
Algorithm
[BOJ] 백준 1405 미친 로봇 - Python/Java
https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 해설 깊이 우선 탐색을 이용해서 방문했던 곳을 다시 방문하지 않는 조건으로 모든 지점을 완전 탐색하는 문제입니다. 깊이 우선 탐색을 이용해서 네 방향으로 N번 이동하게 될 때, 가능한 총 경우의 수는 4^N입니다. 따라서 문제에서 주어진 N
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은 팰린드롬이 되는 것입니다. 저는 맨 처음에 각..
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 과 같은 싸이클이 만들어지는데요. 싸이클..
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번 인덱스에 들어가게 됩니다. 그러면 결과적으로 각 배열의 값은 해당 친구가 풀 수 ..
Algorithm
[BOJ] 백준 2812 크게 만들기 - Python/Java
문제 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 스택 자료구조와 그리디 알고리즘을 이용해서 풀 수 있는 문제입니다. N개로 이루어진 숫자 중에서 K개를 삭제해야 하고, 주어진 숫자의 순서가 변하면 안된다는 점이 스택 자료구조를 쓸 수 있는 이유가 됩니다. 그리고 각 숫자를 삭제할 것인가 말 것인가를 결정할 때 그리디(Greedy)하게 결정할 수 있죠. 우선 결과로 리턴할 문자열 s와 문제에서 주어진 숫자 Num이 있다고 해보겠습니다. 그렇다면 아래 로직에 따라 s를 만들어갈 수 있습니다. 1) s가 빈 문자열이면 무조건 현재 Num의 숫자를 더해줍니다. 2) s가 빈 문자열이..
Algorithm
[BOJ] 백준 9370 미확인 도착지 - Python/Java
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net [해설] 이 문제는 다익스트라 알고리즘을 기반으로 해결할 수 있으며 기본 아이디어는 다음과 같습니다. 경로 1) (시작점 → g) + (g → h) + (h → 도착점) 경로 2) (시작점 → h) + (h → g) + (g → 도착점) 위 두 가지 경로 중에서 비용이 더 적은 경로와 (시작점 → 도착점)을 직접 구한 비용이 같다면 해당 도착점은 반드시 (g, h) 도로를 지난다고 볼 수 있..
