[Python/파이썬] 백준 13305번 - 주유소

문제 설명 입출력 예제 풀이 코드 왼쪽에서 제일 오른쪽 도시로 이동하는 최소의 비용을 구하기 위해서는 가장 싼 주유소에서 기름을 넣는 것이 이득이다. 먼저 왼쪽에서 출발할 때는 기름이 없기 때문에 시작지점에서 먼저 기름을 넣고 시작하는데 가장 값이 싼 주유소를 찾기 위해 첫 번 째 주유소를 가장 값이 싼 주유소로 저장해 놓은 뒤 반복문을 통해 저장한 주유소와 현재 위치의 주유소의 기름 값을 비교해 가장 값이 싼 주유소를 갱신해서 기름을 넣으면 된다. 정답 코드 import sys input = sys.stdin.readline n = int(input()) distances = list(map(int, input().split())) oilCosts = list(map(int, input().split(..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2023. 7. 8.
• textsms

[Python/파이썬] 백준 1541 - 잃어버린 괄호

문제 설명 입출력 예제 풀이 코드 그리디 알고리즘 문제로 괄호를 적절히 합쳐서 최소 값이 나올 수 있게 하는 방법만 알면 쉽게 해결할 수 있다. 해당 방법는 모든 + 식들만 먼저 더하고 나중에 구한 값들을 첫 번째 값에서 부터 빼는 방식이다. 이때, 첫 번째 값은 등호가 없으므로 따로 저장하여 처리한다. 만약 10 - 20 + 30 - 60 + 20 - 40 이 주어졌다고 가정해보자. 가장 최소 값이 나올 수 있도록 덧셈 식들만 괄호를 적용하면 다음과 같다. (10) - (20 + 30) - (60 + 20) - (40) 이 식대로 계산을 하면 정답은 10 - 50 - 80 - 40 = -160이 된다. 정답 코드 import sys input = sys.stdin.readline arr = input(..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2023. 6. 29.
• textsms

[Python/파이썬] 백준 1931 - 회의실 배정

문제 설명 입출력 예제 풀이 코드 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 앞의 일이 종료되어야 뒤의 일도 진행할 수 있는 것과 마찬가지로 회의가 빨리 끝날수록 뒤에서 더 많은 회의가 가능하다. 정렬을 하는데 끝나는 시간이 오름차순으로 정렬되었을 경우 시작시간은 같지만 끝나는 시간이 같은 회의가 생길 수가 있다. 이 경우를 대비하여 첫 번째로 끝나는 시간 기준 오름차순, 두 번째로 시작하는 시간 기준 오름차순 으로 총 2번의 정렬이 필요하다. 위의 정렬을 해주기 위해서는 위 순서대로 sort를 하는것이 아니라 반대로 해야한다. 즉, 시작시간의 오름차순으로 정렬을 한 뒤, 정렬된 리스트를 다시 끝나는 시간으로 오름차순 정렬해주는 것이다. 이미 시작시간이 오름차순으..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2023. 6. 28.
• textsms

[알고리즘] 그리디 알고리즘(탐욕법)

Greedy(탐욕) 알고리즘이란 ? Greedy를 번역하면 "탐욕스러운"이라는 뜻을 가집니다. 그리디 알고리즘은 탐욕이란 뜻처럼 현재 상황에서 최적의 해만을 선택합니다. 그리디는 현재 상황의 최적의 해를 구하는다는 것에 중점을 두어야하는데, 그 이유는 다음 그림을 봅시다. 가장 큰수를 찾기 위해 앞으로 간다면 제일 큰 수가 있는 "1000"과 연결되어 있는 100 -> 1000 을 생각할 것입니다. 하지만 Greedy 알고리즘은 시작부터 두 수중 가장 큰 수인 "500"을 탐색하고 그 다음 큰 수인 "200"을 탐색합니다. 이 처럼 그리드는 최종결과에서의 최적의 해가 아닌 "현재상황에서 최적의 해"를 구합니다. 그리디 알고리즘 적용 조건 1. 탐욕스러운 선택 조건 앞의 선택이 이후의 선택에 영향을 주지 ..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 19.
• textsms