출처 : 백준, https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 먹을 수 있는 물고기의 위치와 거기까지의 거리를 어떻게 찾을지 생각해야한다. 2. 같은 거리의 물고기 중 위 왼쪽에 위치한 물고기를 찾아야한다. 풀이 import sys from collections import deque KEY_SIZE = 'size' KEY_EAT_FISH = 'eatFish' KEY_POINT = 'point' d..
출처 : 백준, https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net # 같은 곳에 여러 개의 나무가 심어질 수 있다. # 모든 나무는 나이를 한 살 씩만 먹는다. # 새로 추가되는 모든 나무의 나이는 1살이다. # NxN의 격자에 M개의 나무를 심어서 K년 동안 키울 것 # 나무 좌표의 r, c는 1부터 시작 # 모든 칸은 처음에 양분이 5만큼 들어있음 # 봄 # 나무는 땅에서 나이만큼의 양분을 먹고 나이 + 1 # 하나의 칸에 여..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 먼저, 생각해야 할 부분 1. 규칙 찾기 각 행을 내려가면서 행 내의 모든 숫자를 배열에 추가하면 좋겠지만, 그럴 수 있는 규칙은 보이지 않는다.즉, 일일이 구현해야하는데, 달팽이 모양을 따라가면서 쉽게 구현하기 위한 규칙을 찾아보자. 풀이 def solution(n): triangle = [[0 for _ in range(i + 1)] for i in range(n..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # n개의 집에서 i번째 집은 i만큼 떨어져있고 모든 집은 일자로 놓여있음. # 트럭에는 cap개 싣을 수 있다. # 모든 집에 배달/수거해야하는 택배 개수를 알고 있다. # 모든 택배를 보내고 수거하는데 드는 최소 이동 거리 더보기 풀이 def solution(cap, n, deliveries, pickups): answer = 0 while True: while del..
출처 : 백준, https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net # n개의 단어가 있고 k개의 글자를 가르칠 거임 # 모든 단어는 anta로 시작하고, tica로 끝남. # 단어 내의 모든 글자를 알고 있다면 단어를 읽을 수 있음. # 1
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 많이 플레이된 장르순 -> 장르 내에서 가장 많이 플레이된 노래 순으로 2개 수록 # 같은 경우 idx가 작은 것부터 수록 더보기 먼저, 생각해야 할 부분 1. 많이 플레이된 장르 순으로, 장르 내에서 플레이 수가 상위 2개인 노래를 담아야한다. 이를 위해서는 장르별 플레이수, 장르별 플레이 순으로 정렬된 노래가 필요하다. 위 둘을 구하면, 플레이 수가 많은 장르를 가져..
출처 : 백준, https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net # 주어진 끈 들은 동일한 길이로 잘라 목표 개수만큼 만들어야한다. # 길이와 목표 개수가 주어질 때, 목표 개수로 만들 수 있는 잘린 길이의 최대 길이를 구하시오. # 가진 랜선의 개수 1
출처 : 백준, https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 수열 시리즈.... 더보기 먼저, 생각해야 할 부분 1. 습관적으로 dp 배열을 0으로 초기화했는데 과연 0으로 초기화하는게 맞는지 생각해보자. 풀이 def solution(n, num_list): dp = num_list[:] for i in range(n): for j in range(i): if num_list[j]..
출처 : 백준, https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 더보기 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 크면서 최대 길이가 가장 큰 것 dp = [1 for _ in range(n)] for i in range(1, n): # 나보다 작은 idx 중에 # 가장 긴 길이를 찾아서 + 1 for j in range(i):..
출처 : 백준, https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 더보기 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 작으면서 최대 길이가 가장 큰 것 dp_inc = [1 for _ in range(n)] for i in range(1, n): # 나보다 작은 idx 중에 # 가장 긴 길이를 찾아서 + 1 for j in range(i): if num_list[j] < num_list[i]: dp_inc[i] = max(d..
출처 : 백준, https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net # 병사의 전투력 리스트가 주어진다 # 가장 긴 감소하는 부분 수열을 만들 수 있는 열외 병사의 수 더보기 먼저, 생각해야 할 부분 1. 가장 긴 감소하는 부분 수열을 만들 수 있는 병사의 수는 전체 병사의 수에서 가장 긴 감소하는 부분수열의 길이를 빼면 된다. 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 크면서 최대 길이가 가장..
출처 : 백준, https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net # 숫자 리스트가 주어진다 # 가장 긴 증가하는 부분 수열의 길이를 출력 더보기 풀이 def solution(n, num_list): # 이전에 있는 것들 중 나보다 작으면서 최대 길이가 가장 큰 것 dp = [1 for _ in range(n)] for i in range(1, n): # 나보다 작은 ..
