동학 개발 운동

문제 출처 : www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 해석 : 로봇 청소기가 특정한 조건을 만족하면서 청소를 진행한다. 이때 청소가 완료된 횟수를 출력하는 문제이다. 문제 풀이 : 주어진 문제의 조건을 하나씩 차근차근 따져가면서 풀면 해결할 수 있다. 풀이 코드 from collections import deque dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def solution(): global arr result ..

문제 출처 : www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 해석 : 공기청정기는 여러 규칙에 따라서 움직인다. 이를 수행했을 때 T초 후의 총 먼지의 양을 구하라 문제 풀이 : 주어진 요구사항을 차근차근 하나씩 확인해 가면서 구현하면 풀 수 있다. 풀이 코드 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def check_all(): temp = 0 for i in range(R): temp += sum(arr[i]) retu..

문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 해석 : A에서 B로 만드는데 2가지 방법을 사용할 수 있다. 1. 수를 2배로 만든다. 2. 수의 끝에 1을 붙인다. 이때 최소 횟수로 B를 만드는 것에 +1 한 수를 반환해라, 만들 수 없다면 -1을 반환해라. 문제 풀이 : BFS로 가능한 모든 경우의 수를 체크하면 되는 문제이다. 풀이 코드 from collections import deque def find_answer(A): visited = [] Q = deque() Q.append([0,A]) visited.append(A) while Q: count,..

문제 출처 : www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : N개의 자연수 중에서 M개를 선택하여 수열을 생성한다. 이때 N에는 중복된 수가 들어 있을 수 있으며 수열은 서로 중복되서는 안되고, 수열 속에서 같은 수가 중복 되어도 된다. 문제 풀이 : 재귀적으로 답을 만들어가고 이미 출력된 적이 있다면 이를 제외 해주면 된다. 풀이 코드 def make_answer(start, count, arr2): global candidate if ..

문제 출처 : www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : N개의 수 중에서 M개를 고르는데 중복 없이 결과를 출력해야한다. 이때 N은 중복된 수가 들어있다. 문제 풀이 : permutations과 set을 활용해서 문제를 풀 수 있다. 풀이 코드 from itertools import permutations N, M = map(int, input().split()) num_list = list(map(int, input().split()..

문제 출처 : www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해석 : N개의 수 중에서 M개의 수를 고른다. 이때 자기 자신도 고를 수 있지만 중복은 없다. 또한 비내림차순이다. 문제 풀이 : 재귀적으로 풀어가면서 시작 index를 주면 된다. 풀이 코드 def make_answer(start, count, arr2): if count >= M: for element in arr2: print(element, end = " ") print()..

문제 출처 : www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 해석 : 일정한 거리를 탐색할 수 있다. 이때 가장 많은 아이템을 습득하기 위해서는 어디에 떨어져야 하는지는 구하는 문제이다. 문제 풀이 : 1. 워셜 플루이드 알고리즘을 통해서 모든 경로의 최소 거리를 구하여 계산 할 수 있다. 풀이 코드 INF = int(1e9) N, M, R = map(int, input().split()) area_item = list(map(int, input().spl..

문제 출처 : www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 해석 : N에서 K로 이동하는 방법에는 3가지가 있다. X-1, X+1, X *2 이 때 X*2로 이동할 때는 0초가 걸리고 나머지는 1초가 걸린다. 최소 이동 시간을 구하는 문제이다. 문제 풀이 : BFS로 모든 경우를 체크하면서 푼다. 다만 이때 0초로 이동하는 것이 가장 우선 체크 되어야 하기 때문에 항상 가장 처음에 위치 시킨다. 또한 무한 루프를 방..

문제 출처 : www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해석 : 배낭에 최대한의 가치를 가지도록 물건을 채워넣어서 여행을 갈려고 한다. 이때 배낭의 최대무게까지 들고 갈 수 있는 물건의 최대 가치를 구하라 문제 풀이 : 배낭 정리 알고리즘을 이용해서 풀이할 수 있다. 풀이 코드 import sys input = sys.stdin.readline N, K = map(int, inpu..

문제 출처 : www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해석 : 숨바꼭질을 하는데 이동 가능한 경우는 X-1, X+1, X*2이다. 이때 가장 빠르게 K로 이동할 수 있는 경우의 수와 그 시간을 구하는 문제이다. 문제 풀이 : BFS를 통해서 모든 경우를 조사하면서 횟수를 검사하면 풀 수 있다. 풀이 코드 from collections import deque def search(N): visited = [[-..