크래프톤 정글 week01, day08 - 하노이탑, 1주차 공부키워드 - 2, 퀵 정렬

하노이탑

• 3개의 기둥이 있고 하나의 기둥에 여러 개의 원반이 있는데 각자 크기가 다 다르며 한 번에 한 개의 원반만 옮길 수 있고 크기가 큰 원반은 작은 원반 위에 올릴 수 없다.
• 재귀 함수를 이용한 알고리즘의 대표 문제이며 다음과 같이 동작한다
  • 옮겨야 할 원반이 하나 뿐이라면, 해당 원반을 출발지 기둥에서 목적지 기둥으로 옮기기
  • 그렇지 않으면 재귀함수를 사용해 가장 큰 원반을 제외한 나머지 원반들을 보조 기둥으로 옮긴다.
  • 가장 큰 원반을 목적지 기둥으로 옮기고, 보조 기둥에 있는 원반들을 목적지로 옮긴다.

# 하노이 함수(원판의 갯수, 시작봉, 중간봉, 끝봉)
def hanoi(n, start, sub, finish):
    # 만약 원판의 개수가 1개면 끝봉으로 1번 이동하면 끝이니까 리턴값
    if n == 1:
        print(start,finish)
    # 그렇지 않다면 큰 원판 외 원판을 sub로 옮긴 경로 + 큰 원판을 옮기는 경로 + 큰 원판 위에 나머지 원판을 옮기는 경로를 출력
    else:
        hanoi(n-1, start, finish, sub)
        print(start, finish)
        hanoi(n-1, sub, start, finish)

# 원판의 개수 입력값을 받기
n = int(input())
# 이동 횟수는 규칙성으로 연산 없이도 2의 n승 -1으로 나오기 때문에 미리 출력이 가능 
print(2**n-1)
# 원판의 개수가 20이 넘어가면 경로가 기하급수적으로 늘어나기 때문에 20이상은 출력을 하지않게 막기
if n<=20:
    hanoi(n, '1', '2', '3')

 

하노이탑은 반드시 2개를 옮길 때 3번의 경로를 거쳐 옮길 수 있다. 예를 들어 3개를 옮겨야 할 경우엔

이런 식으로 가장 큰 원반을 옮기기 전에 2개를 옮기려면 3번이 진행된다.

그리고 큰 원반을 1번에서 3번으로 옮기고 2번에 있는 2개를 똑같이 3번을 사용해서 3번으로 이동하여 완성

3(처음 2개 옮길 때) + 1(큰 원반 이동) + 3(큰 원반 위에 2개 옮길 때) = 7

3개를 옮기려면 총 7번이 소요된다.

​

원판의 개수가 홀수 일 땐 2번 째 기둥에 짝수 일 땐 3번 째 기둥에 해야 최적의 경로로 떨어지는 것 같다.

원판이 2개일 때는 3번, 4개일 때는 15번이 소요되는데, 3, 7, 15

규칙성이 생긴다.

2^(원판의 개수) -1 이 최적의 경로 소요 횟수이다.

5개 일 땐 2^5-1 = 31번, 6개 일 땐 2^6-1 = 63번

원판이 늘어나든 줄어들든 같은 값으로 반복이 되기 때문에 재귀함수 알고리즘에 딱 맞는 문제 같다.

---

1주차 공부 키워드 - 2

• 이분 탐색
  • 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
  • 리스트의 중간 값을 확인해서 원하는 값을 찾을 때까지 반으로 나눠가는 방식
  • 알고리즘 작동 방식
    • 1. 리스트의 중간 위치 확인
    • 2. 찾고자 하는 값이 중간 값보다 작으면, 리스트 끝을 중간 위치로 변경해 뒷 부분 제거
    • 3. 찾고자 하는 값이 중간 값보다 크면, 리스트 시작을 중간 위치로 변경해 앞 부분 제거
    • 4. 리스트에 한 요소만 남거나 찾고 싶은 값을 찾으면 종료

​

• 분할 정복
  • 복잡한 문제를 작게 나누어 해결하는 알고리즘
  • 큰 문제를 해결하기 쉬운 여러 하위 문제로 분해해 해답을 결합하여 원래 문제의 해답을 찾는 방법
  • 단계
    • 1. 분할
      • 주어진 문제를 더 작은 부분으로 분할, 원본 문제를 두 개 이상으로 분할
    • 2. 정복
      • 분할된 작은 문제를 재귀적으로 해결. 만약 크기가 작아 쉽게 해결 가능하면 이 단계에서 해결
    • 3. 결합
      • 하위 문제의 해결책을 원래 문제의 해결책으로 결합
  • 예시)
    • 병합 정렬, 퀵 정렬, 이분 탐색 등

​

• 스택
  • LIFO(후입선출) 원칙을 따르는 자료구조 중 하나. *매우 중요
    • 후입선출 : 가장 마지막에 들어온 항목이 가장 먼저 나가는 방식
  • 주요 연산
    • Push
      • 스택의 맨 위에 새로운 요소를 추가
    • Pop
      • 스택의 맨 위의 요소를 제거하고 반환
    • Top/Peek
      • 스택의 맨 위의 요소를 반환하지만 제거하진 않음
    • IsEmpty
      • 스택이 비어있는지 확인
  • 배열이나 연결 리스트를 사용해 구현할 수 있으며, 항상 최상위 요소에 대한 빠른 접근과 수정이 가능해야 함

​

