스택이란? Stack이라는게 뭘까요? 사전적 의미부터 살펴봅시다. 스택은 쌓다, 포개다 라는 의미를 가지고 있습니다. 말 그대로 데이터를 쌓아서 자료를 저장하는 구조입니다. 우리가 책을 위로 쌓아서 보관해놓았다고 생각해봅시다. 맨 밑에 있는 책을 꺼내기 위해선 어떻게 해야 할까요? 위에 있는 책들을 다 어딘가로 치운 다음 꺼내야 할 것입니다. 스택도 마찬가지입니다. 특정 데이터를 꺼내기 위해서는 위에 있는 데이터를 다 빼내야 합니다. 그래서 스택은 후입선출(LIFO; Last In First Out)의 특징을 가지고 있습니다. 스택 ADT 스택에 요소를 추가하거나 삭제하는 연산, 현재 스택 상태를 검사하는 연산들로 구성됩니다. create(size) ::= 크기가 size인 스택 생성 is_full(s)..

재귀란? 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다. 재귀 함수를 선언할 때 선언한 함수 자신을 호출하는 것입니다. 그렇게 되면 재귀 함수를 한 번 만 실행해도 함수 자신을 호출하므로 또 다시 함수가 실행되고.. 를 계속 반복하는 것이 바로 재귀(recursion)입니다. 재귀의 대표적인 예시가 바로 팩토리얼(factorial) 함수인데, 코드로 살펴봅시다. int factorial(n) { if(n to (from은 경유)로 옮김 hanoi(via, from, to, n - 1); } } 응용: [백준 11729] 하노이 탑 이동 순서 이를 응용하여 아래와 같은 문제를 풀 수 있습니다. https://www.acmicpc.net/problem/11729 1172..

추상 자료형 (ADT; Abstract Data Type) 자료형 말 그대로 데이터의 종류입니다. 프로그래밍 언어가 기본적으로 제공합니다. ex) 정수, 실수, 문자, 배열 등… 추상 자료형 실제적인 구현으로부터 분리되어 정의된 자료형입니다. ex) 자료구조 특징 구현과 분리해 자료형을 추상적(수학적)으로 정의했습니다. 데이터나 연산이 무엇(what)인지는 정의되지만 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않습니다. 자바에서 사용하는 interface도 추상 자료형을 나타내기 위한 방법입니다. ::= ’~으로 정의된다’를 의미합니다. 예시 1. ADT 표기 자료구조 중 스택을 ADT로 표기해보겠습니다. ::= 기준으로, l-value에는 정의할 메소드명을 기입해주고 r-value에는 어떻..