전체 글

관련 학습 포인트: 분할정복, 재귀 Divide and Conquer 학습포인트 Divide and Conquer 알고리즘 : merge sort / quick sort persucode template? 분할과 정복 타입의 알고리즘의 시간복잡도를 측정하기 위한 master theorem 분할과 정복 들어가기 개념 같거나 연관된 타입의 2개 이상의 하위문제로 문제를 쪼개는(분할, divide) 기법. 어디까지 쪼개냐 하면, 바로 충분히 간단하게 직접 해결할 수 있을 때까지 쪼개어 계산(정복, conquer)하고, 최종결론을 형성하기위해 하위문제의 결과와 결합한다. Divide: 문제 S를 하위문자의 집합으로 나눈다. Conquer: 각각의 문제를 재귀적으로 푼다. Combine/merged: 각각의 하위..

학습한 사이트 https://leetcode.com/explore/learn/card/sorting 정렬의 기초 Inversion: 순서관계에서 벗어나 있는 한 쌍의 요소들 stability : 동일한 요소의 순서를 보장하는 특징 컴퓨터 과학의 정렬=정렬/순서 관계ordering relation이며, 이는 두가지 필수 속성들을 갖고 있어야 한다. ( **Law of Trichotomy, Law of Transitivity** ) If a b 정렬은 순서관계에 기반해서 비순서관계의 요소들을 다시 일련의 순서가 있는 요소들로 재배치하는 것. Inversion..

BigO 알고리즘의 증가 추세로 표시하는 시간 복잡도 표기 방법 2n^2도, 3n^2도 O(n2)로 같다. loop를 한번 쓰면 최악의 경우 모든 계산을 한다. 즉 n번을 계산하게 되므로 루프 시 n*n⇒ n^2가 된다. Big O -upper bound Big Omega - lower bound Big Theta - Tight bound 어떤 경우? 최악의 경우 최선의 경우 ≤ ≥ == 알고리즘의 성장 속도 특정 값보다 작거나 같음 특정 값보다 크거나 같음 특정 값과 같 무엇을 표시? 알고리즘의 상한을 표시 알고리즘의 하한을 표시 상한과 하한의 The bounding of function 을 표시 asymptotic bound(점근적 결합) asymptotic upper bound를 제공 asympto..

🧾 1과 자신 이외의 자연수로는 나눌 수 없는 자연수 1은 소수가 아니다. 소수의 성질을 이용하여 소수를 판별한다. 소수 판별 문제 유형 소수 판별이 필요한 문제 유형은 크게 두가지로 보인다. 소수를 반별 특정 범위 내에서 소수를 찾아 반환하기 소수 판별 (True/False) N을 이용하기 2부터 n-1까지 나누기 def isPrimeNum(n): for i in range(2,n): #2~n-1까지의 모든 수를 나누어 확인 if n%i==0: return False return True 시간복잡도 : O(n) n이 1,000,000(백만)일 때 2~999,999의 모든 수를 하나씩 나누기 때문에 비효율적이다. n/2 까지 나누기 def isPrimeNum(n): ref=int(n/2)+1 for i ..

반복: 어떤 조건이 성립하는 동안 반복해서 처리하는 구조를 반복 구조(repetition structure)라 하고 Loop라고도 한다. loop : while과 for while 조건식이 참일 동안 명령문이 반복되다가 false가 뜨는 순간 반복 종료 실행하기 전에 반복을 계속할 것인지 판단한다. (사전 판단 반복 구조) while ( condition) { statements; //body of the loop } for for(initialization; condition; iteration){ //body of the 'for' loop } while vs for While for 언제 사용하나? 반복 횟수(umber of iterations)가 정해지지 않을 때 반복의 횟수를 이미 알고 있을 때..

학습 사이트 https://leetcode.com/explore/learn/card/array-and-string/ https://www.algolist.net/Data_structures/Array 두 사이트 모두 c++과 java 위주로, 두 언어를 비교하며 설명하였다. 주요 키워드 배열 vs 동적배열 (dynamic array) 배열과 동적배열의 기본 연산자(basic operation) 다차원배열(multidimensional arrays) 이해와 이차원배열 이해 문자열string의 이해와 문자가 가진 다른 특징들? 투 포인터 기술 two-pointer technique 배열 순차적으로 요소들의 집합을 보관하기 위한 데이터 구조. (An array is a basic data structure t..