* 이 게시글은 이지스 퍼블리싱의 를 기반으로 작성되었습니다. 시간 복잡도 : 주어진 문제를 해결하기 위한 연산 횟수. 시간 복잡도 정의하기 시간 복잡도를 정의하는 3가지 유형은 다음과 같다. 빅-오메가 : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법 빅-세타 : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법 빅-오 : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법 1~100 사이의 무작위값을 찾아 출력하는 코드를 수행할 때, 빅 오메가의 시간 복잡도 : 1 빅 세타의 시간 복잡도 : 2/N 빅-오의 시간 복잡도 : N 실제 코딩 테스트에서는 다양한 테스트 케이스를 수행하여 모든 케이스를 통과해야만 합격하기에 항상 최악일 때를 염두해야 한다. 즉, 빅-..
Study
해싱 (hashing) 데이터의 키 값을 간단한 함수를 사용해 변환한 값을 리스트의 인덱스로 사용하여 데이터를 리스트에 저장하는 절차로 공간 낭비를 줄이면서 키 값을 이용한 데이터 검색의 시간 복잡도를 가능하다면 O(1)로 유지하기 위해 사용. 해시 함수 (hash function) : 해싱에 사용되는 함수 해시 값 (hash value) : 해시 함수가 계산한 값 (=해시 주소) 해시 테이블 (hash table) : 데이터가 해시 값에 따라 저장된 구조 해시 함수를 통해 큰 키 공간을 작은 주소 공간으로 변환. python에서는 hash() 함수를 통해 해싱을 진행할 수 있다. 해시 테이블 (hash table) 해시 테이블 ht는 m개의 버킷(bucket) ht[0], ht[1], ht[2], ....
힙 (Heap) 힙은 완전 이진 트리로서 부모 노드 키값의 우선순위가 자식 노드 키 값의 우선순위보다 높은 자료 구조. 힙은 완전 이진 트리의 형태와 노드의 키 값에 대한 힙의 조건을 반드시 유지해야 한다. 완전 이진 트리 : 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리. 힘의 종류 MAX 힙 : 키 값이 큰 항목이 우선순위가 높은 것으로 간주하므로 루트 노드의 키가 가장 큼 MIN 힙 : 키 값이 작은 항목이 우선순위가 높은 것으로 간주하므로 루트 노드의 키가 가장 작음 힙과 우선순위 큐 힙 자료구조는 파이썬에서 우선순위 큐를 구현하기 위해 사용된다. 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 활용 예시 물..
큐(Queue) 한 쪽 끝 위치(Rear)에서 새로운 항목을 삽입(Enqueue)하고, 다른 한 쪽 끝 위치(Front)에서 기존 항목을 삭제 및 반환(Dequeue)하는 논리적 선형 구조 시간 순으로 먼저 삽입된 항목이 먼저 삭제되는 선입선출(FIFO : First-In, First-Out) 구조 Rear(뒤)에서만 삽입이 이루어지고 Front(앞)에서만 삭제가 이루어지는 특수한 리스트. python에서의 큐 python 리스트에서의 구현 enqueue : O(1) (append()) dequeue : O(N) (삭제 후 자리이동) 단순 연결 리스트로 구현 enqueue : O(N) dequeue : O(1) (pop()) 환형 연결 리스트 : enqueue dequeue 모두 O(1) 큐에 적용 가능..
스택(Stack) 한 쪽 끝(Top)에서만 새로운 항목을 삽입(Push)하거나 기존 항목을 삭제 및 반환(Pop)하는 논리적 선형 구조. 시간 순으로 먼저 삽입된 항목이 나중에 삭제되는 후입선출(LIFO : Last-In, First-Out) 구조. Top에서만 삽입, 삭제가 이루어지는 특수한 리스트.(List) python에서의 스택 python 리스트(동적 배열)에 의한 구현 -> push pop 연산 모두 O(1) 단순 연결 리스트에 의한 구현 -> push pop 연산 모두 O(1) 스택에 적용 가능한 주요 연산 Stack() : 빈 스택 생성 push(item) : 기존 Top 다음 위치에 item 삽입 pop() : Top 위치에 존재하는 item 삭제 및 반환 peek() : Top 위치에 ..
선형 회귀 (Linear Regression) 피처와 연속형 결과값 사이의 관계를 설명하는 선형 방정식(선형결합) 혹은 가중치 합의 함수를 찾는 알고리즘. 입력 피처 벡터 x = (x1, x2, ..., xn)가 있고 이에 대응되는 결과값 y가 있을 때, y를 가능한 잘 맞출 수 있는 선형 방정식을 찾는다. 하지만 실제 데이터가 선형 관계로 딱 표현되지 않을수도 있기 때문에 절편(bias)를 추가해준다. 로지스틱 회귀와의 차이점 위와 같은 과정은 동일하지만, 로지스틱 회귀에서는 위에 과정에 추가로 방정식의 결과값을 로지스틱 함수를 통해 0~1 사이로 변환하는 과정이 더 존재했다. cost function MSE (Means Squared Error) 사용. 결과값과 예측값의 차이! 경사 하강법을 통하여 ..
로지스틱 함수 로지스틱 회귀 분류기는 로지스틱 함수(시그모이드 함수)를 사용하는 분류기이다. 로지스틱 함수 (Logistic Function) 시그모이드 함수 (Sigmoid Function) 입력된 값에 0과 1 사이의 값을 할당하는 함수 피처 변환 로지스틱 회귀에서 함수의 입력인 z는 피처 x의 가중합이다. 즉, 입력 피처들이 선형 변환된 값. 주어진 데이터를 선형 변환만으로 완벽하게 목적하는 공간으로 매핑하는 것은 어렵다. 때문에 보통 절편(=bias)를 식에 추가하여 사용한다. 로지스틱 회귀 분류기 로지스틱 함수를 통한 피처 벡터 x의 클래스 판별 로지스틱 함수가 항상 0과 1 사이의 값을 가지기 때문에 y^를 p(y=1|x)로 생각할 수 있다. 즉, 해당 값을 확률 자체로 판단할 수 있다. ex..
의사결정 트리 분류기 (Decision Tree Classifier) 의사결정 트리 분류기는 트리 모양의 순차형 다이어그램을 통해 주어진 데이터를 분류. 트리의 루트부터 시작해서 모든 중간 노드들은 의사 결정 사항 (조건) 트리의 맨 끝에 있는 리프 노드는 의사 결정 사항에 따른 최종 결과 의사결정 트리 분류기의 동작은 의사결정 트리를 생성하는 학습 단계와 생성된 의사결정 트리에 따라 주어진 데이터를 분류하는 분류 단계로 나눠 볼 수 있다. 대표적인 트리 생성 알고리즘 : ID3, C4.5, CART, CHAID 예시 의사결정 트리는 데이터를 재귀적으로 파티셔닝하여 생성. CART (Classification and Regression Tree) 학습데이터를 사용하여 각 노드를 왼쪽 자식 노드와 오른쪽 ..
