동학 개발 운동

문제 출처 : 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..

문제 출처 : www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 문제 해석 : 마을을 두개로 분할 하려고 한다. 이때 마을 내부에 있는 길의 Cost가 최소가 되도록 마을을 분할 해야한다. 문제 풀이 : 최소 신장트리를 이용해서 마을 전체를 순회하는 도로를 구성한 다음 가장 큰 비용을 가진 길 하나를 제거하면 각자 모든 원소를 포함하는 2개의 마을 도로가 생성된다. 풀이 코드 import sys input = sys.std..

문제 출처 : www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 해석 : 나누기 3, 나누기 2, 빼기 1을 수행해서 1로 만드는데 가장 적은 횟수의 연산을 한 경우를 찾는 것이다. 문제 풀이 : Q를 이용하면 풀 수 있다. 풀이 코드 from collections import deque N = int(input()) Q = deque() Q.append([N]) answer = [] while Q: arr = Q.popleft() x = arr[0] if x == 1: answer = arr break if x % 3 == 0: Q.append([x//3] ..

문제 출처 : www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 해석 : 어떠한 소수를 연속된 소수의 합으로 표현 할 수 있는 경우의 수를 구하여 반환하는 문제이다. 문제 풀이 : 이 문제를 풀기 위해서는 2가지 알고리즘을 적용해야 한다. 1. 에라토스테네스의 체 : 주어진 N까지의 소수를 미리 구한다. ( 모든 경우를 체크해서 소수를 만들 경우 시간 초과가 발생합니다. ) 2. 투포인터 : start, end 두 개의 포인터를 이용해서 원하는 값보다 작은 경우 end += 1을 큰 경우에는 start += 1을 적용해서 end가 N이 될때까지 수행합니다. 풀이 코드 imp..

문제 출처 : www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 문제 해석 : 그룹을 만들어 그룹내에 키차이가 최소가 되도록 모든 그룹의 키 차이를 구하는 문제이다. 문제 풀이 : N명의 학생들을 K개의 그룹으로 나눈다고 했을 때 달리 말하면 N-K 개의 키 차이를 무시할 수 있다는 것이다. 이러한 원리에 따라서 알고리즘을 작성하면 풀 수 있다. 풀이 코드 N, K = map(int, input().split()) person = list(map(int,..

문제 출처 : www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해석 : 빙산은 물에 접한 면의 수만큼 녹는다. 이때 빙산이 2개의 덩어리로 분리 될 때 까지 걸리는 시간을 구하라. 문제 풀이 : 2개의 기능을 구현하면 풀 수 있다. 1. 빙산이 2개로 분리되었는지 검사하는 함수 2. 빙산이 1년이 지날 때마다 녹이는 함수 두 개의 함수 모두 BFS 알고리즘을 통해서 풀 수 있으며 풀이는 아래와 같다. 풀이 코드 import sys, copy fro..