codeit
-
알고리즘: 백준 2217번 로프 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 16:51
백준 2217번 링크입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 로프들이 견딜 수 있는 리스트를 만들어 오름차순으로 배열한다. 만약 10, 25, 30가 로프가 버틸 수 있는 최대중량으로 주어진다면 10 x 3 = 30 25 x 2 = 50 30 x 1 = 30 으로 최대 버틸 수 있는 중량은 50이 된다. ropes[i] * (n - i) 들로 이루어진 리스트의 최대 값을 찾으면 되는 것이다. import sys input ..
-
알고리즘: 백준 1932번 회의실 배정 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 16:22
백준 1932번 링크입니다. https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 최대 사용할 수 있는 회의의 수를 구하기 위해서는 가장 빨리 회의가 끝나는 순으로 회의를 나열한다. 회의의 끝나는 시간을 오름차순으로 배열한 후 전 회의의 시작시간과 다음 회의의 끝나는 시간을 비교하여 리스트를 담는다. 처음에 2차원 리스트의 두번째 요소만 배열하기 위해서 이중 for문을 사용했지만 O(n) = n^2가 되기 때문에 시간초과가 되었다. 그래서 lambda x: x[1]를 key로 받아 sort 함으로써 문제를 해결하였다. import sys input = sys.stdi..
-
알고리즘: 예제를 풀어보자! (feat. 투자의 귀재 규식이)(Brute force, Divide and conquer)알고리즘 2020. 7. 13. 20:04
규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이스북과 인스타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠. 계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max를 작성해 보려고 합니다. 우선 함수 sublist_max는 파라미터로 며칠 동안의 수익이 담겨 있습니다. 예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 날에는 4달러를 벌었고, 마지막 날에는 8달러를 잃은 거죠. 먼저 이 문제를 Brute Force 방법을 이용해서 이 문제를 한 번 풀어봅시다! 1...
-
알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!알고리즘 2020. 7. 13. 13:51
그리디 알고리즘이란(Greedy Algorithm)이란? 뜻 그대로 탐욕스런 알고리즘이라고 생각하면 쉽다. 미래를 내다 보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 그리디 알고리즘은 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다. 그래서 보통 최적의 답이 필요 없는 경우에 사용하지만 그리디 알고리즘이 최적의 답을 보장해 주는 문제도 있다. 그리디 알고리즘은 다음과 같은 조건을 만족할때 최적의 답을 보장한다. (다음과 같은 조건이 없어도 그리디 알고리즘을 사용할 수는 있다.) → 최적 부분 구조가 있을 때 문제를 부분 문제로 나누어 해결하여 기존 문제의 답을 찾아낼 수 있는 경우 → 탐욕적 선택 속성을 갖고 있을 때 다이나믹 프로그래밍처럼 답의 모든 부분을 고려하지 않고 탐욕적 ..