Python 문법 정복하기 썸네일형 리스트형 [Python] Max Heap Max Heap(최대 힙)의 삽입 알고리즘과 시간복잡도에 대해 공부해 봅니다. Heap은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 항상 최대/최소의 값들이 필요한 연산이 있다면? 바로 힙을 쓰면 된다. 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조로, 다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다. 그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가게되고, 그래서 최대의 값들을 빠르게 구할 수 있게 된다. 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아니다! 8 Level 0 6 3 Leve.. 더보기 [Python] Tree 트리는 이름처럼 계층형 구조로 위 아래가 구분되어 있습니다. 앞서 공부한 큐(Queue), 스택(Stack) 은 자료구조에서 선형 구조라고 하는데, 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다. 이와 달리 트리는 비선형 구조입니다. 비선형 구조는 데이터가 계층적 혹은 망으로 구성되어 있는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. Tree 에서 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연.. 더보기 [Python] HashTable (Chaining, Open Addressing) 해시테이블이란, 해시함수를 이용해 키를 값에 매핑하는 자료구조입니다. 해시함수란, 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수로, 쉽게 말해 임의의 값을 넣어도 예상 크기 내에서 결과가 나오는 함수입니다. 예를 들면 ‘나머지를 반환하는 함수’가 좋은 해시 함수의 예입니다. HashTable 해시함수를 이용해 키를 값에 매핑하는 자료구조 해시함수 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수 쉽게 말해 임의의 값을 넣어도 예상 크기 내에서 결과가 나오는 함수 ‘나머지를 반환하는 함수’가 좋은 해시 함수의 예 def modThree(n): return n % 3 print(modThree(0)) # 0 print(modThree(1)) # 1 print(mod.. 더보기 [Python] LinkedList 예제 (Palindrome) 주어진 리스트가 팰린드롬인지 판별하는 프로그램을 작성하세요. 예시1) [1, 2, 2, 1] ⇒ True 예시2) [1, 2] ⇒ False test.python from structures import LinkedList l1 = LinkedList() for num in [1, 2, 2, 1]: l1.append(num) l2 = LinkedList() for num in [1, 2]: l2.append(num) assert isPalindrome(l1) assert not isPalindrome(l2) practice.python def isPalindrome(ln): arr = [] head = ln.head if not head: return True node = head while node: .. 더보기 [Python] Queue 예제 (Josephus) 1부터 N까지 차례대로 줄을 섰을 때, 맨 앞에 선 사람만 들여보내주고 그 다음 순서인 사람은 제일 뒤로 보내는 특이한 줄서기가 있습니다. 예를 들어, N=6인 경우, 123456 이 순서대로 줄을 서있을 것입니다. 이때 제일 먼저 1이 입장하고 남은 순서는 23456이 됩니다. 2는 두 번째 순서이므로 제일 뒤로 보내서 34562가 됩니다. 다시 3이 입장하여 4562가 되고, 4가 두 번째 순서이므로 5624가 됩니다. 5가 입장하고 246, 2가 입장하고 64, 6이 입장하여 4, 마지막으로 4가 입장하게 됩니다. N이 주어질 때 제일 마지막으로 입장하는 숫자를 계산하는 프로그램을 작성하세요. test.python assert test_problem_queue(2) == 2 assert test_p.. 더보기 [Python] Queue (FIFO) '큐'란 자료 구조는 "놀이기구"을 떠올리면 된다. 한 줄로 섰다가 한 줄로 나오는 놀이기구! (데이터를 한쪽 끝으로 넣고, 반대쪽에서 빠져 나온다) Swift 언어에서의 큐 의 예시도 함께 비교해 보자. Queue - 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조 놀이기구 특징: First In First Out = FIFO 가장 처음에 줄을 선 사람이 가장 빨리 나온다. 가장 마지막에 선 사람은 가장 늦게 나온다. 먼저 해야 하는 일들을 저장하고 싶을 때나 먼저 들어온 일들을 순서대로 처리해야 할 때 큐를 사용한다. test.python def test_queue(): queue = Queue() queue.push(1) queue.push(2) queue.push(3) que.. 더보기 [Python] Array & LinkedList 연결리스트, 스택, 큐, 해시테이블, 힙 → 파이썬의 베이직 자료구조 5인방 자료구조는 알고리즘을 효율적으로 구현하기 위한 기초 체력이므로 제대로 공부해 봅니다. Array vs. Linked LIst Array : 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트) LinkedList (연결리스트) : 직접 구현. 접근 어려움, 삽입 쉬움. Array LinkedList 특정 원소 조회 O(1) O(N) 중간에 삽입 삭제 O(N) O(1) 데이터 추가 데이터 추가 시 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다. 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다. 정리 데이터에 접근하는 경우가 빈번하면 Array 사용 삽입과 삭제가 빈번하면 LinkedList를 사용 .. 더보기 [Python] Stack 예제 여는 괄호와 닫는 괄호가 쌍을 이루는지를 확인하는 코드를 짜기 위해 스택 자료구조를 사용해 봅니다. '(', ')', '{', '}', '[' 및 ']' 만 포함된 문자열이 주어졌을 때 입력 문자열이 유효한지 확인하는 프로그램을 작성하세요. assert test_problem_stack("()") assert test_problem_stack("()[]{}") assert test_problem_stack("({[][]})") assert test_problem_stack("({[]})") assert not test_problem_stack("(]") assert not test_problem_stack("(()]") assert not test_problem_stack("(((])") assert n.. 더보기 이전 1 2 다음
