ComDoc ComDoc

스택(Stack ADT) 스택(stack)을 영한사전에서 찾아보면 '(보통 깔끔하게 정돈된) 무더기'라고 되어 있습니다. (차곡차곡) 물건을 쌓아 올리면 아래 것은 빼기가 어렵죠? 마지막에 쌓은, 제일 위의 것을 먼저 꺼내 쓸 수 밖에 없습니다. 이를 LIFO(= last-in, first-out = 후입 선출) 또는 FILO(= first-in, last-out = 선입 후출)라고 하며, 이와 같은 형태의 자료 구조를 스택이라고 합니다. 스택에 자료를 집어넣는(=쌓아주는) 것은 push, 스택에서 자료를 꺼내는 것은 pop이라고 합니다. 리스트와 클래스를 이용해서 스택 추상 자료형을 만들어 보겠습니다. class Stack: def __init__(self): self.data = [] def push..

요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation) 전설에 의하면 1세기에 유대인 로마 전쟁 당시 역사가 플라비우스 요세푸스와 40명의 유대인이 로마 군인에게 붙잡힐 위기에 처했다. 유대인 병사들은 포로로 잡히느니 죽음을 택하기로 했다. 사람으로 원을 만든 다음 사람이 남지 않을 때까지 매 세번째 병사를 죽여나가기로 작전을 세웠다. 요세푸스와 다른 한명은 일찍 죽음을 당하는 위치에 서고 싶지 않아 어디에 서야 최후까지 생존할 수 있을 지 빨리 계산해야 했다. n명의 사람이 원을 만들고 매 m번째 사람을 죽이는 프로그램을 구현하시오. 그리고 마지막으로 남을 두 사람을 계산하시오. 리스트 먼저 리스트를 이용해 보겠습니다. (문제를 보고 처음 떠오른 거라...

원형(순환형) 연결 리스트에서는 단방향 연결 리스트와 같은 노드를 사용합니다. 단방향과 다른 점은 원형 연결 리스트에서는 생성시 헤드의 링크(next 프로퍼티)가 자기 자신을 가리킨다는 것입니다. 여기에 삽입을 하면 최종적으로 마지막 요소의 링크가 헤드를 가리키게 되죠. 복잡한 양방향 연결 리스트를 만들지 않고 간단하게 역방향 탐색을 할 수 있다는 것이 원형 연결 리스트의 장점입니다. 원형 연결 리스트에서는 노드의 끝을 지나 계속 탐색하면 결국 역방향에 있는 노드로 이동할 수 있습니다. 다만 이렇게 수정할 경우 show 함수가 무한 루프에 빠집니다. show 함수의 조건문을 head에 다다르기 전에 멈추도록 수정해야 합니다. class Node: def __init__(self, element): sel..

단방향 연결리스트는 역방향 탐색이 쉽지 않습니다. 이를 해결하는 가장 쉬운 방법은 이전 노드의 링크를 만들어 주는 것입니다. 이럴 경우 메모리를 좀 더 소모하고, 프로그램이 약간 복잡해지는 단점이 있습니만, 삭제 과정에서 이전 노드를 찾을 필요가 없기 때문에 삭제가 단순해지는 장점도 있습니다. 실제로 프로그래밍을 해보면 단방향에서 조금만 코드를 수정하면 됩니다. 단방향과 비교해서 뭐가 달라졌는지 확인해보십시오. class Node: def __init__(self, element): self.element = element self.next = None self.previous = None class DoublyLinkedList: def __init__(self): self.head = Node('he..

리스트에는 단점이 있습니다. 마지막이 아닌 부분에 데이터를 추가하거나 삭제할 때 뒤 요소들을 모두 이동해야 하는 점이죠. 연결 리스트의 장점은 중간에 추가 삭제 시 요소를 이동할 필요가 없기 때문에 좀 더 빠르게 처리할 수 있습니다. 단점은 요소의 임의 접근을 지원하지 않는다는 점이죠. 연결 리스트 추상 자료형의 설계 연결 리스트는 노드를 기본으로 하는 자료형입니다. 노드는 요소(엘리먼트)와 다른 노드를 참조하는 링크로 구성되어 있습니다. class Node: def __init__(self, element): self.element = element self.next = None 새로운 노드를 추가할 때는 링크만 수정하면 됩니다. 연결 리스트에서는 어디서부터 시작할 지에 대한 문제가 있습니다. 그래서 ..

매일 하나씩 40일에 완성하는 파이썬 자료구조 & 알고리즘 추상 자료형 (Abstract Data Type, ADT) 추상 자료형이란 추상화 된 자료형이겠죠? 그럼 자료형이 뭘까요? 프로그래밍 언어마다 약간의 차이는 있지만 보통 정수, 실수, 불린, 문자, 문자열 등을 자료형이라 합니다. C언어에서는 구조체(https://dojang.io/mod/page/view.php?id=407)까지도 자료형에 포함합니다. 파생형(derived type)으로 분류하죠. 추상 자료형은 (class 등을 이용해서) 추상적으로 자료형을 표현했다 정도로 간단히 이해하고 넘어가겠습니다. 더 자세한 것은 위키 백과를 참고하시구요. 자료형: https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C%..

매일 하나씩, 40일 완성 파이썬 자료구조 & 알고리즘 1. 자료구조의 분류 단순구조 : 기본적인 자료형 정수 실수 문자 문자열 선형구조 : 자료들간 앞 뒤 연결 관계가 1:1을 가져 선형 관계라고 함. 순차리스트 : 배열, 자료가 메모리 상에 연속적으로 저장됨. 연결리스트 : 연속된 메모리 공간을 사용하지 않음. 단위: 노드 (= 데이터 + 다음 노드를 가르키는 참조값) 단순 연결 리스트 이중 연결 리스트 : 앞 뒤 모두의 참조값 저장. 원형 연결 리스트 : 마지막 노드가 첫번째 노드를 가르킴. 스택 stack : 후입 선출 Last in First out 큐 Queue : 선입 선출 덱 Deque : 양방향 인 아웃 가능, 스택 + 큐 비선형구조 : 자료들 간의 앞 뒤 연결 관계가 '1:다(多)', ..

깃헙에서 예제가 잘 보이지 않을 때는 raw를 클릭하시던지 저장해서 보시면 될 것 같습니다. 예제 주소: https://github.com/pycrawling/crawling-tutorial/blob/master/daum-cafe-mobile-crawler-reply.ipynb * 크롤링 + db 저장까지 하겠습니다. 본문편에서 설명한 부분은 제외합니다. 1. import sqlite 파이썬의 기본 내장 DB인 sqlite를 사용하겠습니다. import sqlite3 2. 데이터베이스 초기화 sqlite는 IF NOT EXISTS 조건을 사용해서 테이블을 생성할 수 있습니다. 편합니다. ^^ conn = sqlite3.connect(DB) cur = conn.cursor() sql = 'CREATE TA..