하노이탑 문제

하노이탑 문제란큰판이 작은판보다 반드시 아래에 배치되어야하는 규칙을 지키면서 탑을 한 지점에서 다른 지점으로 옮기는 문제이다.아이디어하노이탑 문제는 분할정복 기법으로 접근하여 풀 수 있다. 즉, 하나의 큰 문제를 여러개의 작은 문제로 쪼개어서 풀 수 있다.설계# 디스크 옮기기def move(from, to): disk = tower[from].top() tower[from].pop() tower[to].push(disk)# 하노이 탑 옮기기def hanoi(n, from, temp, to): if n == 0: return hanoi(n -1, from, to, temp) move(from, to) hanoi(n -1, temp, from, to) 하노이탑 문제는 세개의 작은 문제로 쪼갤 수 있다.① ..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 11. 20.

[ 자료구조 ] Stack

#1 스택스택은 데이터를 쌓는 형태로 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last in First Out) 자료구조다.#2 연산push스택에 데이터를 삽입하는 연산으로 스택의 가장 위에 데이터를 저장한다.pop스택에 데이터를 삭제하는 연산으로 가장 마지막에 저장한 데이터를 제거한다.peek스택의 가장 위 데이터를 확인한다.#3 스택의 사용파이썬# 빈 스택 초기화stack = []print("stack:", stack)# 스택에 원소 추가stack = [1, 2, 3]stack.append(4)print("stack:", stack)# 스택 원소 제거stack = [1, 2, 3]stack.pop()print("stack:", stack)# 스택 원소 찾기stack = [1, 2, 3..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 26.

스택 예제: 미로찾기

스택스택은 데이터를 쌓는다. 그리고 가장 나중에 들어온 데이터를 먼저 처리한다. 당장 눈에 들어온 일부터 먼저 처리하는 느낌이다. 미로를 탐험하다보면 보고 있는 위치가 어떤 장소이냐에 따라 스택에 넣을 지 말지, 탐색을 할 지를 결정할 수 있다. 위치struct Pos { int row; int col; // 디버깅을 위한 편의 기능 friend ostream &operator 스택으로 미로찾기void StackMaze() { Stack s; Pos start = {1, 1}; // i = 1, j = 1 시작 지점 s.Push(start); while (!s.IsEmpty()) { Pos p = s.Top(); s.Pop(); ..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 19.

[자료구조] Stack

자료구조를 사용하는 이유데이터는 구조화 된 여부에 따라 정형, 비정형으로 구분한다. 컴퓨터 시스템에서 데이터를 효율적으로 다루기 위해서는 데이터가 구조화되어야한다. 데이터를 효율적으로 저장하고 관리하기 위해 구조화 된 형태를 자료구조라고 한다. 배열, 스택, 큐 모두 자료구조이다. 자료구조마다 각기 다른 방식으로 데이터를 관리하고 처리한다. 스택개념스택은 후입선출원칙(LIFO)에 따라 데이터를 관리한다. 데이터를 넣는 순서와 반대로 데이터가 꺼내진다. 즉, 가장 마지막에 넣은 데이터가 가장 먼저 나오게 된다.스택에서 가장 마지막에 들어간 데이터의 위치를 top이라고 한다.스택은 push, pop, peek 연산이 있다. push 연산은 데이터를 넣는다. pop은 top에 있는 데이터를 제거한다. peek..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 19.

스택: 차곡차곡 쌓여가고 있는 나의 빨래들처럼

스택이란? 스택은 데이터를 임시로 저장하는 자료구조로 데이터를 차곡차곡 쌓을 수 있습니다. 스택에 데이터를 넣는 작업을 push, 빼는 작업을 pop이라고 합니다. 스택의 윗부분을 top, 아랫부분을 bottom이라고 합니다. 스택 구성요소 스택 배열 스택의 본체입니다. 데이터를 저장하는 공간입니다. 인덱스가 0 인 공간이 바닥(bottom)입니다. 빈 스택에 데이터를 넣으면 인덱스가 0인 공간부터 채워집니다. stk[0] = data 스택 크기: capacity 스택에 들어갈 수 있는 데이터의 최대 개수입니다. 스택배열의 크기와 일치합니다. capacity = len(stk) 스택 포인터: ptr 스택이 현재 가진 데이터의 수입니다. ptr이 0이면 스택은 비어있습니다. 스택이 가득찼다면 ptr은 ca..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 3. 26.