Stack

문제 : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 어떤 문제인가? 문제에 특별한 어려움은 없는 문제였다. 레이저를 기준으로 잘린 쇠막대기의 개수를 구하면 된다. 접근 방법 문제를 읽고 고민 없이 바로 stack을 사용하기로 결정했다. 입력받은 문자열의 index를 하나하나 살펴보면서 각각에 경우에 따른 처리를 해주면 된다. int cnt = 0; stack stick; 잘린 쇠막대기의 개수를 셀 cnt를 0으로 초기화해준다. 괄호를 넣어둘 char..

스택이란? 스택은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 스택은 입구와 출구가 같은 선형 구조이다. 따라서 가장 먼저 입구에 들어간 자료가 가장 늦게 출구로 나갈 수 있다. 프링글스 통을 생각하면 이해가 쉽다. 처음 프링글스 통이 채워질 때 가장 먼저 들어간 프링글스가 가장 마지막에 우리들의 손에 집혀 입으로 들어온다. 이를 후입 선출(또는 LIFO, last in first out) 구조라고 한다. 스택에서의 접근은 항상 마지막 원소에서만 일어난다. => 제일 위에 있는 프링글스를 잡는다. 이 마지막 원소를 top이라고 한다. 스택의 탐색 앞서 포스팅한 배열과 연결 리스트가 자료구조를 구현하는 기본적인 방법이다. 보통 스택의 탐색을 top함수라고 한..