A seeker after truth

아래 두 코드는 흔하고 유명한 알고리즘 문제 2개를 재귀로 풀어본 예다. 1. palindrome def palindrome(string): if len(strung) Asia > Korea > Asia Regional - Taejon 2001] 문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오 힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면, f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기 강의자료에 있는 문제 분석 내용을 반드시!!..

* 본문은 (박선주, 영진닷컴)의 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..