동학 개발 운동

문제 출처 : www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해석 : 묶음을 찾는 문제이다. 즉 그래프 전체의 연결 상태가 주어졌을 때 연결 요소를 구하는 문제이다. 문제 풀이 : 모든 노드의 부모를 찾아 기록하고 그 부모의 갯수를 출력하면 이는 연결 요소를 찾는 것과 같은 작업이다. 풀이 코드 def find_parent(parent, x): if parent[x] != x: parent..

문제 출처 : www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 해석 : 주어진 조건에 따라 집합 연산을 수행하는 프로그램을 작성하는 문제이다. 문제 풀이 : 까다로운 조건이 없어 주어진 제시문대로 코드를 작성하면 풀 수 있다. -> Pypy3로 컴파일 하면 메모리 초과가 난다. 이는 pypy3가 내부적으로 더 메모리를 많이 사용하기 때문이 것 같다. 풀이 코드 import sys input = sys.stdin.readline M = int(input()) S = set() for _ i..

문제 출처 : www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 : 이동 가능한지 여부를 경로를 토대로 구하는 문제이다. 몇번을 어디를 거쳐가는 지는 생각하지 않고 어떤 방식으로든 갈 수 있으면 1 없으면 0을 출력하면 된다. 문제 풀이 : 플루이드 - 워셜 알고리즘을 통해서 해결 가능하다. 플루이드 - 워셜 알고리즘은 거쳐가는 모든 경우를 고려하여 가능한지 검사 할 수 있다. 풀이 코드 import sys input = sys.stdin.readline N = int(input()) vis..

문제 출처 : www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 해석 : ATM에 줄을 서있는 모든 사람이 업무를 마치는 순간까지 걸리는 시간이 최소가 되게 하는 문제이다. 문제 풀이 : 앞에서의 대기 시간이 줄어들면 뒤의 사람의 대기시간이 줄어드는 것이 보장되기 때문에 항상 적은 숫자가 앞으로 갈 수록 시간이 적게 걸리는 것이 보장된다. -> Ai = A1 + A2 + ...... + Ai-1 + Ai 이기 때문이다. 풀이 코드 N = int(input()) P = list(map(..

문제 출처 : www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해석 : 최소힙을 절댓값을 기준으로 생성하고 이를 구현하는 문제이다. 문제 풀이 : 파이썬에서 기본으로 제공하는 heapq를 이용하는데 이때 push, pop에 단순한 숫자말고 [절댓값, 부호]로 삽입하고 출력을 절댓값 * 부호로 함으로 해결할 수 있다. 가능한 다른 풀이 : 직접 힙을 구현하여 풀이 할 수 있다. 풀이 코드 import heapq import sys i..

문제 출처 : www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 해석 : 적록 색약인 사람과 아닌 사람이 보는 그림에서 구역 수의 차이를 구하는 문제이다. 문제 풀이 : 전형적인 BFS의 구역 구하기 문제에서 적색과 녹색을 구별하지 못하는 부분이 추가된 문제이다. 이 부분을 새로운 배열을 선언함으로 중복 코딩 없이 해결 할 수 있다. 풀이 코드 from collections import deque def normal(a, b, Arr): Q = d..

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