데굴데굴

⚙️ 오늘 배운 주제 자료구조 - 스택, 큐 🐹 오늘의 기분 섹션 4에 들어왔다. 이번 유닛에서는 자료구조를 배우는데 그 첫 타자는 스택과 큐였다. 독학할 때 파이썬으로 공부해본 적이 있어서 개념 자체는 크게 어렵게 느껴지지 않았다. 자바스크립트 class로 구현해보고 두 자료구조를 응용한 여러 문제를 푸는 것이 어려웠다. 브라우저 스택이랑 박스 포장까지는 페어분과 고민하면서 나름 빠르게 풀었는데 프린터 큐에서 완전 막혀버렸다. 한 시간 정도 고민하다가 결국 레퍼런스를 봤는데 더 이해가 안 됐다 (?) 라이브세션에서 알려주신 코드가 더 이해가 잘 됐다. 올려주신 레퍼런스 보면서 풀이 뜯어보고 혼자 다시 풀어보려고 한다. 🗝 키워드 스택, 큐, 후입선출, 선입선출, push, pop, enqueue, de..

2164번: 카드2 (acmicpc.net) 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 입력이 50만까지 주어지기 때문에 시간 초과에 유의하여 풀어야 한다. 처음에는 리스트로 해결했는데 답은 맞았지만 시간 초과가 발생하여 deque 라이브러리로 해결했다. 아래 페이지를 보면 deque의 삽입/삭제 연산 시간 복잡도는 O(1), 리스트는 O(n)이라 설명하고 있다. 리스트는 삽입/삭제 연산에서 비워진 곳을 메우기 위해, 혹은 새로 삽입된 값의 자리를 만들어 주기 위해 원소가 추가로 이동하지만 deque는 ..

10845번: 큐 (acmicpc.net) 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 분명 맞게 푼 것 같았는데 답과는 다르게 출력돼서 뭐지..? 했는데 queue를 for문 내에 정의한 걸 디버깅하다가 깨달았다^^ 그리고 pop을 수행할 때에도 리턴한 값을 출력하기 위해서 print()를 씌워줘야 한다. 비슷한 스택 문제를 풀어봤어서 비교적 수월하게 풀 수 있었다. 이 문제도 역시 n의 입력이 1부터 10000까지 주어지기 때문에 빠른 처리를 위해서 sys 모듈을 사용해야 한다. n도 명..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=nqCNk_DmPio&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11 앞서 배운 스택이 후입선출의 구조였다면, 큐는 선입선출(First-in First-Out)의 구조이다. 먼저 들어온 것이 먼저 나간다. 그래서 선착순 자료구조라고도 한다. 파이썬 리스트로 큐 구현하기 1 enqueue(value): 큐의 가장 오른쪽 끝에 값을 삽입 dequeue(): 큐의 가장 왼쪽 값을 삭제 후 리턴 front(): 큐의 가장 왼쪽 값을 리턴 len(): 큐의 저장된 값의 개수 isEmpty(): 큐가 비었는지 알려줌 class Queue: def __init__(se..