동학 개발 운동

문제 출처 : www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해석 : 홍수가 일어나고 있고, 고슴도치는 D를 향해서 물을 피해 가야합니다. 이때의 최소 시간을 구하는 문제입니다. 단 도달할 수 없을 경우 실패 문자를 출력합니다. 문제 풀이 : 간단한 BFS 알고리즘 통해서 풀 수 있습니다. 물의 이동과 고슴도치의 이동을 유심히 살펴 순서를 정의해주면서 탐색하면 됩니다. 풀이 시간 (기록용) : 30분 풀이 코드 import heapq dx = [0, 0, 1, -..

문제 출처 : www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 해석 : 자신의 왼쪽으로만 전파를 쏘는 타워가 있다. 이 전파를 수신하기 위해서는 이보다 큰 타워여야한다. 이때 자신의 전파를 받는 전파의 인덱스를 출력하라. 문제 풀이 : 일반적인 투포인터, 2중 for문으로는 500,000만개의 타워를 처리할 수 없기 때문에 Stack을 이용해야 한다. 풀이 시간 (기록용) : 1시간 풀이 코드 (Python) from collections import..

문제 출처 : www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 해석 : 체스말이 4개이상 모이거나 1000번을 해도 4개가 모이지 않으면 게임이 끝난다 이때 끝날 때 까지의 시간을 구하는 문제이다. (주어진 조건을 모두 충족하면서) 문제 풀이 : 문제에는 주어지는 조건이 있다. 체스판에 경우에 따라서 모든 경우를 차근차근 생각해서 풀이하면 된다. 풀이 시간 (기록용) : 1시간 32분 풀이 코드 dx = [0, 0, -1, 1] dy = [1, -1..

문제 출처 : www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 해석 : 키의 대소 비교 결과가 M개 주어졌을 때 N 명의 학생들 가운데 자신의 키 순서를 정확하게 알고있는 사람의 수를 구하는 문제이다. 문제 풀이 : 그래프 탐색을 통해서 자신보다 작은 사람의 수, 자신보다 큰 사람의 수를 알고 있는 만큼 기록한다. 이후에 자신이 알고있는 사람의 키 순서가 N-1일때 그 사람은 자신의 키 순서를 정확하게 알고 있다고 볼 수 있다. 풀이 시간 (기록용) : ..

문제 출처 : www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제 해석 : 주사위를 굴리면서 바닥에 숫자가 있으면 복사하고, 없다면 주사위의 숫자를 바닥에 복사한다. 이렇게 명령을 진행할 때 마다 주사위 윗면의 수를 출력하는 문제이다. 문제 풀이 : 문제의 조건을 주의하면서 작성한다. 이때 주사위를 굴리는 경우에 따라서 변화하는 방향을 유의하면서 변경해주면 풀이할 수 있다. 풀이 시간 (기록..

문제 출처 : www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 문제 해석 : 더하기 사이클을 처리하는 알고리즘을 따라 했을 때 원래 수가 다시 나오는데 얼마나 걸리는지 구하는 문제이다. 문제 풀이 : 주어진 조건을 차근차근 구현하면 풀이 할 수 있다. 여기서 주의해서 구현해야 할 부분은 입력값이 10보다 작은 경우에는 자기 자신을 아닌 경우에는 각 자릿수의 합을 가지고 연산을 이어 간다는 점이다. 풀이 시간 (기록용) : 12분 풀이 코드 N ..

문제 출처 : www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제 해석 : 다각형의 넓이를 구하는 문제이다. 문제 풀이 : 신발끈 공식을 활용해서 풀이할 수 있다. 풀이 시간 (기록용) : 40분 12초 풀이 코드 from collections import deque import math def ccw(x1, y1, x2, y2, x3, y3): return (x1 * y2 + x2 * y3 + x3 * y1) - (y1 * x2 + y2 * x3 + y3 * x1) N = int(..

문제 출처 : www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 문제 해석 : 두 배열에 있는 부분 배열의 합이 T를 만족하느 갯수를 찾는 문제이다. 문제 풀이 : 배열의 부분합을 저장한 딕셔너리 자료형을 탐색하여 갯수를 카운트하면 된다. 풀이 시간 (기록용) : 35분 12초 풀이 코드 import sys from collections import defaultdict input =..

문제 출처 : www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 해석 : 작업에 우선 순위가 정해져 있고 우선순위를 모두 완수 해야 다음 작업을 할 수 있다. 다만 작업들은 동시에 수행 가능하다. 이때 모든 작업을 완료하는데 소요되는 시간을 출력하라 문제 풀이 : 위상정렬, 다이나믹프로그래밍을 통해서 문제를 풀이 할 수 있다. 진입 차수가 0인 것을 큐에 넣으면서 dp 테이블을 수정한다. 점화식을 다음과 같다. - dp[x] = max(dp[x]..

문제 출처 : www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 해석 : 말이 움직일 수 있는 최대 길이의 경로를 탐색한다. 여기서 바닥에 적힌 알파벳은 한번씩만 방문 가능하다. 이때의 최대 경로 길이를 반환하는 문제이다. 문제 풀이 : DFS로 문제를 풀이하면서 alpha_table을 통해서 이미 방문한 적이 있는지 없는지를 검사한다. 계속해서 변환하는 작업을 줄이기 위해 테이블을 입력 받을 때 map(ord(x)-65, input().strip..