• 하노이의 탑

  

  문제

  세개의 막대와 여기에 쌓여질 서로 다른 크기의 원반들로 구성

  퍼즐이 시작될 때는 원반들이 한 막대에 크기가 작은 것부터 큰 순서로, 제일 위에 제일 작은 워반이 원뿔형태로 쌓여 있다.

  퍼즐의 목적은 전체 원반을 다음 막대로 다음의 규칙을 지키면서 옮기는 것이다.

  규칙

  한번에 하나의 원반만 옮길 수 있다

  옮길 때마다 한 막대의 맨 위의 원반을 다른 막대에 이미 놓여있는 원반위로 옮기게 된다.

  자기보다 작은 원반 위로는 옮길 수 없다.

  알고리즘

  맨 위의 n-1개의 원반을 처음 탑에서 보조 탑으로 옮긴다.

  처음 막대의 n번째 원반을 목표 탑으로 옮긴다

  보조 탑의 n-1개의 원반을 목표 탑으로 옮긴다

  처음 탑으로부터 보조 탑으로 n-1개의 원반을 옮기는 문제는 또 다른 탑 문제로 생각될 수 있다.

  def hanoi(n, from_pos, to_pos, aux_pos):
  	if n == 1:
  		print(from_pos, "to", to_pos)
  		return
  	hanoi(n - 1, from_pos, aux_pos, to_pos)
  	print(from_pos, "to", to_pos)
  	hanoi(n - 1, aux_pos, to_pos, from_pos)
  
  

연결리스트 (Linked List)란?

• list vs set

  list의 한 표현법으로 linked list가 있다.

  list는 순서가 있다.

  set은 순서가 없다. e.g. {1,2,3} = {2,1,3}

• list를 표현하는 방법

  array

  

  하나의 배열의 항목을 저장하기 위해 메모리 블록 하나가 할당된다. 배열의 항목은 특정 항목의 인덱스를 첨자로 사용하여 일정한 시간으로 접근할 수 있다.

  • 배열의 항목에 접근하는 데 왜 일정한 시간이 걸리는가?

    배열의 항목에 접근하기 위해서는 항목의 주소가 배열의 기본 주소로부터의 offset으로 계산. 기본주소 + offset

    처음에 데이터 형에 따라 항목의 크기가 계산되고, 그것이 항목의 인덱스에 곱해져서 offset이 된다. offset =size * index

    이 과정에서 한 번의 곱셈과 한 번의 덧셈이 필요하다.

    이 두 연산이 일정한 시간이 걸리므로 배열 접근은 일정한 시간으로 수행된다고 할 수 있다.

  array는 사이즈가 유동적이지 못하다.

  linked list

  

  연결 리스트(Linked Lists)는 데이터의 집합을 저장하기 위해 사용되는 데이터 구조이다. 연결 리스트는 다음의 속성을 갖는다.

  연속되는 항목들이 포인터로 연결된다.

  마지막 항목은 NULL을 포인트한다.

  프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.

  (시스템 메모리가 허용하는 한) 필요한 만큼 길어질 수 있다.

  메모리 공간을 낭비하지 않는다.(하지만 포인터를 위한 추가의 메모리를 필요로한다.)

• 연결리스트 ADT

  다음의 연산이 연결 리스트를 추상 데이터형, 즉 ADT (Abstract Data Type)가 되도록 한다.

  연결 리스트의 주요 연산

  삽입 : 항목을 리스트에 추가

  삭제 : 지정된 위치의 항목을 리스트로부터 삭제하여 그 항목을 리턴

  연결 리스트의 보조적 연산

  리스트 삭제 : 리스트의 모든 항목을 삭제 (리스트도 삭제)

  갯수 세기 : 리스트의 항목의 갯수를 리턴한다.

  리스트의 끝으로부터 n 번째 항목 찾기 등

  왜 연결 리스트를 사용하는가?

  연결 리스트와 같은 기능을 하는 다른 데이터 구조들이 많이 있다.

  연결 리스트에 대해 더 논의하기 전에 연결 리스트와 배열의 차이점을 이해하는 것이 중요하다

  연결 리스트와 배열 모두 데이터 집합을 저장하기 위해 사용된다.

• 배열의 장점 (vs Linked List)

  간단하고 사용하기 쉽다

  항목에의 접근이 더 빠르다. (일정한 시간이 걸리는 접근)

• 배열의 단점 (vs Linked List)

  고정된 크기 : 배열의 크기는 정적이다. (사용하기 전에 배열의 크기를 지정해야 한다 - 실행시간에 변경할 수 없다.)

  복잡한 위치 기반의 삽입 : 주어진 특정 위치에 항목을 삽입하려면 기존의 항목들을 이동해야 할 수 있다. 이렇게 해야 원하는 위치에 새 항목을 추가할 자리가 생긴다. 만약 새 항목을 추가할 자리가 가장 앞이면 다른 항목들의 이동 연산이 더욱 오래 걸린다.

• 동적 배열

  동적 배열 (또는 확장 가능 배열, 크기 변경 가능 배열, 동적 테이블, 배열 리스트 등으로 불린다)은 랜덤 접근이 가능한, 크기가 변하는 리스트 데이터 구조

  동적 배열을 구현하는 한 가지 간단한 방법은 처음에 일정한 고정된 크기의 배열로 시작하는 것이다.

  이 배열이 가득 차면, 원래 배열의 두 배 크기의 새 배열을 만든다.

  마찬가지로 배열의 항목의 수가 절반 이하가 되면 배열 크기를 반으로 줄인다.