동학 개발 운동

문제 출처 : www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 해석 : 1번 컴퓨터로 부터 바이러스가 퍼진다. 이때 네트워크상에 연결된 모든 컴퓨터가 감연되는데 이 수를 구하는 문제이다. 문제 풀이 : 다양한 방법으로 문제를 풀이할 수 있지만 자신의 부모를 찾는 연산을 통해서 부모 노드가 1인 모든 노드를 찾으면 되기 때문에 부모를 찾는 방법을 사용했다. 다만 입력의 순서 때문에 오류가 발생할 수 있기 때문에 2번의 union 연산을 진행했다. 가능한 다른 ..

문제 출처 : www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해석 : 계단에 적힌 수들을 합하면서 올라간다. 이때 한번에 한 개씩 3개 이상의 계단을 오르지 못하고 2계단을 한번에 이동할 수 있다. 수의 최대값을 구하는 문제이다. 문제 풀이 : 전형적인 DP 문제로 점화식을 도출 할 수 있다. 한번에 3개의 계단을 연속적으로 이동하지 못하기 때문에 1. 이전계단과 자신의 계단 + 3칸 전 최대값 2. 두개 이전의 계단의 최대값 + 자신의 계단 중 가장 큰 값을 구..

문제 출처 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 해석 : 0과 1로 이루어진 배열에서 1은 이동가능한 것을 뜻한다. 여기서 1,1 에서 N,M으로 이동하는 최소 칸 수를 출력하는 문제이다. 문제 풀이 : 전형적인 탐색 문제로 여기서는 BFS를 이용해서 문제를 풀 수 있다. 거리를 기록하는 array와 방문 여부를 체크하는 array 두개를 이용해서 매 순간 가능한 모든 경로를 체크하면서 문제를 해결 할 수 있다. 풀이 코드 from collections import de..

문제 출처 : www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해석 : 0 또는 1로만 이루어진 구역을 찾는 것으로 다른 숫자가 섞여 있다면 이를 4분할 해서 다시 한 번 검사하는 문제이다. 문제 풀이 : 전형적인 분할정복 문제로 재귀적으로 함수를 사용하여 풀 수 있다. 풀이 코드 def check(arr): length = len(arr) first = arr[0][0] for i in range(length): for j in range..

문제 출처 : www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해석 : 유명한 자료구조 중 하나인 최소힙의 사용법 또는 구현을 할 수 있는지 묻는 문제이다. 문제 풀이 : 입력이 자연수일 때는 삽입 연산을, 0일 때는 pop을 해주는 문제이다. Python에서 제공하는 heapq 를 사용하면 간단하게 문제를 풀 수 있다. 가능한 다른 풀이 : Python에서 제공하는 모듈인 heapq를 사용하지 않고 직접 구현하여 만들 수 있다. 풀..

문제 출처 :www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 해석 : 자른 종이의 모든 수가 같은 경우를 -1, 0, 1 케이스로 카운팅하여 출력하는 문제이다. 만약 모든 수가 같지 않으면 다시 종이를 9등분하여 행위를 반복한다. 문제 풀이 : 전형적인 분할 정복 문제로 작은 문제로 부터 큰 문제로 생각하여 풀이를 진행하면 풀 수 있다. 1. 종이의 모든 내용이 같은지 체크한다. 2. 같지 않다면 인덱싱을 통해서 재귀적으로 이를 수행한다. 3..

문제 출처 : www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 해석 : 듣지도, 보지도 못한 사람 이름을 출력하는 문제이다. 문제 풀이 : 두 집합에서 교집합을 찾는 문제로 파이썬의 intersection을 이용하면 풀 수 있다. 풀이 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) answer = [] hear = [] saw = [] for _ in range(N)..

문제 출처 : www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 해석 : 숨바꼭질을 하는데 있어서 x+1, x-1, x*2로 이동하면서 이를 찾는 문제이다. 문제 풀이 : BFS 알고리즘으로 해결 가능하다. 좌표를 찾든 가능한 모든 경우의 방문여부 체크 배열을 만든 후에 3가지 경우에 대해서 계속 해서 검사를 하면서 이동하는 알고리즘을 통해서 문제 해결이 가능하다. 풀이 코드 from collections import deque..

문제 출처 :www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 : 팩토리얼 연산을 한 후에 뒤에서 부터 0이 아닌 갯수를 카운팅 하는 문제이다. 문제 풀이 : 파이썬에서 제공하는 math 모듈을 이용하면 간단하게 indexing을 통해서 문제를 풀 수 있다. 가능한 다른 풀이 : 직접 팩토리얼 연산을 진행하여 문제를 풀어도 무관하다. 풀이 코드 import math N = int(input()) number = str(math.factorial(N)) answer = 0 for i in range(len(number)-1, -1, -1..

문제 출처 : www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 해석 : 고장 리모컨을 가지고 최소 횟수로 원하는 채널로 이동하는 문제이다. 즉 가능한 모든 경우를 계산해서 가장 적게 버튼을 누를 수 있도록 설계해야한다. 문제 풀이 : 이 문제는 가능한 모든 경우를 고려해서 문제를 풀어야 하기 때문에 브루트포스 문제이다. 1. 만들 수 있는 모든 버튼을 만들면서 불가능한 경우를 체크한다. 2. 가능한 경우의 몇번 버튼을 눌러야하는지 계산한..