CS/Algorithm
[BOJ] 백준 2812 크게 만들기 - Python/Java
문제 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 스택 자료구조와 그리디 알고리즘을 이용해서 풀 수 있는 문제입니다. N개로 이루어진 숫자 중에서 K개를 삭제해야 하고, 주어진 숫자의 순서가 변하면 안된다는 점이 스택 자료구조를 쓸 수 있는 이유가 됩니다. 그리고 각 숫자를 삭제할 것인가 말 것인가를 결정할 때 그리디(Greedy)하게 결정할 수 있죠. 우선 결과로 리턴할 문자열 s와 문제에서 주어진 숫자 Num이 있다고 해보겠습니다. 그렇다면 아래 로직에 따라 s를 만들어갈 수 있습니다. 1) s가 빈 문자열이면 무조건 현재 Num의 숫자를 더해줍니다. 2) s가 빈 문자열이..
CS/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) 도로를 지난다고 볼 수 있..
CS/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를 사용했습니다. 한편, 이 문제의 핵심은 "이전 세대의 드래곤 커브가 현재 세대의 드래곤 커브를 만드는 데 사용된다"는 점..
CS/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를 이..
CS/Algorithm
[BOJ] 백준 18119 단어 암기 - Python/Java
https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 해설 비트마스킹을 이용해서 풀 수 있는 전형적인 문제입니다. 문제에서 주어지는 영어 단어는 모두 소문자로만 주어지기 때문에, 이 문제에서 다뤄야 할 모든 알파벳 경우의 수는 26가지입니다. 따라서 모든 알파벳을 다 알고 있는 경우를 11111111111111111111111111, 모든 알파벳을 모두 모르는 경우를 00000000000000000000000000이라고 표현할 수 있죠. 그리고 ..
CS/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를 구하는 함수를 짰습니다. 그렇다면 보다 구..
CS/Algorithm
[BOJ] 백준 1707 이분 그래프 - Python/Java
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 해설 먼저 이 문제를 풀 때 가장 중요한 것은 이분 그래프가 무엇인지 정확히 이해하는 것인데요. 문제에서 정의한 이분 그래프는 아래와 같습니다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)라 부른다. 즉, 그래프의 모든 정점을 크게 두 집합으로 나눌건데, 인접한 녀석..
CS/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
CS/Algorithm
[프로그래머스(Python/Java)] 빛의 경로 사이클
https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 이 문제는 배열을 적절히 잘 사용할 수 있는지에 대한 구현 능력과 / 문제 조건에 대한 상황을 잘 이해했는지를 테스트하는 문제인 것 같습니다. [1] 먼저 "배열을 적절히 잘 사용할 수 있는가?"는 빛이 범위 밖을 벗어났을 때와 어떤 지점에서 빛이 꺾일 때 어떻게 처리를 해줄 것인가에 대한 내용인데요. 아래 주석에 써놓은 것처럼 범위..
CS/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..
