동학 개발 운동

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

SQL 이란 ? - Structured Query Language의 약자로 구조화된 질의 언어 - 데이터를 조회, 수정, 갱신 할 수 있는 명령어 - MySQL, Oracle, MariaDB등이 있음 ( 아래는 MySQL을 기준으로 작성 ) SELECT SELECT 문은 테이블에서 원하는 정보를 불러올 때 사용하는 문법 테이블의 열에 속하는 데이터를 불러온다. *은 모든 것을 가져오는 것을 뜻함 SELECT col1, col2, .... FROM table_name; DISTINCT 중복을 배제하고 고유값만을 출력하고자 할 때 사용 ( SELECT와 같이 사용 ) SELECT DISTINCT col1, col2, ... FROM table_name; WHERE 조건을 걸어 검색하고자 할 때 사용 SELE..

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

문제 출처 : www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 해석 : 각 건물을 건설하기 위해서는 선행되어야 하는 건물이 있다. 이를 고려하였을 때 각 건물이 지어지는데 필요한 최소 시간을 출력하라 문제 풀이 : 위상정렬과 DP를 활용하면 풀 수 있다. 풀이 코드 from collections import defaultdict, deque N = int(input()) answer = [0] * (N+1) cost = [0] * (N+1) ..

문제 출처 : www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 해석 : N개의 보석과 K개의 가방이 있다 이때 가방에는 1개의 보석만 넣을 수 있고 무게 제한이 있다. 또한 보석에는 무게와 가치가 매겨져 있다. 가장 높은 가치의 보석을 훔치는 경우의 가치의 합을 구하라 문제 풀이 : 정렬과 heapq를 활용해서 풀 수 있다. 배낭을 오름차순으로 정렬하고 보석은 무게를 기준으로 오름차순으로 정렬..