[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

[Java/자바] 프로그래머스 Lv2 - 조이스틱 (Greedy/탐욕법)

문제 설명 Solution.java 정답 코드 class Solution { public int solution(String name) { int answer = 0; // 조이스틱 조작 횟수 int len = name.length(); int move = name.length() - 1; // 기본 최소 좌우이동 횟수 (좌, 우 커서) // 해당 커서 알파벳 변경 최솟값 (위, 아래 커서) for (int i = 0; i < len; i++) { answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1); // 연속된 'A'가 끝나는 지점 찾기 int next = i + 1; while(next < len && name.charAt(next)..

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

[Java/자바] 프로그래머스 Lv2 - 구명보트 (greedy 탐욕법)

문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.s 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세..

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

[Java/자바] 프로그래머스 - 체육복/Greedy(탐욕법) 알고리즘

문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2022. 11. 30.
• textsms