5. 스택과큐
a. 스택 Stack차례대로 삽입하고 최근에 저장된 값을 삭제(FILO) push스택에 값 추가pop가장 나중에 push된 값을 스택에서 제거하고 반환top가장 나중에 push된 값을 제거하지 않고 반환__len__스택의 저장된 요소 갯수를 반환isEmpty스택에 요소가 존재하는지 참거짓 1234567891011121314151617181920212223
Home
4. 해쉬테이블
a. 해시테이블해시 테이블은 일종의 정보를 저장하는 서랍장. a는 2층에 b는 3층에 c는 1층에 넣어두는 방식…b를 보고 싶으면 어떤 서랍에 넣었는지 알아내서, 3층 서랍에 있는 내용 중에 b와 일치하는 것을 찾는 것. 해시테이블은 삽입, 삭제, 검색 연산을 빨리 처리할 수 있다. 만약 순서대로 정보를 서랍장에 넣었을 경우, 어떤 정보를 찾으려 할 때 일
3. 양방향리스트
a. 왜 양방향 연결 리스트가 필요한가?한방향 연결 리스트는 다음 노드를 연결하는 링크만 존재, 이전 노드를 알려면 head부터 다시 탐색을 해야된다… 이런 불필요한 연산을 줄이고자 이전 노드를 연결하는 링크가 있는 양방향 연결 리스트를 구현하고자 한다. 양방향 연결 리스트의 주요 개념은 다음과 같다. 이전 노드로의 링크(prev)를 포함해 이전 노드로 이
2. 배열과리스트
a. 배열(array)데이터를 연속적인 메모리 공간에 저장 주소를 통해 매우 빠르게 접근 배열의 시작 주소, 저장된 값의 종류, 인덱스 세가지 정보로 원하는 값의 주소를 계산 가능. 읽기와 쓰기 연산에 O(1)시간이 걸림 고정된 길이를 가지며, 읽기와 쓰기만 지원하는 경우가 많다. b. 리스트 (파이썬)c의 배열에는 실제 데이터가 저장된 형식이지만, py
7.피보나치
피보나치 수 피보나치 수열이란 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)로 정의되는 수열! 구현 방법 피보나치수 정의를 그대로 재귀함수로 구현 간단하지만..O(g^n) 지수 시간이 걸림..(g는 황금비율 1.1618…) 이차원 배열을 재귀적으로 곱하기 (1 1)(F(n-1)) (1 0
6.Median of Medians 알고리즘
MoM(Median of Medians) 알고리즘퀵셀렉트는 세가지 영역으로 나누는데, 피벗보다 큰 쪽으로 너무 몰리면 수행시간이 길어졌었다. MoM 알고리즘은 피벗을 적절하게 고르는 알고리즘이다.피벗보다 작은 값의 집합 A, 피벗보다 큰 집합 B 둘 다 n/c보다 작도록 피벗을 설정하는 것이다!! 이런 과정으로 피벗을 고른다고 하면, 재귀 과정에서
5.독특한탐색
특수한 선택 문제다음과 같은 요구 조건을 가지느 문제들은 선택(Selection)문제라고 보면 된다. 입력 : n개의 값과 k(1<=k<=n) 값 출력 : k번째로 작은 입력 값 목표 : 비교 횟수 최소화 상한(upper bound) : 어떤 결과를 찾아내는데 항상 임의 횟수의 연산이면 무조건 찾아낼 수 있다.하한(lower
4.일반적인 탐색
일반적인 선택 문제n개의 값중 k 번째 작은 수 찾기 - QuickSelction 배열 중 임의의 수 p를 고른다.(이 p는 pivot) p보다 작은 값을 A에 따로 모으고, p보다 큰 값을 B에 따로 모으고, p와 같은 값을 M에 따로 모은다. 만약 A의 원소가 k보다 작으면 A의 k번째 작은 값이 전체 데이터의 k번째 작은 값이다. 이제 A에서 k보다
3.재귀 알고리즘
재귀 알고리즘재귀 알고리즘 = 알고리즘 내부에서 한번 이상 자신의 함수를 호출sum(n) = 1+2+..+nsum(n) = sum(n-1)+n 123def sum(n): if n==1 : return 1 return sum(n-1) + n 수행시간T(n) = sum(n)의 수행시간이라 할 때T(n) =
2.분할정복법
분할정복법큰 문제를 작은 문제로 분할해 재귀적으로 해결 a와 n 입력받아 a^n 값 구하는 power1(a,n)을 분할 정복법으로 해보자. power1(a, n) = power1(a, n-1)*a 이다. 123def power1(a, n): if n==1: return a return a*power1(a, n-1) power1의 걸리