A seeker after truth

* 본문은 (박선주, 영진닷컴)의 1-2장을 읽고 필요한 부분 일부를 메모한 내용에 패스트캠퍼스 강의 내용을 보충한 글입니다. 1. O표기법 안에 들어가는 N은 처리해야 할 데이터의 양. - O(log_2 n): 처리할 데이터 양 증가할수록 실행 시간도 약간씩 증가. 그러나 증가폭이 완만하단 것 알지? 일반적으로 효율이 좋은 검색 알고리즘의 성능이 이에 해당. - O(N): 데이터 양&실행시간 비례 - O(NlogN): 처리해야 할 데이터 양에 비해 정비례보다 약간 더 증가하는 실행 시간 갖게 됨. 일반적으로 효율이 좋은 정렬 알고리즘의 성능이 여기 해당. - O(N^2): 2의 n승까지 있는데 이하 생략. ⭐️여기서! 반복문이 1개면 O(n), 2개면 O(n^2),... 등인 걸 알고있을텐데, vari..

((굉장히 유익한 내용이었다. https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0

*본문은 (성균관대학교 출판부, 2017)을 참고하여 작성되었습니다. 그디리 알고리즘이란 단어 뜻 그대로 '탐욕적' 문제해결 방법에 해당한다. 즉, 주어진 문제 상황에서 최선의 답을 선택하는 방식으로, 선택할 때마다 가장 좋은 방법을 선택하여 답을 찾아가는 것이다. 그러나 이 알고리즘은 데이터 간의 관계를 고려하지 않고 매 순간마다 최선의 선택을 적용하기 때문에 근시안적으로 의사 결정을 내리는 문제 해결 방안이다. 그리디 알고리즘은 전체 문제에 대한 완벽한 최적의 해결책을 보장하지 못하는 특성 때문에 다음과 같은 특정 문제 해결에 적용하는 것이 가능하다. 현재 단계의 선택이 다음 선택에 전혀 무관하며, 매 단계 선택된 최적의 해결 방안이 전체 문제해결의 최적화로 이어지는 경우에 적합한 알고리즘이다. 이 ..

*본문은 (성균관대학교 출판부, 2017)와 사이트(https://wayhome25.github.io/cs/2017/04/15/cs-16/), 패스트캠퍼스 알고리즘 강의를 참고하여 작성되었습니다. 1. 정의와 예시 •동적 계획법: 가장 작은 문제부터 상향식으로 해결해 나가는데, 이 작은 문제가 중간~상위 문제와 중복되는 내용이며 이 작은 것을 위로 올라갈 때까지 계속 합쳐 나간다. •분할 정복: 주어진 문제를 더 이상 분할할 수 없는 단위까지 계속 분할하여 부분 문제를 해결할 수 있는 해를 찾는 것. 동적 계획법과 차이점은, 가장 하위의 문제가 중간 및 상위 문제와 내용이 중복되지 않고 하향식 접근법(상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식)이다. 일반적으로 재귀함수로 구현..

*본문은 (성균관대학교 출판부, 2017)을 참고하여 작성하였습니다. 무식하게 다 해보는 것을 의미함. 일반적으로 알고리즘은 문제 해결을 위한 전략을 제시하는데, 하드웨어 발달로 인해 컴퓨터의 빠른 계산 능력이 지원된다는 것을 감안하면 가능한 경우의 수를 일일이 계산하여 답을 찾는 것도 하나의 전략이다. 이를 완전 탐색(exhaustie search) 혹은 Brute Force라 함. 주어진 문제를 완전 탐색으로 해결하는 과정을 이해하기 위해선 재귀함수 개념을 적용해야 한다. 재귀함수는 주어진 문제를 작은 문제로 쪼개어 해결한 뒤 원래 문제를 해결하는 방식이다. 1. 버블 정렬(bubble sort) def bubbleSort(dataList): for checkrange in range(len(data..

*본문은 (성균관대학교 출판부, 2017)을 참고하여 작성하였습니다. 1. 개요 선택,삽입,버블 빠른,합병,쉘 정렬 등 존재. 앞 3개는 단순&비효율, 뒤 3개는 복잡&효율. 알고리즘 선택 기준은 1)자료의 양 2)사용 가능한 메모리 크기 3)정렬 위한 자료 이동 빈도 수 1)이 적으면 앞 3개를 주로 선택하고, 많으면 뒤 3개 선택하지만, 메모리 크기가 작으면 이들 중 메모리 적게 먹는 알고를 선택할 수밖에 없다. 효율성의 기준은 3번, 즉 이동 빈도 수고 이게 바로 빅오로 연결되는 것. 빅오를 계산하여 알고 효율성을 검토하는 것을 '시간 복잡도'라고 한다. 2. 선택 정렬(selection sort) def selection_sort(arr): for i in range(len(arr)-1): min..