바킹독의 실전 알고리즘 : 스택의 활용(수식의 괄호 쌍)

수식의 괄호 쌍이란?코테에서 한 번쯤 봤을 법한 문제이다. (())()()))(()()())(()위처럼 있다고 할 때 괄호 쌍이 모두 있는지 판단하는 문제이다. 일단 안쪽부터 짝 맞추기를 해본다면 첫번째 입력만 맞다는 것을 알 수 있다. 괄호가 여러 종류일 때는 단순히 괄호 개수만으로 판별하기 어렵다. ({(){}})이러한 유형은 스택을 사용한다면 빠른 시간복잡도로 풀어낼 수 있다.

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 덱

정의와 성질양쪽 끝에서 삽입 삭제 전부 가능한 자료구조이다. Double Ended Queue라고 큐의 진화형 느낌이다. 큐의 성질원소의 추가가 O(1)원소의 제거가 O(1)제일 앞/뒤 원소 확인이 O(1)앞뒤 외의 원소들은 원칙적으로 확인/변경 불가능 다만 STL deque에서는 인덱스로 원소 접근이 가능하다. 기능과 구현const int MX=100005;int dat[2*MX+1];int head=MX, tail=MX;void push_front(int x){ dat[--head]=x;}void push_back(int x){ dat[tail++]=x;}void pop_front(){ head++;}void pop_back(){ tail--;}int front(){ ret..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 큐

정의와 성질큐는 FIFO 바로 나와주면 된다. 큐의 성질원소의 추가가 O(1)원소의 제거가 O(1)제일 앞/뒤 원소 확인이 O(1)앞뒤 외의 원소들은 원칙적으로 확인/변경 불가능 추가 -rear제거 -front로 보통 나타낸다. 기능과 구현스택 어렵지 않았으니까 걍 내가 구현해보자. const int MX = 100005;int dat[MX];int tail=0; // 추가 int head=0; // 제거void push(int x){ dat[tail++]=x;}void pop(){ head++;}int front(){ return dat[head];}int back(){ return dat[tail-1];}제미나이한테 던졌더니 길이 제한 생각 안 하냐고 혼났다. 그치 대기큐 같은 ..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 스택

정의와 성질스택은 LIFO이다. 큐, 덱, 스택 같은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한된 자료구조를 Restricted Structure라고 부른다. 스택의 성질원소의 추가 O(1)원소의 제거 O(1)제일 상단의 원소 확인 O(1)나머지 원소들의 확인/변경 원칙적으로 불가능 기능과 구현const int MX=1000005;int dat[MX];int pos=0;일단 여기서 원소를 담은 큰 배열과 인덱스를 저장할 변수 한 개만 있으면 구현이 가능하다. pos는 원소의 개수이자 추가할 때 삽입해야 하는 인덱스를 의미한다. #include using namespace std;const int MX=1000005;int dat[MX];int pos=0;void push(int x){ dat[..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 연결 리스트

정의와 성질연결 리스트의 성질 k번째 원소를 확인/변경하기 위해 O(k)이미 정한 위치에 추가 및 제거는 O(1)메모상에 연속된 데이터는 아니라서 cache hit rate는 낮고, 할당은 쉬움 연결리스트 종류단일 연결 리스트 이중 연결 리스트 : 양방향으로 연결되어 있어서 이전 이후 원소 주소를 둘 다 들고 있다. 원형 연결 리스트 : 사이클 돈다 생각하면 편하다. 기능과 구현struct NODE { struct NODE *prev, *next; int data;};손코딩 문제 1원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법? 효율적으로 구하라 -> 시간복잡도와 공간복잡도를 생각해봐야 한다. 동일한 노드가 나올 때까지 계속 다음 노드로 ..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 배열

정의와 성질배열 : 메모리 상에 원소를 연속하게 배치한 자료구조 O(1)에 k번째 원소 확인 가능 오버헤드 거의 없음 hit rate 높음 -> CS 확실히 중요하네.. 연속된 자료구조이기 때문에 할당에 제약이 있다 -> 메모리상에도 연속적 기능과 구현#include using namespace std;void insert(int idx, int num, int arr[], int& len){ for(int i=len;i>idx;i--) // i가 길이부터 시작이니까 arr[i]=arr[i-1]; //i-1이 맞는 위치(?) 맞는 배열의 인덱스, 1번째 원소 인덱스 번호는 0 arr[idx]=num; //그리고 넣어준다. len++; //len도 하나 늘어난다. }void erase(int..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.