자료구조

문제 : 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함수라고 한..

이번 포스팅에선 배열 (Array)에 대해 살펴볼 것이다. 저번 포스팅에서 필요할 때마다 메모리를 할당받아 데이터를 저장하는 방법인 연결 리스트(Linked List)를 다뤘으니 이번 포스팅에선 미리 메모리를 확보한 다음 연속된 공간에 저장하는 방법인 배열에 대해 알아보자. 배열은 자료구조를 배우기 이전에도 컴퓨터 과학을 공부했다면 다 들어봤을 만한 기초적이고 중요한 것이다. 배열이란? 배열(array)은 같은 타입의 변수들로 이루어진 유한 집합으로 정의된다. 배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다. 배열은 같은 종류의 데이터를 많이 다뤄야 하는 경우에 사용할 수 있는 가장 기본적인 자료구조이다. 배열의 탐색 배열은..