Algorithm
[BOJ] 백준 15685 드래곤 커브 - Python/Java
15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제를 한 두 세번정도 읽으면서 이해를 하고, 그대로 구현해주면 되는 문제입니다. 다만, 이 문제에서 X가 증가하는 방향이 오른쪽이고, Y가 증가하는 방향이 아래쪽이라는 점에서 일반적인 이차원 리스트의 인덱싱과 조금 다른데요. 이 부분은 X, Y를 그냥 바꿔서 생각하면 됩니다. 그런데 저는 그냥 있는 그대로 X, Y를 사용했습니다. 한편, 이 문제의 핵심은 "이전 세대의 드래곤 커브가 현재 세대의 드래곤 커브를 만드는 데 사용된다"는 점..
Algorithm
[BOJ] 백준 1915 가장 큰 정사각형 - Python/Java
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이 문제를 직관적으로 생각해보면 아래와 같은 완전탐색에 대한 아이디어를 떠올릴 수 있습니다. "이차원 배열에 존재하는 모든 점에 대해 해당 지점을 오른쪽 아래 모서리라고 생각한 뒤, 정사각형 길이를 1부터 늘려나가보면서 이전 지점들을 탐색하고, 모두 1로 채워져있으면 정사각형 크기를 갱신한다." 하지만 이 방식으로 문제를 해결하면 결국 맨 끝의 점에서는 시간복잡도가 O(N^3)에 가까워지는 것을 예상할 수 있습니다. 따라서, 이 문제는 위의 정의를 바탕으로 DP를 이..
Algorithm
[BOJ] 백준 18119 단어 암기 - Python/Java
https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 해설 비트마스킹을 이용해서 풀 수 있는 전형적인 문제입니다. 문제에서 주어지는 영어 단어는 모두 소문자로만 주어지기 때문에, 이 문제에서 다뤄야 할 모든 알파벳 경우의 수는 26가지입니다. 따라서 모든 알파벳을 다 알고 있는 경우를 11111111111111111111111111, 모든 알파벳을 모두 모르는 경우를 00000000000000000000000000이라고 표현할 수 있죠. 그리고 ..
Algorithm
[BOJ] 백준 1253 좋다 - Python/Java
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 해설 주어진 N개의 수 중에서 임의의 숫자 K가 서로 다른 두 숫자 P, Q의 합으로 표현이 되면 K를 "좋다(Good)"이라고 하며, 좋은 수의 개수를 구하는 것이 문제의 목표인데요. 저는 이분 탐색을 이용해서 문제를 풀었습니다. 파이썬은 bisect 라이브러리를 이용했고, 자바같은 경우 직접 리스트에서 찾고자 하는 숫자가 들어갈 수 있는 lowerBound, upperBound를 구하는 함수를 짰습니다. 그렇다면 보다 구..
Algorithm
[BOJ] 백준 1707 이분 그래프 - Python/Java
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 해설 먼저 이 문제를 풀 때 가장 중요한 것은 이분 그래프가 무엇인지 정확히 이해하는 것인데요. 문제에서 정의한 이분 그래프는 아래와 같습니다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)라 부른다. 즉, 그래프의 모든 정점을 크게 두 집합으로 나눌건데, 인접한 녀석..
Algorithm
[프로그래머스(Python/Java)] 행렬 테두리 회전하기
https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 배열의 원소 이동을 잘 구현할 수 있는지를 묻는 문제입니다. 아래 문제의 조건처럼 1
Algorithm
[프로그래머스(Python/Java)] 빛의 경로 사이클
https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 이 문제는 배열을 적절히 잘 사용할 수 있는지에 대한 구현 능력과 / 문제 조건에 대한 상황을 잘 이해했는지를 테스트하는 문제인 것 같습니다. [1] 먼저 "배열을 적절히 잘 사용할 수 있는가?"는 빛이 범위 밖을 벗어났을 때와 어떤 지점에서 빛이 꺾일 때 어떻게 처리를 해줄 것인가에 대한 내용인데요. 아래 주석에 써놓은 것처럼 범위..
Algorithm
[프로그래머스(Python/Java)] 땅따먹기
https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 이 문제는 각 행의 원소 개수가 4개로 고정되어 있고, 행을 한 칸씩 내려갈 때 그 이전 행과 동일한 열을 선택할 수 없는 조건만 존재합니다. 완전 탐색으로 모든 경우를 보기 위해서는 O(3^N) 만큼의 시간 복잡도가 소요되기 때문에 제한된 시간 안에 문제를 해결할 수 없습니다. *시간 복잡도가 O(3^N)인 이유는 각 행을 내려갈 때마다 3..
Algorithm
[BOJ] 백준 1914 하노이탑 - Python/Java
https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 해설 이 문제가 실버2인 이유는 아마 대중적으로 알려진 문제라서 그렇지 않을까 생각합니다. 혼자서 풀려고 했을 때는 정말 모르겠어서 다른 사람들의 풀이를 참고해서 이해할 수밖에 없었습니다...☹️ 하노이탑 문제의 핵심 아이디어는 원반 N개 문제를 해결하기 위해서는 원반이 N-1개인 문제를 해결하면 된다는 것인데요. 구체적으로 풀어서 이야기해보면 아래와 같습니다. 1) N개의 원반이 주어지면 위에서부..
Algorithm
[백준(Python/Java)] 6497_전력난
6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 이 문제는 도시의 모든 집을 연결할 수 있는 최소한의 간선(길)만을 선택하는 문제로, 최소 스패닝 트리(Minimum Spanning Tree, MST)를 이용해 풀 수 있습니다. MST를 구현하는 방법에는 우선순위 큐를 이용하는 방법, 크루스칼 알고리즘을 이용하는 방법과 프림 알고리즘을 이용하는 방법이 있는데요. 이 문제에서는 MST에 보편적으로 쓰이는 크루스칼 알고리즘을 이용해 해결했습니다. 개별 간선(Edge)은 해당 길의 비용과 이어진 두 마을(정점)의 정보를 가지..
