알고리즘
-
알고리즘: 백준 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..
-
알고리즘: 백준 1149번 RGB거리 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 21. 14:43
최적 부분구조와 중복되는 부분이 있으므로 다이나믹 프로그래밍으로 풀어줍니다. 점화식: 1. n번째 집에서 R을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 G을 칠할 때 비용의 최솟값, n - 1 번째 집에서 B을 칠할 때 비용의 최솟값 ) + n 번째 R을 칠하는데 드는 비용 2. n번째 집에서 G을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 R을 칠할 때 비용의 최솟값, n - 1 번째 집에서 B을 칠할 때 비용의 최솟값 ) + n 번째 G을 칠하는데 드는 비용 3. n번째 집에서 B을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 R을 칠할 때 비용의 최솟값, n - 1 번째 집에서 G을 칠할 때 비용의 최솟값 ) + n 번째 B을 칠하는데 드는 비용 n개..
-
알고리즘: 예제를 풀어보자! (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...
-
알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)알고리즘 2020. 7. 10. 19:34
다이나믹 프로그래밍(Dynamic Programming)이란? 다이나믹 프로그래밍은 부분 문제들의 답을 중복되지 않게 최적의 방법으로 구하고 이를 통해 기존의 답을 구하는 방식이다. 정리하자면 어떤 한 문제가 최적부분구조와 중복되는 부분 문제가 있을 때 동적 프로그래밍을 사용하면 효율적이다. (두 조건을 만족하지 않아도 다이나믹 프로그래밍을 할 수 있다.) → 최적부분구조(Optimal substructure) 어떤 문제가 최적 부분구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해서 기존 문제의 최적의 답을 구할 수 있다. 예를 들면, 최단경로를 찾는 문제가 있다. → 중복되는 부분 문제(Overlapping subproblems) 주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들..
-
알고리즘: 분할 정복(Divide And Conquer) 예제 공부하기! (합병 정렬, 퀵 정렬)알고리즘 2020. 7. 10. 17:39
분할 정복(Divide and conquer)이란? 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식. 분할 정복은 다음과 같은 절차를 거친다. 1. Divide 2개 이상의 작은 문제들로 쪼갠다. 2. Conquer 나누어진 작은 문제들을 푼다. 3. Combine 나누어 해결한 문제들을 합친다. 1. 1부터 n까지의 합 (1 + 2 + 3 + ... + n) def consecutive_sum(start, end): if start == end: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid + 1,..
-
알고리즘: 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)알고리즘 2020. 7. 1. 21:53
1. 시간 복잡도란? 시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력함수의 관계를 나타내는 것입니다. 쉽게 말해서 문제 해결에 시간이 얼마나 걸리냐? 를 정량적으로 나타낸것입니다. 그래서 보통 시간 복잡도가 적은 알고리즘을 빠른 알고리즘 시간 복잡도가 큰 알고리즘을 느린 알고리즘이라고 합니다. 알고리즘의 시간복잡도 표기법은 점근표기법(Big-O)을 통해서 나타내는데 오늘 여러가지 경우의 시간 복잡도과 공간 복잡도를 알아보겠습니다. 주로 O(1), O(lgn), O(n), O(nlgn), O(n2^2), O(n^3) 정도가 많이 사용되고, 나머지는 흔치 않습니다. def my_print(my_list): print(my_list) my_print([2, 3]) my_print([2..
-
알고리즘: 선형탐색 알고리즘(Linear search algorithm)과 이진탐색 알고리즘(binary search algorithm)알고리즘 2020. 7. 1. 15:26
탐색 알고리즘이란 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘입니다. 여러가지 탐색 알고리즘이 있지만 대표적으로 선형탐색 알고리즘과 이진탐색 알고리즘에 대해서 공부하겠습니다. 두 알고리즘 다 정렬되어있다는 가정하에 알아보겠습니다. 1. 선형탐색 알고리즘(Linear search algorithm) 순서대로 하나씩 값을 찾아보는 알고리즘입니다. 원하는 값을 발견하면 더이상 탐색하지 않습니다. def linear_search(element, some_list): # some_list의 안에 element가 있으면 인덱스를 리턴 for i in range(0, len(some_list)): if some_list[i] == element: return i # 왼쪽 값부터 시작해서 하나씩 비교..