Python/자료구조 & 알고리즘7 06. 연결 리스트(Linked List) 연결 리스트 연결 리스트(linked list)는 값과 다음 노드에 대한 포인터가 포함된 노드로 이루어진 선형 리스트이다. 마지막 노드는 Null값을 갖는다. 연결 리스트의 크기는 동적일 수 있다. 삽입 시간복잡도는 O(1)이다. 검색 및 시간복잡도는 O(n)이다. FIFO 연결 리스트 2020. 6. 1. 05. 데크(deque) & 우선순위 큐(priority queue) 데크(deque) 스택과 큐의 결합체로 볼 수 있다. 양쪽 끝에서 항목의 조회, 삽입, 삭제가 가능하다. 우선순위 큐(Priority Queue) Queue와 비슷한 추상 데이터 타입이지만, 각 항목마다 연관된 우선순위가 있다. 두 항목의 우선순위가 같으면 큐의 순서를 따른다. 힙을 이용해 구현한다. 힙(Heap) 각 노드가 하위 노드보다 작은(또는 큰) 이진 트리이다. 균형 트리의 모양이 수정될 때, 다시 균형 트리로 만드는 시간복잡도는 O(log n)이다. 최대 최소값을 구하기 위해 만들어졌다. 최대힙(max heap) 구현하기 우선순위 큐 구현하기 2020. 6. 1. 04. 컬렉션(Collection) 컬렉션(Collection) 컬렉션 자료구조는 데이터를 서로 연관시키지 않고 모아두는 컨테이너(container) 이다. 맨버십 연산자 : in 크기 함수 : len 반복성 set and dictionary Set 반복 가능하다. 가변적이며 중복 요소가 없다. 정렬되지 않는 데이터 타입이다. 즉 인덱스 연산을 할 수 없다. 중복 요소를 제거할 수 있다. 시간복잡도 O(1) 이다. 딕셔너리(dictionary) hash table로 구현되어 있다. 특정 객체에 해당하는 임의의 정수 값을 상수 시간 내에 계산한다. 연습문제 단어 횟수 세기 애너그램 문장 또는 단어의 철자 순서를 바꾸는 놀이 주사위 합계 경로 주사위를 두 번 던져서 합계가 특정 수가 나오는 경우의 수와 경로를 구해보자 단어의 중복 문자 제거 .. 2020. 6. 1. 03. 스택(Stack) & 큐(Queue) 스택(Stack) LIFO(Last in, first out)구조이다. 즉, 배열의 끝에서만 데이터에 접근할 수 있다. 배열 인덱스 접근이 불가하다. 시간복잡도 : O(1)이다. stack의 동작 push : 스택 맨 끝에 항목을 삽입 pop : 스택 맨 끝 항목 반환 및 제거 top/peek : 스택 맨 끝 항목 반환 empty : 비어있는지 확인 size : 스택 크기 확인 스택 구현 1. python list를 활용한 stack 구현 2. Node(객체)의 컨테이너로 Stack 구현 2020. 5. 26. 02. Built-in Sequence Type 파이썬의 내장 시퀀스 타입 내장 시퀀스(sequence) 데이터 타입은 다음과 같은 속성을 갖는다. 맴버십 연산 : in 키워드 사용 가능 크기(size) 함수 : len(seq) 사용 가능 iterability slicing 가변성(mutable) vs 불변성(emutable) 가변형 타입 : 리스트, 바이트 불변형 타입 : 튜플, 문자열, 바이트 배열 얕은 복사(shallow copy) vs 깊은 복사(deep copy) 코드 참조 네임드 튜플(named tuple) 일반 튜플과 비슷한 성능과 특성을 갖지만, 인덱스뿐 아니라 이름으로 참조 가능 tuple과 마찬가지로 immutable 하다. 바이트와 바이트 배열 원시 바이트(raw byte)를 처리하는데 사용할 수 있는 데이터 타입이다. 불변 타입 .. 2020. 5. 12. 01. 숫자 숫자 파이썬에서 정수는 int 이며 immutable 하다. 정수의 크기는 4Byte(32bit)이다. 최대공약수(GCD) 유클리드 호제법을 사용 최소공배수(LCM) 최대공약수를 이용하여 lcm을 구할 수 있다. gcd를 g라고 가정하면 a = ga, b = gb 이다.(단, a, b은 서로소) lcm은 gab 이므로 lcm = a * b / gcd(a, b) 라고 할 수 있다. 피고나치 수열(Fibonacci sequence) 피고나치 수열(fibonacci sequence)은 첫째 및 둘째 항이 1이며, 그 이후의 모든 항은 바로 앞 두항의 합인 수열 1 1 2 3 5 8 13 21 ... find_fibonacci_seq_iter()의 시간복잡도는 O(n)을 갖는다. find_fibonacci_se.. 2020. 5. 8. 00. 시간복잡도 시간복잡도 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것. 알고리즘의 최적화를 위해 필요하다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타낸다. 빅-오 표기법은 계수와 낮은 차수의 항을 제외시켜 간소화한다. 상수 시간(Constant time) 알고리즘이 입력 크기에 구애받지 않는 값에 의해서 한정된다면, 상수 시간이라고 말 할 수 있다. 예를 들어, 단 하나의 연산이 어떤 배열에서의 요소 위치를 알아내는 것을 수행한다고 할 때, 이 요소의 접근하는 것은 상수 시간이 걸린다. 선형 시간(Linear time) T(n) = O(n) 수행시간이 입력 크기에 따라 선형적으로 증가한다. 예를 들어, 리스트의 모든 요소를 더하는 알고리즘.. 2020. 5. 8. 이전 1 다음
