Algorithm
[BOJ] 백준 16929 Two dots - Python/Java
문제 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 해설 이 문제에서 정의하는 싸이클을 판단하는 기준은 여러가지가 있는 것 같습니다. 저같은 경우에는 [1] '시작 노드와 연결된 간선(최대 4개)에 대해 동일한 간선을 이용하지 않고 다시 시작 노드로 돌아올 수 있다면, 싸이클이 형성된다' 라고 생각했습니다. 그런데 다른 분들의 풀이를 보니 [2] '시작 노드에 대해서는 방문 체크를 하지 않은 채 DFS 탐색을 하다가, 그 경로의 길이..
Algorithm
[BOJ] 백준 12100 2048(Easy) - Python/Java
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 해설 배열의 회전이나 변환, 슬라이싱을 얼마나 잘할 수 있는지를 보는 문제 같았습니다. 문제에서 요구하는 시뮬레이션 상황을 구현하기 위해서는 배열의 원소들을 상하좌우로 미는 함수를 구현해야 하는데요. 배열을 적절히 인덱싱해서 상하좌우에 해당하는 함수를 각각 구현할 수도 있지만, 저는 왼쪽으로 미는 함수 하나만 구현해놓고 배열의 전치(Transpose)와 대칭(Mi..
Algorithm
[BOJ] 백준 16973 직사각형 탈출 - Python/Java
문제 https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 해설 일반적인 너비우선탐색(BFS) 문제가 약간 변형된 문제입니다. 보통 격자점이 주어지고 너비 우선 탐색을 하는 문제에서는 이동(탐색)하는 주체가 단위 격자점의 크기와 동일한데요. 이 문제에서는 격자점의 일부를 이루는 직사각형이 이동(탐색)을 하는 주체로 설정된 것입니다. 따라서 기존의 BFS 문제를 풀 때와 달리 아래와 같이 고민해야 하는 부분이 생깁니다. 1) ..
Algorithm
[BOJ] 백준 15681 트리와 쿼리 - Python/Java
문제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 해설 해당 문제의 해설은 문제에서 주어지는 [힌트] 부분에 상세하게 제시되어 있어서 이 내용을 따라서 구현하기만 하면 정답을 구할 수 있습니다. 그래도 간단하게나마 제 해설을 적어보겠습니다. 1. 이 문제에서는 노드들을 그래프 형태로 입력받은 뒤, 트리의 루트 노드가 주어지기 때문에 루트를 기준으로 DFS를 수행하면 트리 구조를 ..
Algorithm
[BOJ] 백준 2482 색상환 - Python/Java
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 해설 이 문제에서 중요한 조건은 색상들이 "원형"으로 놓여져있다는 것인데요. 원형 배열에서는 맨 앞의 원소와 맨 마지막 원소가 서로 인접해있기 때문에, 이 둘의 관계를 적절히 처리해주는 것이 문제를 푸는데 핵심적인 열쇠가 됩니다. 저는 이 문제를 해결하기 위해 다음의 두 케이스를 나누어 생각하고, 두 케이스에서 구한 답을 총 경우의 수에 더해서 정답을 냈는데요(원형 배열에서 아래와 같이 두 가지 케이스로 나누어 문..
Algorithm
[BOJ] 백준 1013 Contact - Python/Java
문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 해설 이 문제의 포인트는 정규표현식 (100+1+ | 01)+ 을 통해 앞에서부터 문자열 매칭을 시도하면 '틀린다'는 것입니다. 그 이유는 기본적으로 Greedy한 선택이 이 문제의 정답을 보장하지 않기 때문인데요. 예를 들어 100011001 이라는 문자열을 보겠습니다. 정규표현식을 통해 앞에서부터 최대한 많은 문자열을 매칭시키면 아래와 같은 결과가 나옵니다. [정규표현식 이용]..
Algorithm
[BOJ] 백준 2533 사회망 서비스(SNS) - Python/Java
문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 해설 트리에서의 DP를 이용해서 해결할 수 있는 문제입니다. 일반적으로 일차원 배열이나, 이차원 배열에 관한 DP를 풀 때는 반복문을 순회하면서 이전값을 현재값을 구하는 데 활용하는데요. 트리는 이러한 구조가 현재 노드와 자식 노드가 갖는 서브트리로 치환되어 나타난다는 점에서만 그 형태가 다르다고 볼 수 있습니다. 따라서, 기본적으로 트리를 활용한 DP를 적용하기 위해서는 DFS 탐색을..
Algorithm
[BOJ] 백준 2661 좋은 수열 - Python/Java
문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 해설 이 문제는 백트랙킹과 그리디 알고리즘을 동시에 사용해서 해결한 문제입니다. 우선 문제에서는 1, 2, 3만을 가지고 길이가 N인 좋은 수열들 중 가장 작은 수를 나타내는 수열을 만들어야 하는데요. 이를 위해서는 필연적으로 작은 숫자를 우선으로 수열을 만들어보고, 해당 수열이 좋은 수열이면 문제의 조건을 만족할 것이라는 그리디한 선택을 떠올릴 수 있습니다. 하지만, 계속해서 그리디한 선택을 했을 때 ..
Algorithm
[BOJ] 백준 4811 알약 - Python/Java
문제 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 해설 DP를 통해 문제를 해결할 때 고민하는 부분은 크게 세 가지입니다. 1. 현재 상황은 이전의 상황에서 어떻게 변하는가? 2. 상황의 변화를 표현하기 위해 필요한 변수는 몇 개인가? 3. DP 테이블의 초기화는 어떻게 해야하는가? 이 문제를 위 관점에서 정의해보겠습니다. 문제에서 주어진 각 시점에서 선택할 수 있는 변화는 '완전한 알약 하나를 먹거나', '반절짜리 알약 하나를 먹거나' 두 가지입니다. 따..
Algorithm
[BOJ] 백준 1719 택배 - Python/Java
문제 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 해설 이 문제는 기본적으로 다익스트라 알고리즘을 이용해서 풀 수 있는데요. 문제에서 요구하는 X 지점에서 Y 지점을 최단거리로 이동할 때 첫번째로 방문하는 지점을 구하기 위해서는 필연적으로 이동하는 '경로' 역시 저장해줘야 하는 문제입니다. 한편, 다익스트라 알고리즘에서 경로를 저장하는 법은 Dictionary나 Map을 이용하면 쉽게 구현할 수 있습니다. 기본적으로 각 지점의 이전 지점만을 저장하기 때문에 1:1로 매핑이 될 수밖에 없기 때문인데요...