• 큐
  • FIFO(선입선출) 원칙을 따르는 자료구조 중 하나. *매우 중요
    • 선입선출 : 가장 먼저 들어온 항목이 가장 먼저 나가는 방식
  • 주요 연산
    • Enqueue
      • 큐의 끝에 새로운 요소를 추가
    • Dequeue
      • 큐의 앞부분에서 요소를 제거하고 반환
    • Front/Peek
      • 큐브의 첫 번째 요소를 확인하지만 제거하진 않음
    • IsEmpty
      • 큐가 비어있는지 확인
  • 작업 스케줄링, 너비우선탐색(BFS)알고리즘, 캐시 구현 등에 사용
  • 배열이나 연결 리스트를 통해 상황에 따라 구현할 수 있다.
    • 배열 : 빠른 접근이 가능하나 요소를 제거할 때마다 모든 요소를 이동해야 함
    • 연결 리스트 : 요소를 추가하고 제거하는 것이 간편하지만 접근 시 많은 시간 소요

​

• 우선순위 큐
  • 각각의 요소가 우선순위를 가진 자료구조
  • 일반적인 큐와는 다르게 우선순위가 가장 높은 요소가 가장 먼저 나가게 됨
  • 주요 연산
    • Insert
      • 우선순위와 함께 요소를 추가
    • Delete of Remove
      • 우선순위가 가장 높은 요소를 삭제하고 반환
    • Peek
      • 우선순위가 가장 높은 요소를 확인하지만 삭제하진 않음
  • 사용 처
    • 여러 작업을 우선순위에 따라 스케줄링해야 할 때
    • 네트워크 트래픽 제어에서 패킷을 우선순위에 따라 처리해야 할 때
    • 그래프 알고리즘에서 최소 신장 트리나 최단 경로를 찾을 때 사용
  • 배열, 연결 리스트, 힙 등 다양한 방법으로 구현 가능
    • 힙
      • 이진 트리의 일종으로 가장 일반적이며, 부모 노드와 자식 노드 간에 특정 순서가 있는 트리
      • 우선순위 큐를 구현하는데 매우 효율적이고, 삽입 및 삭제 연산에 O(log n)로그 시간 복잡도의 시간 복잡도를 가짐

​

• 연결 리스트(Linked List)
  • 노드라는 요소들이 포인터를 통해 서로 연결된 형태로 데이터를 저장하는 자료구조
  • 주요 연산
    • Insertion(삽입)
      • 연결 리스트의 특정 위치에 새로운 노드를 삽입
    • Deletion(삭제)
      • 연결 리스트의 특정 노드를 삭제
    • Search(탐색)
      • 연결 리스트에서 특정 값을 찾는다.
  • 형태
    • 단일 연결 리스트
      • 각 노드가 다음 노드만을 가리키는 형태
    • 이중 연결 리스트
      • 각 노드가 이전 노드와 다음 노드를 모두 가리키는 형태
    • 원형 연결 리스트
      • 마지막 노드가 처음 노드를 가리키는 형태
  • 장점
    • 배열과 달리 공간 할당이 필요가 없어 메모리 활용이 효율적
    • 동적으로 데이터를 관리하기 때문에, 실행 시간 중에 데이터의 추가 및 제거가 자유롭다.
  • 단점
    • 임의 접근이 불가능해 특정 요소를 찾으려면 처음부터 순차적으로 탐색해야 한다.

​

• 해시 테이블
  • key-value값을 저장하는데 사용되는 데이터 구조. 연관배열이라고도 불린다. *가장 중요한 자료구조 중 하나
  • 해시 함수를 사용해 키를 정수로 변환하고 인덱스로 사용해 값을 저장한다.
  • (넣을 값 % 인덱스 개수)로 나온 나머지 값의 인덱스 자리에 값을 저장한다.
  • 주요 연산
    • Insert(삽입)
      • 주어진 키와 값을 해시 테이블에 삽입
    • Delete(삭제)
      • 주어진 키와 그에 해당하는 값을 해시 테이블에서 삭제
    • Search(탐색)
      • 주어진 키에 해당하는 값을 찾는다.
  • 삽입, 삭제 탐색연산의 시간 복잡도가 O(1)이기 때문에 효율적인 탐색속도를 제공
  • 해시 충돌 해결 방법
    • 체이닝(chaining)
      • 두 개 이상의 키가 동일한 해시코드를 가질 때 해당 버킷의 리스트에 새로운 key-value값을 추가
        • 동일한 자리에 값이 더 할당될 시 새로운 값을 맨 앞자리에 넣는다.
          • ex) 기존 값 : 42, 새로운 값 : 21 => index[0] = 21, 42
      • 조회 발생 시 해당 버킷을 찾아 리스트를 순회하여 원하는 키를 찾는다.
      • 충돌이 자주 발생하면 많은 key-value값이 몰려 탐색시간이 길어짐
    • 개방 주소법(Open Addressing)
      • 해시 테이블의 다른 버킷에 key-value값을 저장
      • 해시 테이블이 가득 차면, 새로운 key-value값을 저장하기 위해 테이블 크기를 조정해야 함
  • 데이터베이스에서 인덱스를 구현하거나, 웹 브라우저의 캐싱, 컴파일러 등에 활용

 

---

퀵 정렬

• 분할 정복을 통해 리스트를 정렬하는 효율적인 알고리즘
• 원리
  • 1. 리스트에서 한 요소를 선택하는데, 이 요소를 pivot(피벗)이라고 한다.
  • 2. 피벗보다 작은 요소들은 피벗의 왼쪽으로, 큰 요소들은 피벗의 오른쪽으로 이동 시키는데 이 과정을 파티션이라고 한다.
  • 3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 재귀적으로 정렬한다.
• 시간 복잡도는 O(n log n)이며, 최악의 경우 O(n^2)이지만 그런 상황은 드물고 대부분에 있어 매우 효율적인 알고리즘이기 때문에 자주 사용된다.

​

학습시간 : 11 ~ 26시