후회가 없도록

문제 출처: https://www.acmicpc.net/problem/5430 1. 결과 메모리 46428KB, 시간 336ms 2. 풀이 이 문제는 우선 입력과 출력 예시를 통해 확인할 수 있겠지만, 예시처럼 입력을 받아서 원하는 형태의 숫자로 변환하는 것, 출력을 원하는 형식대로 출력하는 것이 생각보다 고민이 됐다. 그래서 아래 코드처럼 입력과 출력이 조금은 더 길다. 본격적인 문제의 아이디어는 결국 뒤집든 안 뒤집든 한쪽 끝에서 숫자를 제거한다는 점에서 떠올렸다. 만약 스택의 형태로 풀었다면, D일 때는 [1:]로 슬라이싱을, R일 때는 reverse 정렬을 하게 되는데, 이는 슬라이싱을 할 때마다 남은 길이만큼 연산(한 칸씩 앞으로 당기는 것)이 발생하고, R이 있을 때마다 정렬이 발생한다는 뜻이..

문제 출처: https://www.acmicpc.net/problem/18258 1. 결과 메모리 92936KB, 시간 1764ms 2. 풀이 이전에 풀었던 큐 문제에서 이번엔 시간제한이 추가되었다. 문제 설명에서는 시간 복잡도가 O(1)이어야 한다고 제시했다. 연결 리스트를 통한 큐는 비교적으로 삽입, 삭제 등의 연산에서 유리하다고 생각했기 때문에 이전에 연결 리스트로 구현한 큐 코드를 그대로 제출했다. 하지만 이 코드가 시간 초과가 발생했다. 최대한 메모리와 연산을 줄여서 구현한 연결 리스트와 큐인데도 시간 초과가 발생했다. 이전에 패키지 collections에서 deque라는 자료구조가 큐를 구현한 것이고, queue 라이브러리의 Queue보다도 연산이 빠르다는 것을 들었기 때문에 이번엔 deque..

문제 출처: https://www.acmicpc.net/problem/10845 1. 결과 메모리 29200KB, 시간 80ms 2. 풀이 문제에서 제시한 연산 6개를 수행할 수 있는 기본적인 자료구조 큐를 구현해보는 문제였다. 큐는 FIFO(First In First Out), 선입선출의 특징을 갖는 자료구조로써, 말 그대로 먼저 들어온 자료가 먼저 출력되는 형태이다. 현실에서는 선착순, 은행 대기줄 등의 상황을 예시로 들 수 있다. 파이썬에서 제공하는 자료 타입인 리스트(list, 자료구조인 리스트와는 다른 것)로도 구현할 수 있는데, 기본적으로 파이썬의 리스트 타입은 자료구조 중 '배열'이고, 그중에서도 기본적으로는 스택을 구현한 형태를 갖는다. append를 하면 가장 뒤에 쌓이고, pop을 하면..

자료구조는 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 자료들이 순서를 가지고 있는 연속된 자료구조를 뜻한다. 선형 구조를 갖는 대표적인 자료구조는 스택(Stack)과 큐(Queue)가 있는데, 이 글은 이 둘에 대한 개념과 구조, 구현 소스 코드 등을 정리했다. 1. 스택(Stack) 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조로써, 후입선출, LIFO(Last In First Out) 등의 성격을 갖는다. 배열, 연결 리스트 등의 자료구조로 구현할 수 있으며, 파이썬의 리스트도 거의 스택과 비슷한 방식으로 동작한다. push, pop, size, empty, top 등의 연산을 구현할 수 있으며 이를 구현한 코드와 다른 책을 참조한 소스 코드는 각각 아래 링크에 있다. 1) 간단하게 구..