동적 계획법이란? 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 푸는 알고리즘 기법 중 하나입니다. DP는 부분 문제의 결과 값을 저장해놓고 재활용하여 전체 문제를 해결하는 방식으로 동작합니다. 동적 계획법의 조건 DP는 크게 2가지 조건을 만족해야 합니다. 작은 부분 문제들이 반복되어 나타나는 구조여야 합니다. 한 부분 문제에서의 정답이 다른 부분 문제에서의 정답을 결정하는 데 영향을 미쳐서는 안 됩니다. 동적 계획법의 절차 DP 알고리즘은 일반적으로 다음과 같이 세가지 절차를 따릅니다. 주어진 문제를 작은 부분 문제로 분할합니다. 부분 문제의 해결을 위해 이전 단계에서 구한 값을 저장하고 재귀로써 문제를 해결합니다...
파이썬 input 사용방법 파이썬에서 사용자의 입력을 받는 방법은 여러 가지가 있지만, 가장 기본적인 방법은 input 함수를 사용하는 것입니다. input 함수는 키보드로 입력한 값을 문자열로 리턴해주는 함수입니다. 알고리즘 연습을 하게 되면 필수로 알아야 하는 함수라서 정리겸 포스팅합니다. input 함수의 기본 사용법 input 함수는 다음과 같은 형식으로 사용할 수 있습니다. 변수 = input(메시지) 메시지는 생략할 수 있으며, 메시지를 입력하면 프롬프트에 출력됩니다. 예를 들어, 다음 코드는 이름을 입력받아 출력하는 코드입니다. name = input("이름을 입력하세요: ") print("당신의 이름은", name, "입니다.") input 함수로 다른 자료형 입력받기 input 함수로 입..
요즘 알고리즘 공부를 하고 있는데 어찌나 귀찮은지 게으른 생활이 계속되는 것 같습니다. 심심풀이로chatGPT에게 알고리즘 공부를 하는 이유를 물어보았습니다. \ 알고리즘 공부를 해야하는 이유는 무엇인가요? 한글로 해봤더니 확실히 느리고 쓰다 마네요. 타임제한이 있는 것 같습니다. 두번이나 continue를 했습니다. chatgpt는 여러가지 이유가 있지만 큰 맥락은 프로그래밍 스킬향상과 문제해결 능력 향상된다. 문제를 정의하는 기술이 생긴다는 얘기가 주였던 것 같습니다. 알고리즘 공부 하는 방법을 3가지로 요약해주세요 chatgpt에게 알고리즘 공부방법을 3가지로 얘기해달라고 했더니 다음과 같이 3가지로 얘기했습니다. 1. 연습 반복 2.책이나 강의를 통해서 배운다. 3.다른 사람과 협업하고 프로젝트 ..
선택정렬이란? 선택정렬은 아주 단순한 정렬 알고리즘입니다. 최소값을 찾은 후 맨 앞에 데이터와 교체하는 것을 반복하는 방법입니다. 당연히 정리가 끝난 인덱스 이후로 반복해야합니다. 다시 처음부터 하면 안됩니다. 내가 최소값을 선택한 후 그걸 맨 앞으로 끌어오는 작업만 하면 됩니다. 그래서 선택정렬이라고 하는게 아닌가 싶습니다. 출처: https://en.wikipedia.org/wiki/Selection_sort 알고리즘 구현 선택정렬은 최소값을 선택하고 지정한 리스트의 앞의 값이랑 비교를 해야합니다. 맨 앞에 있는 값과 최소값을 비교해 작으면 바꿉니다(swipping) 예를 들어, 데이터가 3개 [16,3,8]라면 처음 한 번 실행할때 [16,3,8]의 최소값인 3과 맨 앞값인 16을 앞으로 넣습니다...
요즘 알고리즘을 공부중인데 로직만으로는 뭔가 답답하네요 ㅜ 알고리즘 진행을 눈으로 보고 싶다는 생각이 굴뚝 같습니다. 그래서 구글링을 해봤더니 있었습니다. 정렬 알고리즘만 확인할 수 있지만 그래도 눈으로 확인할 수 있어서 속이 시원합니다. 물론 위키백과에서 정렬 알고리즘 치면 그림으로 나오긴 하는데 하나씩 봐야하는 단점이 있어서 제가 찾는 건 아니었습니다. 저는 한꺼번에 알고리즘을 보면서 비교해보고 싶었습니다. visualgo 으로 가면 알고리즘 진행과정을 확인할 수가 있습니다. 사이트 바로가기 : https://visualgo.net/en/sorting?slide=6-8 Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - Vi..
알고리즘 이론의 정렬에 대한 내용입니다. 프로그램 작성시 정렬을 세우는 건 아주 중요하고 빈번한 일입니다. 간단한 프로그램을 만들 때는 파이썬 내장 함수로 정렬이 가능하니 큰 필요성을 못 느낄 수 있는데 큰 프로그램을 만들거나 새로운 문제가 나타날 때 정렬 알고리즘을 알고 있지 않으면 역량부족으로 한참 해맬 수도 있습니다. 정렬 알고리즘은 알고리즘 파트 중에서 쉬운 편에 속해서 기초로 알고리즘이라는 분야를 입문하기 좋은 파트이므로 시간을 내서 배워보시는 것을 추천드립니다. 이번 포스팅에서는 버블 정렬에 대해 소개하겠습니다. 버블정렬 정렬은 데이터가 있을 때 이를 정해진 순서대로 나열하는 것을 의미합니다. 손으로 쓰면 너무 쉽겠지만 컴퓨터는 그게 아니라서 알고리즘을 짜서 데이터를 정렬할 수 있게 해주어야 ..
재귀용법이란? 함수 안에서 동일한 함수를 호출하는 방법으로 여러 곳에서 응용되니 익숙해져야 할 용법입니다. 재귀 호출의 동작방식은 함수 내부에서의 스택이라고 볼 수 있는데 함수의 결과값 위에 또 다른 결과값을 얹히는 방식으로 알고리즘이 진행됩니다. 그후에 맨 위에 값부터 리터하고 값을 넘겨줍니다. 얹는 과정을 Call function 결과값을 리턴하는 과정을 Returning values 라 했습니다. 실제 코드가 어떻게 돌아가는지 볼 수 있는 사이트가 있는데 아래 링크로 남겨놓겠습니다. 알고리즘의 진행순서가 어떻게 되는지 살펴보시기 바랍니다. https://pythontutor.com/visualize.html#mode=display 재귀용법의 제한 재귀용법을 무한정 쓸 수 있다면 반복문은 필요하지 않..
해쉬테이블(HashTable)은 주어진 공간에서 값을 저장하게 되면 충돌이 일어나게 됩니다. 이를 처리하는 기법 2가지를 소개합니다. 사실 더 많은 방법이 있는데 어짜피 파이썬에서는 딕셔너리로 다 커버가 되기 때문에 연습용으로 보시면 좋을 것 같습니다. 아래 내용을 보시면 공간의 제약이 거의 없는 딕셔너리의 장점이 얼마나 큰지 느끼실 수 있을겁니다. 참고로 실제 딕셔너리처럼 key값을 잘 정리하지는 않았습니다. 해쉬테이블이 충돌하는 이유 데이터는 많은데 공간은 제약되어있다면 충돌이 일어날 수밖에 없습니다. 예를 들어, 데이터가 만약 9개가 있고 공간이 8개까지밖에 없다면 해쉬테이블의 원리상 무조건 1개 이상은 충돌이 일어날 수밖에 없습니다. 공간을 넓힐 수 있다면 최대한 넓히는 게 좋지만 현실세계는 메모..
파이썬에서는 딕셔너리로 이미 구현이 되어있는 해쉬테이블을 굳이 구현해보겠습니다. 개인적인 이해를 위한 글이니 재미있게(?) 봐주셨으면 합니다. 해쉬테이블(Hash table) 해쉬테이블은 키(Key)에 데이터(Value)를 저장하는 데이터 구조입니다. 나열의 구조인 스택이나 큐와는 다르게 Key를 통해 바로 데이터를 받아올 수 있습니다. 다루기 편하고 검색 속도가 엄청나게 빨라진다는 장점이 있습니다. 파이썬에서는 딕셔너리로 구현이 되어있고 다른 언어는 공간을 확보하고 해쉬테이블을 사용하지만 파이썬은 그럴 필요는 없습니다. 해쉬테이블은 Key-Value의 함수역할을 하는 해싱 함수를 통해 데이터를 반환하는 방식입니다. 즉, 해싱함수를 h라 할 때h(Key)=Value가 됩니다. 함수역할을 하긴 하지만 va..
판다스로 단순 이평선을 구할 때는 판다스 내에 rolling을 이용한 방식으로 구합니다. 그런데 커스텀하게 만든다면 결국 recursive 알고리즘을 쓰게 되어있습니다. 왜냐하면 주식데이터는 시간과 값으로 이루어져 있고 시간에 따른 변화를 분석하는 것이 보통 금융데이터 분석을 하는 목적이기 때문입니다. 결론적으로 Recursive를 써야하니 속도 개선이 필요합니다. 이번 포스팅에서는 판다스를 이용할 때의 속도 개선입니다. Exponentially weighted moving average(EWMA)라는 지수가중평균선을 만들어 분석하는 시간이 얼마나 드는지 확인해보겠습니다. 판다스로 EWMA를 바로 만들 수 있지만 임의로 만들어서 해보겠습니다. EWMA EWMA에 대한 자세한 설명은 나중에 기회가 되면 따..
Recursive algorithm의 경우에 대해 알아보겠습니다. 이전 포스팅에서 numba와 cython을 가지고 속도 개선을 했는데 Recursive algorithm은 통하지 않습니다. 그 이유와 개선 방법에 대해 설명하겠습니다. 참고로 현재 속도개선에 관한 포스팅은 python for finance라는 책을 참고해서 포스팅하고 있습니다. 그런데 책대로 해도 다 되는 건 아니라서 여기저기 참고하면서 블로그에 정리를 하고 있습니다. 이러면서 공부가 되는거겠죠? 아무튼 정리의 목적이 크니 알아두셨으면 합니다. Recursive algorithm 재귀라고 하는 방법입니다. 고등학교 수학시간에 수열에서 배운 점화식을 얘기합니다. 함수를 만들면 만든 함수를 이용해 다음 수를 계산하는 방법입니다. 예로 팩토리..
알고리즘을 구성했을 때 파이썬에서 속도 개선을 위한 시도입니다. 어느 알고리즘을 하느냐에 따라 속도 차이는 있을 수는 있습니다. 알고리즘 이론에서 배우는 복잡한 알고리즘 말고 간단한 알고리즘으로 이전 포스팅에서 얘기한 속도 개선방안 중 어느 것이 효율적인지 확인해보도록 하겠습니다. 알고리즘은 소수 찾는 방법을 만들건데 메르센소수나 페르마 소수 같은 수학 지식이 들어간 방법 말고 소수의 정의대로 알고리즘을 만들어서 시도를 하겠습니다. 소수는 1과 자기자신으로만 나누어지는 숫자를 의미합니다. 예로 2,3,5,7 이런 수가 있습니다. 숫자가 작으면 금방 소수인지를 알아낼 수 있지만 숫자가 커지면 굉장히 어려워집니다. 소수를 찾는 규칙이 따로 존재하면 규칙을 사용하면 되지만 현재로서는 그런 규칙은 부분적으로만 ..
Loop의 퍼포먼스 개선입니다. 순수 파이썬, numpy, numda와 cython으로 평균을 구하는 루프를 만들어 시간 비교를 해보겠습니다. 시간 측정을 위해서 %time 과 %timeit을 쓰려고 합니다. %time은 한 줄의 코드 실행시간을 측정할 때 사용할 수 있고 %timeit은 코드를 여러 번 시도를 한 후 시간 측정을 해서 오차범위를 알려줍니다. Python 파이썬의 내장함수로만 평균을 구해보겠습니다. %time은 코드 한 줄로 해야되니 평균을 구하는 함수를 만들어서 진행을 하겠습니다. import random def average_python(n): s = 0 for i in range(n): s += random.random() return s/n n= 1000000 %time avera..
파이썬은 간결하고 직관적으로 쓸 수 있는 장점이 있는 반면에 굉장히 느린 코드입니다. 루프나 알고리즘을 실행하면 다른 언어에 비해 시간이 오래걸립니다. 간단한 구조는 시간이 얼마 안 걸려서 큰 문제는 없겠지만 알고리즘이 복잡해지고 데이터 크기가 커지면 시간은 굉장히 중요한 요소가 됩니다. 답은 간단하게 속도가 빠른 C 나 C++을 쓰면 되지만 갑자기 C를 배워서 할 수 있는 실정이 안 된다면 파이썬 안에서 개선할 방안을 찾아야 합니다. 개선 방안으로는 다음과 같이 있습니다. Vectorization(벡터화) : 좌표값이나 행렬로 값을 모으는 것을 벡터화라고 합니다. 주로 수학이나 공학에서 쓰는 행렬개념과 비슷합니다. 벡터를 행렬표시로 변환해서 쓰면 행렬 계산으로 넘어가 계산을 하게 되는 건데 그런 학술적..
링크드 리스트를 업그레이드한 더블 링크드 리스트를 살펴보겠습니다. 더블 링크드 리스트는 양방향으로 포인터를 연결한 이중 구조로 이루어져 있습니다. 하나의 데이터당 Prev pointer, Next pointer를 가지게 됩니다. 구조상 양쪽으로 데이터를 연결하게 되어서 양방향으로 탐색하기가 좋습니다. 즉, 탐색이 좀 더 쉬워집니다. 다만, 기본적인 링크드 리스트보다 데이터당 한자리를 더 써야 하므로 좀 더 무겁습니다. 구현도 링크드 리스트보다 좀 더 복잡합니다. 그렇지만 양방향으로 탐색이 가능하다는 장점과 큰 틀로 구현 해놓으면 관리를 할 수 있는 수준이기에 많이 쓰입니다. 달라지는 점은 prev pointer 가 있다는 것이고 그에 따른 코드가 추가된다는 것 빼고는 링크드 리스트와 다를 게 없습니다. ..