그리디

[python3] 백준 11000 (강의실 배정, 최소힙, 그리디)

1~3시, 2~4시, 3~5시의 강의가 존재할때 최소 몇개의 강의실이 필요한지 구해야한다. 보통 강의실 문제는 그리디로 하나의 강의실이 존재할때 몇개의 수업이 가능한지는 물어보는 문제가 많았던거 같은데 이번에는 강의가 존재할때 몇개의 강의실이 필요한지 구해야한다. 처음에는 갈피를 못잡았다. 그리디 같은 느낌이 들어서 정렬을 해보고 구하려고 했는데 잘 구해지지 않았다. 그래서 알고리즘 분류를 보니 예상도 못한 우선순위 큐가 존재했다. 우선순위 큐를 사용해야한다는 힌트를 보자 바로 풀이가 떠올랐다. 우선 우선순위 큐에 들어가야하는것은 강의실이 될 수 있다. 즉, 해당 강의실을 몇시부터 몇시까지 쓰는 큐가 된다. 처음에는 1-3시에 강의실을 사용할 것이기 때문에 큐에 A(1-3)으로 넣는다. 2-4강의는 A(..

[python3] 백준 1339 풀이 ( 단어 수학, 그리디 )

이 문제는 상당히 헤맸다. 결국 1시간내에 풀지 못해서 질문을 찾다보니 좋은 접근 방법이 있어서 그걸 토대로 푸니 금방 풀렸다. 길이가 최대 8인 문자열이 최대 10개가 주어진다. 각 알파벳은 숫자를 의미하는데 숫자를 대입하여 모든 문자열의 총합을 구하면 된다. 예를 들어 AB + A의 최대값은 98+9 = 117로 나타낼 수 있다. 그럼 간단한 규칙을 찾아낼 수 있다. 1. 가장 앞에 있는 문자열일수록 큰수를 대입해야한다. 2. 많이 나올수록 큰수를 대입해야한다. 그런데 이렇게 정리하면 삽질을 하게 된다. 한마디로 짧게 생각하면 스스로 함정에 빠지는 거다. 그냥 간단하게 AB -> A*10+B*1, B-> B*1 AB+B -> A*10 + B*2 가 된다. 따라서 이걸 그대로 해주면 어떤 값이 가장 크..

[python3] 프로그래머스 섬 연결하기 ( 그리디, MST, 크루스칼, 유니온 파인드)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 처음에는 그래프 알고리즘을 고민했다. 다익스트라,플로이드를 떠올렸지만 이건 목적지가 존재하는 경우에 사용하는 알고리즘이라 사용불가능 했다. 그러다가 가중치를 기준으로 정렬하여 하나씩 포함하면 되지 않을까 했고 visited 배열을 만들어 노드를 체크해주었다. def solution(n, costs): answer = ..

[python3] 프로그래머스 추석트래픽 풀이 ( 그리디 )

이 문제는 접근은 바로 했는데 한 날짜를 계산하는 포인트에서 막혀서 상당히 버벅거리다 다른 풀이를 보고 빠르게 해소되었다. 그래서 다시는 잊지 않고자 이렇게 풀이를 쓴다. 문제를 요약하면 다음과 같다. 로그에 처리시간과 걸린시간이 주어진다. 그렇다면 1초간 얼마나 많은 트래픽을 처리할 수 있는지 확인하고자 한다. 로그는 날짜순으로 오름차순으로 제공된다. 위와 같은 그림을 보면 각 초마다 매번 확인을 하며 로그를 확인해야하는가 싶다. 그렇게 된다면 24시간을 초당 루프를 돌아야하고 더구나 각 로그가 속하는지도 확인을 해야한다. 다행인건 주어지는 로그가 오름차순으로 정렬되어 있다는 점이다. 이를 통해 문제 해결의 실마리를 찾을 수 있다. (각 구간에 속하기만 하면 된다. ) 따라서 로그1이 존재할때 로그 1..

백준 13305 풀이 (주유소, 그리디 알고리즘)

이거 문제를 읽고 어떤방식으로 풀어야 하는지는 바로 알아챘다. 그러나 진짜 진짜 코딩이 왤케 까다로운지 코딩때문에 시간이 오래걸렸다. 노트에는 어떤 로직으로 풀어야하는지 알겠는데 이걸 코딩으로 짜려니 이상하게 안풀렸다ㅋㅋㅋㅋ 문제는 간단하다. 주유소 가격과 거리가 존재할때 언제 주유를 하고 이동을 해야 마지막 거리까지 가장 싼 가격에 도착할 수 있는가를 묻는 문제이다. 그러면 바로 생각할 수 있는것은 i와 i+1을 비교하여 가격이 저렴한곳에서 주유를 하면된다. 그럼 규칙이 만들어진다. 1. i와 i+1의 주유값을 비교한다. i가 비싸면 i+1까지 비용을 지불하고 이동한다. 2. i가 싸다면 다음 거리까지 i에서 지불하고 이동한다. 3. 마지막 도시에 도착하는지 인덱스를 확인하여 연산을 종료한다. n = ..

백준 1541 풀이 (잃어버린 괄호, 그리디)

백준에 단계별로 풀기를 가면 그리디가 DP보다 아래에 있다. 그래서 그리디가 상당히 어려운가보다 했는데.....그리디가 훨씬 쉽다. DP로 고통받았던게 슬퍼졌다. 이번 문제는 +와 -만 존재하는 식을 짰을때 괄호를 이용하여 최솟값을 찾으라는 문제였다. 40-50+30 = 20 이지만 40-(50+30) = -40 으로 만들어 보라는 소리다. 그럼 괄호를 어디에 쳐야하는지 생각해본다. 일단 -만나면 (를 쳐주고 다음 -를 만났을 때 )를 쳐주면 +들을 묶을 수 있다. 그렇다면 결국 중요한것은 +를 묶어주어야한다는 것이다. 따라서 처음 입력받을 때 -마다 짤라주고 안에 존재하는 것들을 합치고 빼면 된다. 설명하려니까 어렵다. 아래의 코드를 보면 쉽게 이해가 된다. l = input().split('-') f..