동학 개발 운동

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

개발을 진행할 때 필수적으로 사용하게 되는 서비스중 하나는 Git 입니다. 자신이 작성한 코드를 공유하거나 협업을 진행하는데 가장 활발하게 사용되는 Git 저장소중 하나인 GitHub를 올바르게 사용하기 위해서 사용법을 익혀야 합니다. Git은 원래 버전 관리를 위해 탄생한 도구로 개발을 진행하면서 버전별로 이를 로컬 저장소에 저장하고 문제가 있을 때나 수정이 필요할 때 checkout을 할 수 있게 합니다. 이를 Online 으로 업로드하는 서비스가 GitHub입니다. 많은 UI가 있지만 올바르게 모든 기능을 활용하기 위해서는 Git 명령어를 익힐 필요가 있습니다. 0. git init : git을 초기화 합니다. 1. git clone : 원격 저장소에 있는 레포지토리를 다운로드 받습니다. 2. gi..

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