새콤달콤하니    

[두다지 week2] 데이터 구조(리스트, 스택...) python으로 구현하기

develop, algorism, python, dudaji
written byzuhern1zuhern

in

2019. 02. 16

메모

우선순위 큐, AVL

데이터구조

리스트

1. python으로 리스트 구현 예제

2. python 내장 리스트 사용법

3. 문제

4. 문제풀이

일단은 풀었으니까 저장용

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다.
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

리스트 구현해서 풀이 (메모리: 29308 KB 시간: 6212 ms)

import sys

class Node:
  def __init__(self, initdata):
    self.data = initdata
    self.next = None
    self.prev = None


class LinkedList():
  
  def __init__(self):

    self.next = None
    self.last = None
    self.current = None
    self.head = None
    self.count = 0

  def insert(self, value):
    
    new_node = Node(value)

    if self.head is None:
      new_node.prev = new_node
      new_node.next = new_node
      self.head = new_node
      self.current = new_node
    else:
      new_node.next = self.head
      new_node.prev = self.last
      self.head.prev = new_node
      self.last.next = new_node

    self.last = new_node
    self.last = new_node
    self.count += 1

    return self.current
    
  def deleteCurrent(self):

    tar_node = self.current
    prev_node = tar_node.prev
    next_node = tar_node.next

    if self.head is self.current:
      self.head = next_node
    
    if self.last is self.current:
      self.last = prev_node

    prev_node.next = next_node
    next_node.prev = prev_node

    self.current = next_node
    self.count -= 1

    return tar_node

  def getCurrent(self):
    return self.current
  
  def getNext(self):
    self.current = self.current.next
    return self.current

  def listCount(self):
    return self.count
 
cnt, gap = map(int, sys.stdin.readline().strip().split())
 
linked_list = LinkedList()

for i in range(1, cnt+1):
  linked_list.insert(str(i))

result = '<'
 
while not linked_list.listCount() == 0 :
  for i in range(gap-1):
    linked_list.getNext()

  result += str(linked_list.deleteCurrent().data)
  if not linked_list.listCount() == 0:
      result += ', '
  else:
      result += '>'
 
sys.stdout.write(result)

array 사용해서 시간 단축… (메모리: 29056 KB 시간: 72 ms)

  • next 찾는 for 문 변경… 
import sys

cnt, gap = map(int, sys.stdin.readline().strip().split())
 
tarList = []

for i in range(1, cnt+1):
  tarList.append(str(i))

remove_index = gap-1
result = '<'

while not len(tarList) == 0:
  result += str(tarList.pop(remove_index))
  if not len(tarList) == 0:
    result += ', '
    remove_index += (gap-1)
    # print("remove_index", remove_index, "len(tarList)", len(tarList))
    if remove_index > len(tarList)-1 :
      remove_index = remove_index % len(tarList)
  else:
    result += '>'
 
sys.stdout.write(result)

스택

1. python으로 스택 구현 예제

2.python 내장 스택 사용법

  • 파이썬에는 내장된 stack이 없습니다. 내장된 list의 append()와 pop()을 이용하여 스택처럼 사용합니다.

3. 문제


큐

1. python으로 큐 구현 예제

2. python 내장 큐 사용법

3. 문제


우선순위큐

1. 구현 예제

2. python 내장 우선순위큐

3. 문제

  1. 우선순위 큐 구현하기
  2. unittest를 통해 구현체에 대한 검증 (push, pop, peek, (array 기반인 경우) expand, 비어있는 상태에서 pop 테스트 등)

추가자료