[Algorithm] 해시 테이블
* Python을 기준으로 합니다 해시 테이블 (Hash Table) - 개념 해시 테이블 : 키와 값을 매핑해 데이터 양에 상관없이 빠른 탐색을 가능하는 자료구조 Python에서는 일반적으로 dictionary 자료형으로 해시 테이블을 활용함 해시 테이블의 탐색은 O(1)O(1)의 time complexity를 가진다는 장점이 있음 - 키 자체가 해시 함수에 의해 값이 있는 index가 되기 때문 따라서 특정 값을 기준으로 조회를 여러번 해야 하거나, 특정 값과 매핑되는 값의 관계를 활용하는 경우 사용 - BUT, 완전 탐색이나 정렬, 최대/최소 등이 필요한 경우는 배열이 더 유용함 Time Complexity O(1)O(1) : 조회, 값 할당, 키 가져오기 ≠wdict.keys()≠wdict.keys(), 딕셔너리 초기화..
[Algorithm] 큐, 덱
* Python을 기준으로 합니다 큐 (Queue), 덱 (Deque) - 개념 큐 : FIFO (First In First Out) 형태의 자료구조 처리해야 하는 작업들을 큐에 쌓음으로써 쉽게 처리할 수 있음 스택과 마찬가지로 삽입과 삭제를 핵심적인 연산으로 가짐 - 배열에서 append()append()나 pop(0)pop(0)를 통해 삽입/삭제를 수행할 수 있지만, pop(0)pop(0)는 O(n)O(n)을 소모함 - 따라서 큐는 연결 리스트를 통해 구현하는 것이 좋음 큐의 주요 연산 enqueue()enqueue() : 큐의 맨 마지막에 새로운 요소를 추가 dequeue()dequeue() : 큐의 첫 번째 요소를 pop() isEmpty()isEmpty() : 큐가 비어있으면 TrueTrue 아니면 FalseFalse 원형 큐 (Circular Queue) 선형 큐(L..
[Algorithm] 스택
* Python을 기준으로 합니다 스택 (Stack) - 개념 스택 : LIFO (Last In First Out) 형태의 자료구조 처음 실행했던 위치로 돌아가기 위해 이전 실행들을 쌓아서 관리하는 용도 삽입과 삭제를 핵심 연산으로 가짐 스택의 주요 연산 push()push() : 새로운 데이터를 스택의 맨 위에 추가 pop()pop() : 스택의 맨 위에 위치한 데이터를 꺼내서 반환 isEmpty()isEmpty() : 스택이 비어있으면 TrueTrue, 아니면 FalseFalse peek()peek() : 스택 맨 위에 위치한 데이터를 확인 Python에서의 스택 활용 일반적으로 리스트를 스택처럼 활용함 Python 리스트의 append(),pop()append(),pop()은 각각 push(),pop()push(),pop()에 대응 isEmpty()isEmpty()의 경우 리스트의 le..
[Algorithm] 연결 리스트
* Python을 기준으로 합니다 연결 리스트 (Linked List) - 개념 연결 리스트 : 각 데이터들이 순서대로 링크를 통해 연결된 구조 연결 리스트에서 하나의 노드(Node)는 데이터와 링크(Link)를 가짐 링크는 다른 노드의 주소를 가리키는 역할 연결 리스트의 주요 연산 ∈sert()∈sert() : 특정 위치에 새로운 데이터를 삽입 ∂ete()∂ete() : 특정 위치의 데이터를 삭제 isEmpty()isEmpty() : 리스트가 비어있으면 TrueTrue 아니면 FalseFalse size()size() : 리스트의 크기 (들어있는 데이터 수) 반환 배열과 연결 리스트의 비교 리스트 요소 접근 배열은 모든 데이터가 크기가 같고 연속적인 메모리 공간에 위치함 - kk번째 데이터의 위치는 데이터 크기와 kk를 곱한 다음, 시작..
[Algorithm] 배열
* Python을 기준으로 합니다 배열 (Array) - 개념 배열 : 값 또는 변수들의 집합으로 구성된 구조, index와 값을 일대일 대응해 관리 list()list(), [][]로 선언되고, 크기 지정 없이 자동으로 resizing 되는 동적 구조 배열 내의 값을 자주 조회하는 경우 효율적이지만, 메모리 크기가 제한되거나 삽입이 많은 경우 비효율적 - 일반적으로 배열의 값 조회와 append()append()를 통한 배열 끝 삽입은 O(1)O(1)을 소모함 - 배열의 첫 번째나 중간 위치 삽입은, 해당 위치로부터 모든 기존 값들을 뒤로 shift 하므로 O(n)O(n)이 소모됨 배열의 차원 - 1차원 배열 : 기본적인 배열 형태 - 2차원 배열 : 1차원 배열의 확장, arr=[1234]와 같이 선언 ..
[Algorithm] 문자열
* Python을 기준으로 합니다 문자열 (String) - 개념 문자열 : 문자들의 집합으로, emutable 객체 배열처럼 사용할 수 있지만, 한번 선언된 문자열은 상수 취급을 하기 때문에 값을 임의로 변경할 수 없음 대표적으로 + 연산은 문자열을 결합하는데, 이는 내부적으로 상수끼리의 합으로 취급됨 - 결과적으로 새로운 상수를 생성하여 할당하는 방식으로 수행되므로 비효율적임 주요 유형 : Palindrome/Anagram, 진법 변환, 문자열 조작(변환, 탐색, 정렬), 정규표현식 - 구현 1. 문자열 초기화 ′′나 사용 hello1 = 'Hello World!' hello2 = "Hello World!" 2. 문자열 결합 + 나 ′′.jo∈() 사용 여기서 +는 각..