후회가 없도록

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

우선, 자료구조란 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공하는 형태를 의미한다. 자료구조는 추상적 자료형(자료와 그 자료에 대한 연산을 개념적으로 정의만 한 것)을 구체적으로 구현한 결과라고 표현할 수도 있다. 즉, 리스트(파이썬의 자료 type 중 리스트와는 다름), 스택, 큐, 트리 등의 명칭과 그 구조의 개념은 추상적 자료형에 속하고, 이를 실제로 사용할 수 있도록 모듈, 클래스 등을 통해 구현한 것 또는 이를 구현하는 도구가 되는 것(배열, 연결 리스트 등)을 자료구조라고 생각하면 된다. 이 글에는 대표적인 자료구조(배열, 연결 리스트)의 구조 개념, 장단점과 함께 이를 구현한 코드를 정리했다. 1. 배열(Array) 배열은 절대적인 순서에서 인덱스(위치)를 통해 조회..

최근 파이썬을 통해 백준 알고리즘 문제를 풀이하던 중, 리스트로 2차원, 3차원 형태를 만들어야 하는 부분이 있었다. 재귀 함수를 통해 원소 하나하나씩 값을 구하고, 해당 리스트에 저장해야 했다. 나는 아래와 같은 방식으로 리스트를 생성하고, 값을 저장했다. val = [[[0] * 2] * 2] * 2 val[0][0][1] = 7 이를 프롬프트로 진행했을 때, 위와 같은 결과가 되었다. 슬라이싱을 한 적도, 값을 여러 개 지정하려던 의도도 없었는데, 마치 슬라이싱으로 값을 수정한 것처럼 각 리스트의 1번째 원소가 모조리 저장되었다. 솔직히 이전에도 종종 이런 경우가 있었고, 그때마다 결국 그냥 리스트 인덱싱이 아닌, append 함수나 딕셔너리 타입 등을 이용해서 문제를 해결했다. 그러던 중 우연히 ..