동학 개발 운동

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

문제 출처 :www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 해석 : 사람들끼리 몇 다리를 거치면 알고 있는가를 구하는 문제입니다. 즉 그래프로 생각했을 때 이동할 수 있는 경로, 간선 들이 존재하는지 그리고 그 길이가 얼마인지를 계산하는 문제입니다. 문제 풀이 : 모든 사람들에 대해서 계산을 해야하므로 플로이드 - 워셜 알고리즘을 사용하면 풀 수 있습니다. 플로이드 - 워셜 알고리즘은 for k in r..

문제 출처 :www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해석 : 큐와 스택을 이용해서 방문하는 노드를 순서대로 출력하는 문제이다. 기본적인 조회이므로 자신이 원하는 구조로 자료를 정리한 다음 방문처리 해주면 된다. 문제 풀이 : 각각 노드에서 이동가능한 노드를 표시하는 graph를 선언하고 방문 된 적이 있는지 체크하는 visited 를 이용해서 방문 처리를 실행한다. 여기서 주의할 점은 낮은 번호 순서로 방문..

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

문제 출처 :www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해석 : 치킨 거리는 가장 가까운 치킨 집까지의 거리를 의미합니다. 이 문제에서는 도시 전체의 치킨 거리를 최소가 되게 하면서 치킨 집을 일정 숫자만큼 폐업 시켜야합니다. 문제 풀이 : 구현 문제 입니다. 가능한 모든 경우를 고려하여 치킨 집을 정해진 갯수만큼 배치하고 거리를 계산하여 최솟값을 찾아야합니다. 풀이 코드 from itertools import combinat..

문제 출처 : www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해석 : 뱀이 사과를 먹으면 몸의 길이가 늘어나며 경로를 따라 움직입니다. 자신의 몸이나 벽에 부딪히면 게임이 끝나며 이때 시간을 출력합니다. 문제 풀이 : 구현 문제로서 문제에서 제시하는 조건들을 모두 만족시키게 차근차근 풀이를 진행하면 풀 수 있습니다. 풀이 코드 N = int(input()) K = int(input()) board = [[0] * N for _ in range(N)] for ..