동학 개발 운동

문제 출처 : www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 해석 : 가장 큰 변을 가지는 삼각형을 계속해서 이어 붙인다. 이때 N 번째 삼각형의 한번의 길이를 구하라. (삼각형은 정삼각형이다.) 문제 풀이 : 전형적인 DP 문제로서 P[i] = P[i-3] + P[i-2] 이다. 풀이 코드 T = int(input()) for test_case in range(T): N = int(input()) P = [0, 1, 1, 1, 2, 2, 3, 4, 5, ..

문제 출처 : www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 해석 : 해빈이는 매일 다른 옷을 입고 싶어한다. 따라서 가지고 있는 옷에 따른 경우의 수를 구해보자. 단 한가지 카테고리에서 2개 이상의 물건을 착용할 수 는 없다. 문제 풀이 : 딕셔너리를 이용해서 각 카테코리별 아이템을 저장한다. 여기에는 착용하지 않았음을 나타내는 " " 도 포함한다. 그 후 ..

문제 출처 : www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 해석 : 50미터 마다 목이 마르지 않게 맥주를 마신다. 이때 목적지까지 목이 마르지 않게 도착할 수 있는지 주어진 편의점과 시작, 도착점의 거리를 이용해서 계산하는 문제이다. 문제 풀이 : BFS와 플루이드 - 와셜 알고리즘을 이용해서 풀이 할 수 있다. 입력을 통해서 이동 가능한 곳을 1로 표시하고 아닌 곳은 INF로 표시한 다음 모든 가능성에 대해서 검사하고 possible[0]N..

문제 출처 : www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 해석 : 각각 주어지는 DSLR의 조건을 확인하면서 연산을 수행해 원하는 숫자가 나올때 까지의 연산을 출력하는 문제이다. 문제 풀이 : 이 문제 또한 BFS문제이다. 각각의 결과와 명령들을 저장한 배열을 큐에 넣고 원하는 결과가 나올 때 까지 반복하면 문제를 풀 수 있다. 다만 visited 처리를 해줘야 시간 초과, 메모리 초과를 벗어 날 수 있다. 풀이 코드 from coll..

문제 출처 : www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 문제 해석 : 최대 힙을 구현하는 문제이다. 문제 풀이 : 파이썬에서 제공하는 heapq를 이용하면서 입력을 -1을 곱해서 출력 또한 -1을 곱해서 하면 최소힙을 이용해서 최대힙과 동일한 기능을 수행할 수 있다. 가능한 다른 풀이 : 직접 최대힙을 구현하여 풀이 할 수 있다. 풀이 코드 import heapq import sys input = sys.stdin.readline ..

문제 출처 : www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 해석 : 이중 우선 순위 큐를 구현하는 문제이다. 여기서 주의할 점은 최대, 최소 힙의 역활을 동시에 수행해야 한다는 것이다. 문제 풀이 : 파이썬에서는 heapq를 제공하고 있기 때문에 이를 이용하기로 한다. 2개의 heapq를 생성하고 하나는 최대힙으로 하나는 최소힙으로 사용하면서 삭제 연산에 있어서 동기화를 위해서 sync라는 배열을 통해서 삭제시 동시에 삭제를 보장한다. -> re..

문제 출처 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 해석 : 입력된 숫자를 1, 2, 3으로만 나타낼 수 있는 경우의 수를 구하는 문제이다. 문제 풀이 : DP 문제로 dp[i] = dp[i-3]+dp[i-2]+dp[i-1] 이라는 점화식을 통해서 문제를 풀 수 있다. 이와 같은 점화식이 답이 되는 이유는 다음과 같다. 1일때 -> 1 2일때 -> 1+1, 2 3일때 -> 1+1+1, 1+2, 2+1, 3 4일때는 1+3, 2+2, 3+1 이라는 경우를 생각할 수 있다. 풀이 코드 T = int(input()) for test_case in..

문제 출처 : www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 해석 : 토마토가 익는 것은 주변에 익은 토마토에 의해서 이루어진다. 따라서 모든 토마토가 익을 때 까지 걸리는 시간을 출력하는 문제이다. 문제 풀이 : 전형적인 BFS 문제이지만 3차원이기 때문에 인덱싱을 조심해서 풀면 풀 수 있다. 풀이 코드 from collections import deque def BFS(): while Q: x,y,z = Q.popleft()..

문제 출처 :www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 해석 : x,y로 이루어진 달력은 M, N보다 크면 그 나머지 값을 가지게 되는데 1부터 시작하게 된다. 문제 풀이 : 시간 복잡도를 해결하기 위해서는 수학적 계산을 통해서 문제를 풀어야한다. X를 만족하는 M을 for 문을 통해서 반복적으로 위로 연산 하면서 찾으면 해결 할 수 있다. 풀이 코드 T = int(input()) for test_case in range(T): M,N,x,y = ma..

문제 출처 : www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문제 해석 : 주어진 문자열에 특정 문자열이 몇번 반복되는지 검사하는 문제이다. 문제 풀이 : 단순하게 이중 반복문을 통해서 문제를 풀었을 때 시간 초과가 났다. 따라서 반복문을 한번만 돌면서 이를 충족시켜야한다. 풀이 코드 import sys input = sys.stdin.readline N = int(input().rstrip()) M = int(input().rstrip()) S = input().rstrip() a..