동학 개발 운동

문제 출처 : leetcode.com/problems/valid-palindrome/ Valid Palindrome - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 : 입력된 문자열이 뒤집어도 같은 문자열인지 판별하는 문제이다. 문제 풀이 : 이 문제에서는 숫자, 알파벳만 고려한다고 하였기 때문에 전처리후에 뒤집어서 같은지 비교하면 된다. 가능한 다른 풀이 : 리스트를 이용한 풀이 풀이 코드 class Solution: def isPalindrome..

문제 출처 : www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 해석 : 두 팀으로 나누어서 능력치 차이를 최소로 하게 팀을 구성하는 문제이다. 문제 풀이 : 처음에는 itertools의 permutations를 이용해서 풀려고 했지만 메모리초과가 나와서 직접 팀을 구성하고 이를 계산해서 풀었다. 풀이에 필요한 기능은 1. 팀을 구성하는 함수 2. 팀의 능력치 차이를 계산하는 함수 가 있으며 이를 활용해서 바로 풀어 낼 수 있다. 풀이 코드 def cal_diff(team1,..

문제 출처 : 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초로 이동하는 것이 가장 우선 체크 되어야 하기 때문에 항상 가장 처음에 위치 시킨다. 또한 무한 루프를 방..