728x90 Greedy Approach 썸네일형 리스트형 [백준알고리즘] 1541번: 잃어버린 괄호 -Python [백준알고리즘] 1541번: 잃어버린 괄호 -Python https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 단계별로 풀어보기에서 그리디 알고리즘의 마지막 문제이다. 이 문제는 괄호를 '+'와 '-'들 사이에 아무 데나 넣어도 된다는 점이 중요하다. 1+2+3-3+4+5 = 12 이지만 괄호를 다음과 같이 넣으면 결과가 달라진다. 1+2+3-(3+4+5) = -6의 결과가 나온다. 이.. 더보기 [백준알고리즘] 2217번: 로프 -C [백준알고리즘] 2217번: 로프 -C https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net Greedy Algorithm이 DP보다는 역시 생각하기가 쉬운 것 같다. 일단 위 문제를 풀기 위해서.. 더보기 [백준알고리즘] 11399번: ATM -C, Python [백준알고리즘] 11399번: ATM -C, Python https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘의 대표적인 예라고 생각하는 문제이다. 이 문제는 CPU scheduling 기법 중 하나인 SJF(Shortest Job First)을 알고 있다면 쉽게 풀 수 있는 문제이다. 이 문제도 마찬가지로 처리시간이 짧은 순서대로 정렬을 해서 처리를 해주면 된다. 다른 분들은 이 부분을 위해서 시간복잡도가 빠른 퀵 정렬 등을 사용해서 정렬을 해주었지만, 여기서 .. 더보기 [백준알고리즘] 1931번: 회의실배정 -Python [백준알고리즘] 1931번: 회의실배정 -Python https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아랫부분에 새로 푼 방식의 풀이도 추가했다. 이번 문제도 그리디 알고리즘을 이용하는 문제이다. 시작시간과 끝나는 시간이 주어질 때 회의실을 이용할 수 있는 최대 횟수를 찾는 문제이다. 여기서는 문제에 써있는 "단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다." 이 부분이 중요하다. 즉 회의의 시작.. 더보기 이전 1 다음
