자료구조

[C++] 백준 2504번 괄호의 값

2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 스택 자료구조 문제. 구현력을 필요로 하는 노가다 문제이다. 문제 분석 스택 하나에 입력들을 넣어놨다가, 괄호가 닫히는 경우를 처리해주면 된다. 나같은 경우에는 다음과 같이 처리했다. 현재 입력이 '(' 또는 '['인 경우 -> 그냥 스택에 넣어준다. 현재 입력이 ')' 또는 ']'인 경우 -> 만일 스택의 위에 있는 게 숫자들일 경우, 다 더해준 후 *2 / *3을 해준다. 스택의 위에 있는 게 '(' / '[' 일 경우 '(' / '['를 빼내고 2를 넣어..

[C++] 백준 5430번 AC

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문자열 파싱, 자료구조를 이용해서 풀 수 있는 문제. 디테일에서 놓친 부분들이 많아서 틀렸습니다를 많이 받았다. 문제풀이 조건을 다음과 같이 해석해서 풀었다. '덱'을 사용해서 풀고, 현재 방향이 front인지 back인지를 저장한다. 시작의 경우 방향은 front가 된다. 'R' 명령어가 들어왔을 경우 : front / back 방향을 반대로 전환한다. 'D' 명령어가 들어왔을 경우 : 현재 덱에서 방향에 있는 수를 하나 pop한다. 이 때 덱이 비어있으면 error가 발생하도록 한다. 코드 전문 /* * 백준 54..

[C++] 백준 17298번 오큰수

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료 구조 - 스택 문제. 알고리즘 분류를 알고 풀어서 쉽게 접근할 수 있었다. 알고리즘 분류를 모르고 풀면 풀 수 있었을지 모르겠다. 문제풀이 다음과 같은 생각을 하고 풀었다. 큐를 두 개 만든다. 하나는 입력을 받아놓는 큐, 하나는 큐에서 꺼낸 수를 저장해놓는 큐. 입력을 받아놓는 큐에서 하나씩 꺼내보며 꺼낸 수를 저장해놓는 큐의 맨 위와 비교한다. 만일 큐가 비어있다면 오큰수가 없다는 뜻이다. 큐가 비어있지 않을 때에는 현재 수와 저장해놓은 큐의 맨 위의 수를 비교한다..

[C++] 백준 2493번 탑

스택을 이용해서 푸는 문제. 우선순위 큐로도 풀 수 있는 문제다. 자료구조의 기본적인 문제라고 한다. 평이 좋았던 문제였다. 문제풀이 탑들은 왼쪽 방향으로 레이저 신호를 보낸다. 만일, 자신의 왼쪽에 자신의 높이보다 큰 탑이 있을 경우에, 그 탑이 자기 자신의 레이저 신호를 받는 탑이 된다. 레이저 신호는 하나의 탑만 수신 가능하다. 즉, 스택, 우선순위 큐를 이용해서 탑의 높이를 기록해두는데, 지금 내가 탐색하는 탑의 높이보다 높은 탑의 높이가 나올 때까지 pop한다. 어차피 지금 탐색하는 탑보다 낮은 높이의 탑은 필요가 없기 때문이다. 그리고 stack에 넣을 때, 해당하는 높이가 몇번째 탑인지도 기록해 주어야 한다. 예제 6 9 5 7 4를 예로 들어보자. 1. stack : empty input ..

[C++] 백준 1966번 프린터 큐

자료구조 큐를 사용해서 푸는 문제. 큐의 선입선출 구조를 이용해서 문제를 풀면된다. 문제 풀이 문제를 다 읽으면 어떤 방식으로 구현해야 하는지는 이해하기 쉽다. 테스트 케이스 중 6 0 / 1 1 9 1 1 1을 입력하게 되면 pop되는 순서를 알아보자면 최대값 9, 맨 앞 1 맨 뒤로 간다. 최대값 9, 맨 앞 1(원래 첫번째) 맨 뒤로 간다. 최대값 9, 맨 앞 9(원래 두번째) pop된다. 최대값 1, 맨 앞 1(원래 세번째) pop된다. 최대값 1, 맨 앞 1(원래 네번째) pop된다. 최대값 1, 맨 앞 1(원래 다섯번째) pop된다. 최대값 1, 맨 앞 1(원래 0번째) pop된다. 최대값 1, 맨 앞 1(원래 첫번째) pop된다. 따라서 우리가 구하고 싶은 0번째 수는 5번째에 pop되는 것..

[C++] 백준 1874번 스택 수열

자료구조를 이용해서 푸는 문제. 스택 ADT에 대한 이해가 잘 돼있다면 쉽게 머리속에 그려낼 수 있다. 접근 방법 우선 예시로 주어진 테스트 케이스 1번 [4, 3, 6, 8, 7, 5, 2, 1]을 이용해서 살펴보자. 입력은 오름차순으로 이루어지므로 1, 2, 3, ...의 순서로 입력된다. 입력을 받을때마다 다음의 상황을 고려한다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 같다면 스택에 push한 후 pop한다. 이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop해준다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 다르다면 스택에 push만 한다. 예시상황으로 한번 살펴보겠다. 1 : 스택에 push하면 스택이 { 1 }의 상황이고 수열 [4, 3, 6, ..

[C++] 백준 10773번 제로

0을 부르면 최근에 적은 값을 지우고 아니라면 값을 넣는 문제. 최근에 있는 값을 빼야한다. -> 스택 문제 스택 자료구조를 쓰면 쉽게 풀 수 있다. 쉽게 맞출 수 있는 문제라 생각한다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating an account on GitHub. github.com 코드는 위에서 확인이 가능하다.

[자료구조]3. 큐

Queue ADT, 큐 추상자료형 큐는 FIFO(First In, First Out), 선입선출 구조이다. 먼저 들어온 원소가 먼저 나간다. 원소의 삽입은 큐의 뒤에서 이루어지고, 원소의 삭제는 큐의 앞에서 이루어진다. 큐의 주요 기능은 다음과 같다. enqueue(obj) : 큐의 뒤(rear)에 원소를 삽입한다. dequeue(obj) : 큐의 앞(front)에 있는 원소를 꺼낸다. 큐의 추가적인 기능은 다음과 같다. front/top : 꺼내지 않고 큐의 맨 앞의 원소를 확인한다. size : 큐에 저장된 원소의 수를 return한다. empty : 큐가 비어있는지 확인한다. 예외처리는 QueueEmpty로 큐가 빈 상태인지 확인한다. 큐의 구현으로는 배열 혹은 링크드 리스트를 사용할 수 있다. 큐..

[자료구조]2. 스택

STACK ADT, 스택 추상자료형 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다. 삽입과 삭제가 후입선출 구조로 이루어진다. 스택의 주요 기능은 다음과 같다. push(object) : element를 삽입한다. pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다). 스택의 추가적인 기능은 다음과 같다. top() : 마지막으로 push된 element를 보여준다. size() : 저장된 elements의 수를 알려준다. empty() : 스택이 비어있는지 확인한다. 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다. Stack을 사용한 프로그램 예시에는 다음이 있다. 웹 브라우저 방문 기록 텍스트 편집기 되돌리기..

[자료구조]1. 단일 링크드 리스트, 단일 연결 리스트

자료구조란 쉽게 말해, 데이터를 저장하고 사용하기 위해 만드는 것이다. 세 가지 기본기능으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. 자료구조는 구현방법과 성능분석이 중요하다. 링크드 리스트의 특징 (배열과 비교) 배열은 주소가 연속적이지만, 링크드 리스트는 주소가 연속적이지 않다. 배열은 크기가 고정이므로 공간이 부족하거나 낭비될 수 있지만, 링크드 리스트는 크기가 가변적이므로 부족, 낭비가 없다. 배열에 비해 접근이 느리고 구현도 어렵다. 단일 링크드 리스트 단일 링크드 리스트는 node가 순차적으로 이루어져 있다. 각 노드는 값을 나타내는 element 부분과 다음 node를 가리키는 주소(포인터)로 구성된다. 맨 앞 노드를 Head라고 가리키고 맨 뒤 노드를 Tai..