분류 전체보기 (35) 썸네일형 리스트형 여행 준비 보호되어 있는 글입니다. [3부] 11장 해시 테이블 해시 테이블 (Hash Table) 해시 테이블 (또는 해시 맵)은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조. 해시 구조란? 키(Key)와 값(Value) 의 쌍으로 이루어진 데이터 구조. Key를 이용하여 데이터를 찾으므로, 속도를 빠르게 만드는 구조. 파이썬에서는 Dictionary (딕셔너리) 타입이 해시 테이블과 같은 구조임. 기본적으로는, 배열로 미리 Hash Table 크기만큼 생성해서 사용함. 공간은 많이 사용하지만, 시간은 빠르다는 장점이 있음. 검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용됨. 장점 단점 데이터 저장/ 검색 속도가 빠름 일반적으로 저장공간이 조금 더 많이 필요함 키에 대한 데이터가 있.. [3부] 10장 데크, 우선순위 큐 큐 (Queue) 한쪽 끝 (rear) 에서는 삽입 연산만 이루어지고, 다른 한쪽 끝 (front) 에서는 삭제 연산만 이루어지는 유한 순서 리스트 FIFO (First In First Out) 구조 큐에서 데이터를 넣는 것은 put, 데이터를 꺼내는 것은 get 이라고 함. front 는 데이터를 get 할 수 있는 위치, rear 은 데이터를 put 할 수 있는 위치를 의미함. queue큐의 다른 형식 Circular Queue (원형 큐) => 9장 25번 문제 (원형 큐 디자인) Priority Queue (우선 순위 큐) => 10장 27번 문제 Deque (Double-Ended Queue) => 10장 26번 문제 (원형 데크 디자인, 이중 연결 리스트 문제) 데크 (Deque) Double.. [3부] 09장 스택, 큐 스택 (stack) 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형 push(): 요소를 컬렉션에 추가함. pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거함. FILO (First In Last Out) 구조 스택에서 데이터를 넣는 것은 push, 데이터를 꺼내는 것은 pop 이라고 함. push와 pop을 하는 위치를 top 이라고 하고, 스택의 가장 아랫 부분을 bottom 이라고 함. 연결 리스트를 이용한 스택 ADT 구현 class Node: def __init__(self, value, next = None): self.value = value self.next = next class Stack: def __init__(self): self.hea.. [3부] 08장 연결 리스트 자료구조 | 파이썬에 한정된 이야기 아님! 배열과 연결리스트 (Array & Linked List) 배열과 연결리스트는 둘 다 자료들을 저장하는 방식의 일종 (자료구조). 이 두 가지 기본적인 형태가 수많은 자료구조를 만드는 뼈대가 됨. 배열 (Array) 특정 자료형 (Data Type) 들이 메모리 공간상에서 연속적으로 이루어져 있는 자료구조. (e.g. 위 예시는 int 를 담는 배열이, 메모리 공간상에서 연속적인 공간으로 연결되어 있음) 각각의 공간들은 0으로 시작하는 index 값 (0-4) 에 의해 즉각적으로 참조될 수 있음. 메모리 공간상에서 연속적으로 이루어져 있기 때문! 따라서, 배열은 자료에 대한 접근이 빠름. (index 값으로 바로 원하는 칸에 가서 자료를 확인할 수 있기 때문에, .. [3부] 07장 배열 선형 자료구조 & 비선형 자료구조 선형 자료구조 (Linear) 자료를 구성하는 데이터를 순차적으로 나열한 형태 자료들 간의 앞뒤 관계가 1:1의 선형 관계 배열, 스택, 큐, 연결 리스트, 데크 등 비선형 자료구조 (Non Linear) 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태 자료들 간의 앞뒤 관계가 1:n, n:n 의 관계 트리, 그래프 등 (계층적 구조) 디스크 공간 할당 (Dist Space Allocation) 파일 할당 (사용자가 하나의 파일을 불러올 때, 디스크에 블록 단위로 흩어져 있는 파일을 신속하게 찾아내고, 신속하게 저장하기 위해서) 에는 다양한 방법이 있음. 크게 3가지 방법을 알아봄. 연속 할당 (Contiguous allocation) 연결 할당 (Linked .. [2부] 06장 문자열 조작 3부 (선형 자료구조), 4부 (비선형 자료구조)에 들어가기 전에 2부 (파이썬) 마지막에 06장 문자열 조작으로 구성되어 있음. 문자열 조작 (String Manipulation) 이란? 문자열을 변경하거나 분리하는 등의 여러 과정. 문자열 처리와 관련한 알고리즘이 쓰이는 대표적인 분야 정보 처리 분야 (e.g. 어떤 키워드로 웹 페이지를 탐색할 때) 통신 시스템 분야 (e.g. 문자 메시지나 이메일을 보낼 때) 프로그래밍 시스템 분야 (e.g. 프로그램은 그 자체가 문자열로 구성되어 있음) 문자열 조작 part 에서 다루는 문제 no. title leetcode status 1 유효한 팰린드롬 리트코드 125 O 2 문자열 뒤집기 리트코드 344 O 3 로그 파이 재정렬 리트코드 937 X (문제 이.. [2부] 05장 리스트, 딕셔너리 파이썬을 사용하면서 가장 빈번하게 접하게 될 자료형 리스트 (Mutable) 딕셔너리 (Mutable) 리스트 (List) 파이썬의 리스트 순서대로 저장하는 시쿼스 변경 가능한 목록 (Mutable List) 입력 순서 유지 내부적으로는 동적 배열로 구현 동적 배열 (Danamic array): 크기가 고정되지 않은 배열 (7장 배열에서 자세히 소개) 정적 배열 (Static array) 정적 배열 (Static array): 크기가 고정되어 있어, 데이터를 크기 만큼만 저장할 수 있음. 파이썬 리스트는 다양한 기능을 제공함. 리스트를 사용하면 사실상 스택을 사용할지, 큐를 사용할지 고민하지 않아도 됨 (스택, 큐는 9장에서 다룸). 스택과 큐에서 사용 가능한 모든 연산 제공. 또한 리스트는 O(1)에 .. [2부] 04장 빅오, 자료형 빅오 (big-O) 점근적 실행 시간 (Asymptotic Running Time)을 표기할 때, 가장 널리 쓰이는 수학적 표기법 중 하나. 점근적 실행시간이란? 입력값 n이 커질 때 (즉, 입력값이 무한대를 향할 때), 함수의 실행 시간의 추이 알고리즘은 궁긍적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면, 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝남. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 남. 점근적 실행 시간은 달리 말하면 시간 복잡도 (Time Complexity)라고 함. 시간 복잡도란? 사전적 정의: 어떤 알고리즘을 수행하는데 걸리는 시간을 계산 복잡도(Computat.. [2부] 03장 파이썬 파이썬 알고리즘 인터뷰 책 환경 CPython (파이썬의 공식 인터프리터) 파이썬 버전 3.7 PEP8 파이썬 문법 인덴트 (Indent) 파이썬 Indent는 공식 가이드인 PEP8에 따라 공백 4칸을 원칙으로 함. 구글 파이썬 가이드 라인 또한 공백 4칸 들여쓰기가 원칙. 강제는 아니며, 얼마든지 선택적으로 적용 가능, 이외에도 다음과 같은 기준이 있음. 첫 번째 줄에 파라미터가 있다면, 파라미터가 시작되는 부분에 맞춤. 첫 번째 줄에 파라미터가 없다면 공백 4칸 인덴트를 한 번 더 추가함. foo = long_function_name(var_one, var_two, var_three, var_four) def long_function_name( var_one, var_two, var_three, v.. 이전 1 2 3 4 다음
