[프로그래머스] 섬 연결하기 파이썬 풀이
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원을 받았을 때 거슬러..