동학 개발 운동

문제 출처 : 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/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 해석 : 포켓몬의 이름이 순서대로 입력되고 그 순서가 포켓몬의 번호가 된다. 그 다음 입력으로 들어오는 수 또는 이름을 토대로 매칭되는 답을 하면 되는 문제이다. 문제 풀이 : 단순하게 배열로 문제를 탐색하여 풀게 되면 시간 초과가 난다. 따라서 딕셔너리를 이용한 풀이가 가능하다. -> 두 개의 딕셔너리를 생성해 하나는 key를 이름으로 또 다른 하나는 key를 ..

문제 출처 : www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 해석 : 행성 터널을 건설하는데 N개 행성에 대해서 N-1개의 터널을 최소 비용으로 구하는 문제이다. 문제 풀이 : 모든 경로를 생성하고 문제를 풀이하고자 한다면 메모리 초과 또는 시간 복잡도에서 초과가 날 것이다. 따라서 x,y,z에 대해서 정렬을 실행하고 각각 사이의 거리를 저장한 다음 이를 간선으로 취급해서 MST를 실행하면 된다. -> 중복 되는 경우를..

문제 출처 :www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해석 : 계산의 우선순위를 변경하여 가장 작은 값을 결과로 가지도록 하는 문제이다. 즉 최대한 큰 수로서 - 연산을 진행하도록 하는 것이다. 문제 풀이 : 입력되는 문자열을 파싱하는 것을 시작으로 "-"를 기준으로 나누어 최대값으로 생성하고 그 뒤에 "-" 연산을 진행하게 되면 가장 작게 만들 수 있다. 가능한 다른 풀이 : 모든 경우를 생각해볼 수 있지만 비효율적일 수 있다. (ex, ..