[프로그래머스] 섬 연결하기 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 costs 리스트를 건설 비용 기준 오름차순 정렬하자 가장 적은 건설 비용으로 모두를 통행할 수 있게 해야 한다. 따라서 다리를 연결할 때 일단 건설 비용이 가장 적은 것부터 고려할 수 있도록 건설 비용을 기준으로 오름차순 정렬해주자. 섬이 어디 섬과 연결되어 있는지 표현하자 (부모 섬) bridges와 room이라는 리스트를 사용했다. bridges는 연결된 부모 섬을 나타내고, ro..
[백준] 1931번 회의실 배정 파이썬 풀이
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 접근 방식 회의 시작 시간과 끝나는 시간이라는 2가지 기준으로 오름차순 정렬하자. 앞 타임 회의가 끝나면 이후 타임 회의가 시작될 수 있기 때문에 우선 시간을 기준으로 정렬해준다. 현재 회의 시작 시간이 이전 회의의 끝나는 시간보다 크거나 같을 때, 현재 회의를 시작할 수 있다. 이전 회의가 끝나는 시간이 end이고 현재 회의 시작 시간이 x일 때, 현재 회의 시작 조건을 코드로 나타내면 if x >= end이다. 현재 회의가 새롭게 시작되었으므로, 회의 개수는 + 1된다. 현재 회의가 이전 회의 시간이 끝..
[백준] 1541번 잃어버린 괄호 파이썬 풀이
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1. 접근 방식 먼저 입력 받은 식을 파싱하자. split()을 사용하면 구분자인 +, -가 사라지기 때문에 for문으로 하나씩 접근해서 파싱한다. 파싱 결과는 후처리가 수월하도록 리스트 형태로 한다. 최소값을 만드는 방법은 덧셈 부분을 최대한 합치는 것이다. 따라서 파싱한 결과를 순회하면서 위 그림과 같은 리스트가 나오도록 덧셈 부분을 모두 더한다. 이후 위 리스트를 식으로 생각하여 계산하..
[백준] 14916번 거스름돈 파이썬 풀이
https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 1. 접근 방식 다이나믹 프로그래밍과 그리디, 2가지 버전으로 접근했다. 다이나믹 프로그래밍 문제를 연습하고자 카테고리를 타고 들어온 문제였기 때문에 dp 테이블을 사용하는 다이나믹 프로그래밍 기법에 맞춰 풀이하고자 노력했다. 이후엔 그리디로도 문제를 해결해보았다. 이 문제는 dp 방식보다 그리디 방식이 더욱 빠르고 간단하다. 그리디로 작성한 코드는 3번에서 확인할 수 있다. 2원과 5원 동전만 거슬러 줄 수 있으므로, dp 테이블의 5번 인덱스까지 미리 초기화해두자. dp 리스트에 1원 ~ 5원을 받았을 때 거슬러..
[백준] 17521번 Byte Coin 파이썬 정답 코드
17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net 1. 문제 내용 2. 접근 방식 최대 수익은 극소값에서 사고, 극대값에서 팔기를 반복하면 된다. 극소값은 함수가 감소에서 증가로 바뀌는 지점이고, 극대값은 증가에서 감소로 바뀌는 지점이다. 코인을 사고 팔 때, 현재 가지고 있는 coin 개수와의 연관 관계 s 리스트를 순환하면서 언제가 극대값이고, 언제가 극소값인지 파악을 하기 위해선 coin 개수를 함께 고려해야 한다. 위 그래프로 예시를 들어보자. 극소값이 4일째인 2라..
[백준] 1246번 온라인 판매 파이썬 정답 코드
1246번: 온라인 판매 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다. www.acmicpc.net 1. 문제 내용 2. 접근 방식 최대 수익은 최대한 가격이 높을수록 발생할 가능성이 높다. 따라서 우선 Pi를 내림차순 정렬한다. 이후 P0 가격 * 1개의 판매 가격과 P1 가격 * 2개의 판매 가격을 비교한다. 이것을 N > M일 경우에는 M번, N m else n for i in range(loop): temp = ps[i] * (i + 1) if profit
[백준] 10610번 30 파이썬 정답 코드
10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 1. 문제 내용 2. 접근 방식 미르코가 만들고 싶어하는 수가 존재하지 않는 경우? 가장 기본적으로 30의 배수는 무조건 일의 자리 숫자가 0이다. 따라서 입력 받은 수에 0이 없다면 무조건 -1이 출력되어야 한다. 입력받은 수의 숫자를 가장 큰 순으로 재배치한 후 30으로 나눈다. 즉, 입력 받은 수가 2104라면 각 숫자는 2, 1, 0, 4이고, 이를 큰 순으로 배치하면 4210이다. 이렇게 새로 구한 숫자가 30의 배수인지 확인한다. 3. 정답 코드 list..
[백준] 19939번 박 터뜨리기 파이썬 정답 코드
19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 1. 문제 내용 2. 접근 방식 나눠 담을 수 없는 경우는 언제인가? 문제를 쪼개서 접근하고자 먼저 답을 도출할 수 없는 상황을 고민하였다. 예를 들어 k = 3이라면, 공은 최소 3 + 2 + 1 = 6개는 있어야 한다. 따라서 k + (k - 1) + (k - 2) + ... + 1보다 n이 작을 때는 정답을 구할 수 없다. 답을 구할 수 있을 때는, 규칙이 무엇인가? n = 10, k = 4 ▶ 1, 2, 3, 4 (3) n = 11, k = 4 ▶..
[백준] 1758번 알바생 강호 파이썬 정답 코드
1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 1. 문제 내용 2. 접근 방식 많은 팁을 주려는 손님을 먼저 받자 많은 팁을 주려는 손님의 등수를 높임으로써 팁에서 마이너스 되는 값을 줄이면 팁의 최대값을 구할 수 있다. 따라서 입력 받은 팁을 내림차순 정렬한 후, 순서대로 손님을 받으면 된다. 3. 정답 코드 import sys input = sys.stdin.readline n = int(input()) data = [int(input()) for _ in range(n)] data.s..
[백준] 11508번 2 + 1 세일 파이썬 정답 코드
11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 1. 문제 내용 2. 접근 방식 최대한 높은 가격을 무료로 지불하자. 세 개로 모은 가격 중에서 가장 적은 가격이, 나머지 제품들보다 비싸면 이득이다. 즉, 입력 받은 제품의 가격을 내림차순 정렬한 후에 3개씩 짝 지으면 된다. 예를 들어 10, 9, 6, 4, 3, 2가 있을 때 (10, 9, 6)과 (4, 3, 2)로 그룹을 나누면, 첫 번째 그룹에서 가장 작은 가격인 6이 두 번째 그룹에 속한 제품의 가격들보다 비싸므로, 구매 비용이 절약된다. 3..