본문 바로가기

Algorithm/Greedy

 (7)
[Python] 백준 13305번 : 주유소 (S4) - 그리디단계별5 ★ #문제 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net #풀이 & 학습한 내용 "최소 비용으로 주유하여 일직선 도로를 달리는 문제"입니다. 처음에는 주유에 대응되는 도로를 모두 모아서 계산하는 방식으로 문제를 해결했지만, 상당히 비효율적이었고, 그저 도로마다 최소의 기름값을 곱해주어 더해주는 방식으로 변경했습니다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 N = int(input()) roads = list(map(int..
[Python] 백준 1541번 : 잃어버린 괄호 (S2) - 그리디단계별4 #문제 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net #풀이 & 학습한 내용 "식의 값을 가능한 한 작게 만드는 문제"입니다. 그러기 위해서는 -수식을 기준으로 모두 괄호를 묶어주면 됩니다. 따라서 문자열을 split('-')로 나눈뒤에 나눠진 각각의 수식을 eval()함수를 통해 계산하려 했으나, 수가 0으로 시작할 수 있어서 문법오류가 발생했습니다. 따라서 생각을 하다가 -로 나눠진 수식을 다시 +로 나눠준 뒤 형변환(int)을 해서 더해주기로 했..
[Python] 백준 11399번 : ATM (S3) - 그리디단계별3 #문제 www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net #풀이 & 학습한 내용 "기다리는 시간의 합을 최소화하는 문제"입니다. 소요되는 시간이 적을수록 앞에 배치해야 하므로 시간기준 오름차순으로 정렬해주고, 순서대로 합을 구해주면 됩니다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 N = int(input()) total_wait = 0 #각 손님마다 걸리는 시간의 총합 waits = list(map(int,input().split())) waits.sort()..
[Python] 백준 1931번 : 회의실 배정 (S2) - 그리디단계별2 #문제 www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net #풀이 & 학습한 내용 "가능한 한 많은 구간을 선택하는 문제"입니다. 문제를 풀면서 프로그래머스의 단속카메라 문제(supremo7.tistory.com/161?category=873875)와 매우 유사하다고 느꼈습니다. 끝나는 시간 기준으로 오름차순 정렬을 한뒤에 끝나는 시간이 제일 빠른 앞부분부터 순서대로 살펴봐야 한다는 점이 같았습니다. 다만, 단속카메라에서는 끝나는 시간이 같았을 때의 정렬 기준이 상관없었지만, 이번 회의실 배정 문제에서는 끝나는시간이 같았을 때 시작시간 기준으로 오름차순 정렬을 해줘야 했습니다...
[Python] 백준 11047번 : 동전 0 (S1) - 그리디단계별1 #문제 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net #풀이 & 학습한 내용 "동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제"입니다. 큰 단위가 항상 작은 단위의 배수이므로 가장 큰 단위의 동전부터 차례대로 빼주면 됩니다. 만약 이러한 특별한 동전의 조건이 없다면 다이나믹 프로그래밍을 통해 문제를 풀어야 할 것입니다. #소스코드 1 2 3 4 5 6 7 8 9 10..
[Python] TCT: 왕실의 나이트 #문제 이것이 코딩테스트다 P.115 velog.io/@uhan2/%EC%9D%B4%EA%B2%83%EC%9D%B4-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4.Part02.Chapter04-%EC%99%95%EC%8B%A4%EC%9D%98-%EB%82%98%EC%9D%B4%ED%8A%B8-Java [이것이 코딩 테스트다.Part02.Chapter04] - 왕실의 나이트 (Java) todayilearned.Algorithm.solveProblem(왕실의 나이트) velog.io #풀이 & 학습한 내용 파이썬에서 문자를 아스키코드로, 아스키코드를 문자로 바꾸는 ord(), chr()가 있는데, 이 문제에서는 ord()를 활용해서 문제를 해결했습니다...
[Python] 프로그래머스: 단속카메라(Lv. 3) #문제 programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr #풀이 & 학습한 내용 끝나는 지점 순서로 오름차순 정렬을 한 후에, 앞부분부터 살펴보는 Greedy 문제입니다. 우선, 리스트를 sorted()와 lambda함수를 통해서 정렬해줬는데, 이 부분에서 다음 링크를 참고했습니다. velog.io/@aonee/Python-%EC%A0%95%EB%A0%AC-sort-sorted-reverse 이번 문제를 통해 sort와 sorted의 사용방법에 대해 자세히 학습할 수 있었습니다. 정렬 후에는 첫번째 구간의 종료지점을 min으로 설..

티스토리툴바