코드잇
-
알고리즘: 백준 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개..
-
데이터 사이언스: Pandas 시리즈(Series)와 데이터 프레임(Data Frame) 공부하기!데이터 사이언스 2020. 7. 21. 00:52
Pandas에서 제공하는 라이브러리인 시리즈(Series)와 데이터프레임(DataFrame)을 공부하겠습니다. 판다스에는 일차원 데이터를 위한 시리즈(Series)와 고차원 배열을 다루기 위한 데이터프레임(Data Frame)이 있습니다. 그리고 이 판다스를 통해서 SQL, 엑셀파일, csv파일을 가져와 데이터를 활용할 수 있죠 시리즈는 1차원 배열의 데이터를 다루는 자료구조입니다. 시리즈와 1차원 넘파이(numpy)배열은 유사하지만 판다스에서 더 많은 기능을 제공합니다. 시리즈는 파이썬의 딕셔너리와 유사해서 이와 연관지으면 이해하기 쉽습니다. 예를 들어 딕셔너리에서 key와 value가 있다면 시리즈에서는 index와 data가 있습니다. 다만 시리즈의 경우에는 행렬로 표현..
-
데이터 사이언스: numpy 연산과 통계 값들 구하기(표준편차, 분산, 평균, 중앙값...)데이터 사이언스 2020. 7. 18. 19:45
기존 파이썬 리스트의 연산과는 달리 numpy 배열의 연산은 배열 원소들간의 사칙 연산입니다. 각 위치마다 정해진 값을 따로 연산하기 때문에 numpy배열의 모양(shape)이 다른 경우에는 연산이 되지 않아 오류가 뜹니다. 따라서 numpy배열끼리의 사칙연산을 코딩하기 위해서는 우선적으로 각 배열의 shape을 확인하여야 합니다. import numpy as np x = np.arange(10) y = np.arange(10,20) print(x) print(y) [0 1 2 3 4 5 6 7 8 9] [10 11 12 13 14 15 16 17 18 19] numpy 라이브러리를 추가해주고 리스트 x와 y를 만들어줍시다. x + 2 array([ 2, 3, 4, 5, 6,..
-
데이터 사이언스: Jupyter Notebook! 알아두면 유용한 기본단축키와 Markdown 활용법!데이터 사이언스 2020. 7. 14. 00:16
Ctrl-Enter : run cell (셀 실행) Alt-Enter : run cells and insert below(셀 실행) Shift-Enter : run cells and select below (셀 실행) A : insert cell above (상단에 셀 추가) B : insert cell below (하단에 셀 추가) D,D : delete selected cell (선택된 셀 삭제) X : cut selected cell (셀 잘라내기) C : copy selected cell (셀 복사) Shift-M : merge cell below (하단 셀과 합치기) Shift-V : paste cell above (상단에 붙여넣기) V : p..
-
알고리즘: 예제를 풀어보자! (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)이란? 뜻 그대로 탐욕스런 알고리즘이라고 생각하면 쉽다. 미래를 내다 보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 그리디 알고리즘은 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다. 그래서 보통 최적의 답이 필요 없는 경우에 사용하지만 그리디 알고리즘이 최적의 답을 보장해 주는 문제도 있다. 그리디 알고리즘은 다음과 같은 조건을 만족할때 최적의 답을 보장한다. (다음과 같은 조건이 없어도 그리디 알고리즘을 사용할 수는 있다.) → 최적 부분 구조가 있을 때 문제를 부분 문제로 나누어 해결하여 기존 문제의 답을 찾아낼 수 있는 경우 → 탐욕적 선택 속성을 갖고 있을 때 다이나믹 프로그래밍처럼 답의 모든 부분을 고려하지 않고 탐욕적 ..
-
알고리즘: 다이나믹 프로그래밍(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,..