본문 바로가기

대딩192

동적계획법(Dynamic Programming) 동적계획법에 대한 이해 피보나치 수열은 첫째항이 0, 둘째항이 1이고 이전 두항을 더해가며 새로운 항의 값을 구해나가는 수열이다. 0, 1, 1, 2, 3, 5, 8, 13 ... 과 같이 이어지며, 점화식은 다음과 같다. F(N) = F(N-1) + F(N-2) (N >= 2) F(0) = 0, F(1) = 1 N번째 항의 값을 구하는 문제는, N-1번째 항을 구하는 문제와 N-2번째 항을 구하는 문제로 나누어질 수 있다. 이렇게 큰 문제를 작은 문제로 나누어 풀 수 있는 경우를 최적 부분 구조(Optimal Structure) 라고 한다. 최적 부분 구조에 대해 자세히 말하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 최적 부분 구조를 가지는 피보나치 수.. 2021. 11. 17.
소수 판별 알고리즘과 에라토스테네스의 체 소수 판별 알고리즘 소수 판별 알고리즘은 시간복잡도에 따라 다르게 구현 가능하다. 시간 복잡도 O(N) 소수란, 약수가 1과 자기자신 뿐인 수를 말한다. 따라서 N이 소수인지 판별하는 가장 쉬운 방법은 2부터 N-1까지의 수로 나누어 떨어지는지 확인하고, 나누어 떨어진다면 소수가 아니라고 판단하는 것이다. bool isPrime(int N) { if (N < 2) return false; for (int i=2; i 2021. 11. 9.
MinMax scaling, Standard scaling 하는 법(with iris data) Scaling 데이터 셋에 키와 몸무게 Feature가 있다고 가정해보자. 키와 몸무게의 평균적인 값들과 단위는 다르기에, 이를 정제 없이 훈련시킨다면 모델의 정확성이 떨어진다. 따라서 데이터 Feature 들의 크기 규모를 동일하게 하는 작업이 필요한데, 이를 Scaling 이라 한다. - Tip💡 이 글에서는 iris 데이터를 이용하여 실습을 진행하고 있다. iris 데이터는 붗꽃 데이터로, 해당 데이터에는 꽃받침의 길이, 꽃받침의 너비, 꽃잎의 길이, 꽃잎의 너비와 꽃의 종류가 기술되어있다. 다운 받고 싶은 분이 계시다면 Kaggle 참조 Iris Species Classify iris plants into three species in this classic dataset www.kaggle.co.. 2021. 11. 1.
Numpy Indexing, Boolean Indexing, Fancy Indexing Numpy Indexing View(reference) 혹은 Copy를 리턴하는 Indexing 방법들에 대해 알아보자. Numpy Indexing Tutorials Indexing & Slicing : view 리턴 리스트의 인덱싱, 슬라이싱과 동일하게 [](bracket) 을 사용하여 부분 배열을 추출한다. - 1차원 배열의 indexing & slicing import numpy as np arr = np.array([1, 2, 3, 4, 5]) print(arr[0]) print(arr[-1]) print(arr[-2]) output: 1 5 4 왼쪽의 인덱스는 0 부터 시작한다. 배열의 맨 뒷부분 부터 접근하기 위해서는 -1 부터 시작하는 음수의 인덱스를 사용하면 된다. Python 리스트에서와.. 2021. 10. 31.
Numpy 배열 생성하기와 형태 변형하기 Numpy numerical python, 행렬과 관련된 연산에 사용하는 python 라이브러리. python 리스트를 이용한 연산보다 빠르며, 메모리를 적게 차지한다. Numpy Tutorials Tip 💡 Numpy 실습은 jupyternotebook에서 하는 것이 가장 편리하다. 아직 jupyter를 설치하지 않은 분이 계시다면 jupyternotebook 배열 생성하기 np.array() 리스트 데이터를 활용하여 array를 생성할 수 있다. import numpy as np ary = np.array([[1, 2, 3], [4, 5, 6]]) ary output: array([[1, 2, 3], [4, 5, 6]]) np.asarray() np.array() 와 동일하게 array를 생성할 수 .. 2021. 10. 30.
[Matplotlb:3.4.3] Matplotlib와 Python으로 시각화 하는법 Matplotlib 파이썬 언어를 이용하여 데이터를 시각화 할 수 있는 대표 라이브러리 데이터 시각화 라이브러리는 matplotlib 이외에도 seaborn, plotly 등 다양하지만, 대부분 matplotlib를 기반으로 개발됨 matplotlib Tutorials Installation - pip command 를 이용한 설치 (기본) python -m pip install -U pip python -m pip install -U matplotlib - Anaconda 사용자 설치 conda install matplotlib - Tip 💡 matplotlib는 jupyternotebook에서 python 언어로 데이터를 시각화할 때 주로 사용된다. 따라서 jupyternotebook을 아직 셋팅 하.. 2021. 10. 30.
[백준 2410번] 2의 멱수의 합 풀이 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 입력으로 주어진 N을 2의 멱수(2^k) 의 조합으로 몇개나 나타낼 수 있는지 구하는 문제이다. 이는 다이나믹 프로그래밍 기법으로 해결할 수 있다. 수를 하나씩 늘려 가능한 2^k 조합을 구해보면, 다음과 같다. N=1 -> 1 N=2 -> 1+1, 2 N=3 -> 1+1+1, 2+1 N=4 -> 1+1+1+1, 2+1+1, 2+2, 4 N=5 -> 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1 ... N이 홀수일 경우를 살펴보면, N-1의 가능한 조합 끝에 1씩을 더해주어 완성된다. N=3 인 경우, N=2 일 때의 조합 (1+.. 2021. 10. 20.
[백준 2251번] 물통 풀이 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 담을 수 있는 부피가 각각 A, B, C 인 물통 3개가 있다. 초기에는 마지막 물통만 가득 차 있으며, 나머지 물통은 비어있다. 한 물통이 가득 차거나 빌 때까지 물을 옮기고, 이를 반복할 수 있다. 처음 물통에 들어있는 양이 0 일 때, 마지막 물통에 들어있을 수 있는 물의 양을 모두 구해야 한다. 가장 쉬운 방법은, 각 물통에 담길 수 있는 물의 양에 대해 모든 경우의 수를 탐색하고, 첫번째 물통이 비었다면 마지막 물통의 양을 저장하는 .. 2021. 10. 18.
[백준 1992번] 쿼드트리 풀이 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 한 변의 길이가 N(N은 2의 배수)이고 0과 1로 이루어진 정사각형이 주어졌을 때, 이를 압축하여 표현하는 문제이다. 압축하는 규칙을 정리해보면 다음과 같다. 1) 모든 요소가 0인 정사각형은 0을 출력한다. 2) 모든 요소가 1인 정사각형은 1을 출력한다. 3) 1과 0이 섞여있는 정사각형은 4등분 하여 ( 왼쪽 위 정사각형 값, 오른쪽 위 정사각형 값, 왼쪽 아래 정사각형 값, 오른쪽 아래 정사각형 값)을 출력한다. 문제에서 제시한 예시에 대해.. 2021. 10. 15.
[백준 1790번] 수 이어 쓰기 2 풀이 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 1 부터 N까지의 수를 이어붙였을 때, K번쨰 자리에 있는 문자를 출력하는 문제이다. 먼저, K번째 자리에 있는 문자를 찾기 위하여 1번 부터 몇번까지의 수를 이어붙여야 하는지 찾아보자. 수의 특성에 따라, 1 ~ 9 까지의 수는 1자리 수들이고 9 * 10^0 = 9 개 이며, 9*10^0 * 1(문자의 자리수) = 9 개의 문자를 표현한다. 10 ~ 99 까지의 수는 2자리 수들이고 9 * 10^1 = 90 개 이며, 9*10^1 * 2(문자의 자리수) = 180 개의 문자를 표현한다. 1.. 2021. 10. 13.

티스토리툴바