[복습] 알고리즘 기초 1/2 200-자료구조1

Leejaegun·2025년 10월 24일

코딩테스트 시리즈

목록 보기

46/49

1. stack

https://www.acmicpc.net/problem/10828
stack은 기본적인 자료구조 형태이다.

import sys
input = sys.stdin.readline
class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, x):
        self.stack.append(x)
    
    def empty(self):
        return 1 if len(self.stack) == 0 else 0 #문제에서 요구
    
    def pop(self):
        if self.empty():
            return -1
        else:
            return self.stack.pop()
    
    def size(self):
        return len(self.stack)
    
    def top(self):
        if self.empty():
            return -1
        else:
            return self.stack[-1]

N = int(input())
s = Stack()
for _ in range(N):
    command = input().strip().split()
    if command[0] == "push":
        s.push(int(command[1]))
    elif command[0] == "pop":
        print(s.pop())
    elif command[0] == "size":
        print(s.size())
    elif command[0] == "empty":
        print(s.empty())
    elif command[0] == "top":
        print(s.top())

스택은 LIFO (Last In, First Out) 자료구조로,
마지막에 들어간 원소가 가장 먼저 나오는 구조를 말합니다.

⚠️ 실수한 부분과 원인

(1) `empty(self, x)`

→ ❌ empty()는 인자를 받을 필요가 없음
→ self는 객체 자신을 의미하므로, 메서드 안에서 self.stack에 접근 가능.
따라서 외부에서 추가 인자(x)를 받을 필요가 없다.

정상:

def empty(self):
    return 1 if len(self.stack) == 0 else 0

(2) `.split()`과 `.strip()` 순서 오류

→ ❌ input().split().strip()은 리스트에 strip()을 적용하려고 해서 에러 발생
→ split()이 먼저 실행되면 문자열이 아니라 리스트를 반환하기 때문.

정상:

command = input().strip().split()

→ strip()으로 공백 제거 후 split()으로 단어 나누기

(3) `s = []` 로 스택 선언

→ ❌ 이렇게 하면 단순 리스트 객체가 되어,
push, pop, empty 등 Stack 클래스 메서드를 쓸 수 없음.

정상:

s = Stack()

→ Stack 클래스의 인스턴스로 생성해야 s.push(), s.pop() 등을 호출 가능.

🧠 추가 개념: self란 무엇인가?

self는 클래스 내부에서 자신의 인스턴스를 참조하는 변수이다.
즉, Stack 클래스 안에서 self.stack은 해당 객체의 내부 리스트를 의미한다.

예를 들어:

s1 = Stack()
s2 = Stack()

s1.push(10) → s1.stack = [10]
s2.push(20) → s2.stack = [20]

각 객체가 독립적으로 관리되는 이유는,
self가 각 인스턴스를 구분하기 때문이다.

📚 정리 요약

항목	잘못된 코드	수정된 코드	원인
empty 메서드	`def empty(self, x)`	`def empty(self)`	인자 불필요
입력 처리	`input().split().strip()`	`input().strip().split()`	실행 순서 오류
Stack 생성	`s = []`	`s = Stack()`	클래스 인스턴스 미생성
반환 형식	`True / False`	`1 / 0`	문제 요구 출력 형식 불일치

클래스를 쓸 때 가장 중요한 것은
“상태(self)”와 “행동(method)”를 구분해 관리하는 것입니다.
이번 예제는 그 원리를 가장 단순하고 명확하게 보여주는 좋은 연습

2. 단어 뒤집기

https://www.acmicpc.net/problem/9093

N = int(input())
words = []
for _ in range(N):
    words.append(list(input().split()))


for i in range(len(words)):
    for j in range(len(words[i])):
        reverse_word = "".join(str(words[i][j])[::-1])
        words[i][j] = reverse_word
for i in range(len(words)):
    print(" ".join(words[i]))

이 코드를 보면 2차원 행렬을 구하고 거기서 [::-1] 를 해서 풀었다 하지만 이는 이해하기도 어렵고 비효율적인거 같다.

다른 사람의 코드를 보니

r = int(input())
for i in range(r):
    x = input().split()
    j = []
    for e in x:
        f = e[::-1] 
        j.append(f)
    print(' '.join(j))

다음과 같이 f라는 임시 변수를 만들어서 j 라는 list 에 넣고 그냥 마지막에 " ".join 하였다..
이와 같이 좀 가독성있게 짜는 연습이 필요할 듯싶다.

3. 큐

https://www.acmicpc.net/problem/10845

class Queue:
    def __init__(self):
        self.queue = []
    
    def push(self, x):
        self.queue.append(x)
    
    def empty(self):
        return 1 if len(self.queue) == 0 else 0
    
    def size(self):
        return len(self.queue)
   
    def pop(self):
        if self.empty():
            return -1
        else:
            return self.queue.pop(0)
        
    def front(self):
        return self.queue[0] if not self.empty() else -1
    
    def back(self):
        return self.queue[-1] if not self.empty() else -1
    
import sys
input = sys.stdin.readline
N = int(input())
q = Queue()
for _ in range(N):
    command = input().split()
    if command[0] == "push":
        q.push(int(command[1]))
    elif command[0] == "empty":
        print(q.empty())
    elif command[0] == "size":
        print(q.size())
    elif command[0] == "pop":
        print(q.pop())
    elif command[0] == "front":
        print(q.front())
    elif command[0] == "back":
        print(q.back())

🧱 큐(Queue) 정리

큐(Queue) 는
FIFO (First In, First Out) 구조, 즉 먼저 들어온 데이터가 먼저 나가는 자료구조입니다.
이에 반해 스택(Stack) 은 LIFO (Last In, First Out) 구조입니다.

✅ 핵심 메서드 동작 원리

메서드	역할	동작 방식
`push(x)`	큐의 맨 뒤에 원소 추가	`append(x)` 사용
`pop()`	큐의 맨 앞 원소 제거 및 반환	`pop(0)` 사용
`front()`	맨 앞 원소 확인	`self.queue[0]`
`back()`	맨 뒤 원소 확인	`self.queue[-1]`
`size()`	큐에 들어있는 원소 개수	`len(self.queue)`
`empty()`	비어있으면 1, 아니면 0	`1 if len(self.queue)==0 else 0`

⚠️ 실수 및 교정

(1) `self.empty` vs `self.empty()`

self.empty → 메서드 그 자체(함수 객체) 를 가리킴
self.empty() → 메서드를 호출하고 반환값(True/False 혹은 1/0) 을 얻음

즉,

if self.empty:

는 항상 참(True)로 인식되어 잘못된 로직이 됩니다.
올바르게는

if self.empty():

로 호출해야 합니다.

(2) `.pop()`의 기본 동작 방향

list.pop()은 리스트의 맨 뒤 요소를 제거하고 반환합니다.
즉, 스택(LIFO) 구조와 동일한 동작입니다.
큐처럼 맨 앞 요소를 제거하려면,
```
self.queue.pop(0)
```
을 사용해야 합니다.

참고: .pop(1)은 두 번째 요소를 제거합니다.
인덱스 0이 맨 앞이므로, 큐의 맨 앞을 빼려면 반드시 .pop(0)이어야 합니다.

🧠 큐 vs 스택 비교

구분	큐(Queue)	스택(Stack)
구조	FIFO (선입선출)	LIFO (후입선출)
추가(push)	뒤에서 삽입 (`append`)	위에 삽입 (`append`)
제거(pop)	앞에서 제거 (`pop(0)`)	위에서 제거 (`pop()`)
예시	대기줄, 프린터 대기열	호출 스택, 실행 기록

📘 요약

self.empty() — 메서드는 괄호로 호출해야 값이 반환된다.
.pop()은 기본적으로 맨 뒤에서 삭제하므로, 큐에서는 .pop(0)을 사용해야 한다.
큐는 FIFO, 스택은 LIFO 구조로 동작한다.

이 문제를 통해 배운 핵심은

“메서드 호출의 형태와 자료구조의 방향성이 프로그램의 논리를 결정한다.”
입니다.

4. 괄호

https://www.acmicpc.net/problem/9012

import sys
input = sys.stdin.readline
class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return len(self.stack) == 0

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        return -1

    def top(self):
        if not self.isEmpty():
            return self.stack[-1]
        return -1

        
stack = Stack()

N = int(input())
for _ in range(N):
    parent = input().strip()
    stack = Stack()
    valid = True
    
    for ch in parent:
        if ch == "(":
            stack.push(ch)
        elif ch == ")":
            if stack.isEmpty():
                valid = False
                break
            stack.pop()
    if not stack.isEmpty():
        valid = False
    print("YES" if valid else "NO")

배운점
(1) 하나 -> 하나 해야할 때는 그냥 input.strip() 으로 개행만 제거해서 하자.
(2) stack 에서 isEmpty() 는 그냥 return len(self.stack) == 0 이렇게 하면 된다.
(3) valid 라는 변수를 두어가지고 풀어보자.
-> 여기서 논리적 사고력이 중요한데, 나는 지금 이게 부족하다. 세로 모양의 통이 있을때, 괄호가 각각 들어오면 어떻게 되는지 머릿속에 생각해서 풀어보자.

5. 스택수열

https://www.acmicpc.net/problem/1874

import sys
input = sys.stdin.readline

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self,x):
        self.stack.append(x)
    
    def isEmpty(self):
        return len(self.stack) == 0
    
    def pop(self):
        return self.stack.pop() if not self.isEmpty() else -1
    
    def top(self):
        return self.stack[-1] if not self.isEmpty() else -1
    

n = int(input())
stack = Stack()
result = []
next_num = 1

for _ in range(n):
    target = int(input())
    while next_num <= target:
        stack.push(next_num)
        result.append("+")
        next_num += 1
        
    if stack.top() == target:
        stack.pop()
        result.append("-")
    else:
        print("NO")
        sys.exit(0)

print("\n".join(result))

코드를 보면 되게 간단하게 나는 이걸 못 풀었따..
배운점
(1) target 를 만들어서 next_num += 1 하면서 pop 활용..
=> 아직 stack 에 익숙하지 않은것 같다. 알고리즘기초1이거 계속 반복 학습하면서 머릿속에 남기도록 하자.

6.에디터

https://www.acmicpc.net/problem/1406

import sys
input = sys.stdin.readline

class Stack:
    def __init__(self):
        self.left = []
        self.right = []

    def L(self):
        if self.left:
            self.right.append(self.left.pop())
    
    def D(self):
        if self.right:
            self.left.append(self.right.pop())
        
    def B(self):
        if self.left:
            self.left.pop()
        
    def P(self,x):
        self.left.append(x)


string = input().strip()
stack = Stack()
for ch in string:
    stack.left.append(ch)
    
M = int(input())

for _ in range(M):
    command = input().split()
    if command[0] == "P":
        stack.P(command[1])
        
    elif command[0] == "L":
        stack.L()
        
    elif command[0] == "D":
        stack.D()
        
    elif command[0] == "B":
        stack.B()
        

print("".join(stack.left + list(reversed(stack.right))))

🧠 핵심 아이디어

두 개의 스택(left, right)을 사용해 커서 왼쪽/오른쪽 문자를 각각 관리한다.
- L: 왼쪽 스택에서 pop → 오른쪽 스택에 append
- D: 오른쪽 스택에서 pop → 왼쪽 스택에 append
- B: 왼쪽 스택에서 pop (문자 삭제)
- P x: 왼쪽 스택에 append(x)

📚 배운 점 정리

두 스택 구조 활용
- 커서 이동을 O(1)에 구현할 수 있다.
- 문자열 중간 삽입/삭제를 직접 하지 않고 스택 이동만으로 해결.
조건문 사용 습관화
- 예: if self.left: 또는 if self.right:
- 비어 있을 때 pop() 하면 에러 나므로 반드시 조건 체크.
생성자와 인자 관계 이해
- Stack(string)처럼 인자를 전달하려면
  __init__(self, string)으로 정의되어야 한다.
- 현재는 __init__이 인자를 받지 않으므로 Stack()으로 생성.
.join() 사용 시 주의
- join()은 하나의 iterable만 받는다.
- 따라서 "".join(left + list(reversed(right))) 형태로 사용해야 한다.
- join(left, right)처럼 두 개를 넣으면 TypeError 발생.

7. 요시푸스문제

https://www.acmicpc.net/problem/1158

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class DoublyCircularLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = new_node
            new_node.prev = new_node
        else:
            tail = self.head.prev
            tail.next = new_node
            new_node.prev = tail
            new_node.next = self.head
            self.head.prev = new_node
        self.size += 1

    def remove(self, node):
        if self.size == 0:
            return None
        if self.size == 1:
            val = node.data
            self.head = None
            self.size = 0
            return val, None

        val = node.data
        node.prev.next = node.next
        node.next.prev = node.prev
        if node == self.head:
            self.head = node.next
        self.size -= 1
        return val, node.next

    def __len__(self):
        return self.size


# 실행부
N, K = map(int, input().split())
dll = DoublyCircularLinkedList()
for i in range(1, N + 1):
    dll.append(i)

result = []
curr = dll.head

while len(dll) > 0:
    for _ in range(K - 1):
        curr = curr.next
    val, curr = dll.remove(curr)
    result.append(val)

print("<" + ", ".join(map(str, result)) + ">")

🧩 요세푸스 문제 학습 정리

1️⃣ 처음의 착각

문제를 처음 봤을 때, “원형 구조니까 연결 리스트를 쓰면 쉽겠다” 라고 생각했다.
하지만 실제로 구현해보니 전혀 그렇지 않았다.
단방향 연결 리스트로는 다음과 같은 문제들이 있었다.

append() 구현의 어려움
- 원형 연결 구조를 만들기 위해 tail.next = head 를 어떻게 유지할지 감을 잡기 힘들었다.
- 새 노드를 추가할 때마다 head와 tail의 연결 관계를 계속 관리해야 했다.
remove() 구현의 복잡성
- 단방향 구조에서는 prev 포인터가 없기 때문에,
  특정 노드를 지우려면 항상 “이전 노드를 찾아야” 했다.
- 결국 매번 리스트 전체를 한 바퀴 돌면서 prev.next == curr 인 지점을 찾아야 했고,
  삭제 과정이 지나치게 복잡해졌다.
단방향 구조의 근본적인 한계
- 탐색이 한쪽 방향으로만 가능하니,
  삭제·삽입·역방향 탐색이 모두 비효율적이었다.

2️⃣ 해결 방법 — 양방향 원형 연결 리스트로 전환

이 문제를 해결하기 위해 양방향 연결 리스트(Doubly Circular Linked List) 로 구조를 바꾸었다.
각 노드가 next 와 prev 를 모두 가지게 하여,
이전 노드에 직접 접근할 수 있도록 만들었다.

그 결과:

append(): tail을 바로 찾을 수 있으므로 연결이 단순해졌다.
remove(): node.prev 와 node.next 를 직접 조작해서
이전 노드 탐색 없이 O(1)에 삭제 가능해졌다.
코드의 가독성과 안정성이 모두 향상되었다.

3️⃣ 배운 점 요약

항목	단방향 리스트	양방향 리스트
연결 구조	한 방향 (next)	양방향 (next, prev)
이전 노드 접근	불가능 (탐색 필요)	O(1)
삭제 구현	복잡 (탐색 필수)	간단 (포인터 조작만)
요세푸스 문제 구현 난이도	높음	낮음
결론	구조는 단순하지만 실전 구현엔 비효율	구현은 길지만 논리적으로 명확

💡 최종 깨달음

“자료구조를 직접 구현하는 건 단순히 문제를 푸는 게 아니라, 메모리 구조를 이해하는 훈련이다.”
단방향 연결 리스트는 기본 개념을 익히는 데 좋지만,
실전에서는 양방향 구조가 훨씬 명료하고 강력하다.

(2) 그리고 list 로 간단하게 푸는 방법이 있다.

N, K = map(int, input().split())
people = list(range(1, N + 1))
result = []
idx = 0

while people:
    idx = (idx + K - 1) % len(people)
    result.append(people.pop(idx))

print("<" + ", ".join(map(str, result)) + ">")

8. 덱

https://www.acmicpc.net/problem/10866

import sys
from collections import deque
class Deque:
    def __init__(self):
        self.deque = deque()
    
    def push_front(self,x:int) -> None:
        self.deque.appendleft(x)
    
    def push_back(self,x:int) -> None:
        self.deque.append(x)
    
    def pop_front(self) -> int:
        return self.deque.popleft() if self.deque else -1
    
    def pop_back(self) -> int:
        return self.deque.pop() if self.deque else -1
    
    def size(self) -> int:
        return len(self.deque)
    
    def empty(self) -> bool:
        return 1 if len(self.deque) ==0 else 0
    
    def front(self) -> int:
        return self.deque[0] if not self.empty() else -1
    
    def back(self) -> int:
        return self.deque[-1] if not self.empty() else -1


input = sys.stdin.readline
N = int(input())
deque = Deque()
for _ in range(N):
    commands = input().split()
    if commands[0] == "push_front":
        deque.push_front(int(commands[1]))
    elif commands[0] == "push_back":
        deque.push_back(int(commands[1]))
    elif commands[0] == "size":
        print(deque.size())
    elif commands[0] ==  "empty":
        print(deque.empty())
    elif commands[0] == "front":
        print(deque.front())
    elif commands[0] == "back":
        print(deque.back())
    elif commands[0] == "pop_front":
        print(deque.pop_front())
    elif commands[0] == "pop_back":
        print(deque.pop_back())

🧩 덱(Deque) 문제 구현하면서 배운 점 정리

1️⃣ `deque` 임포트 방법

deque 는 파이썬 내장 모듈 collections 안에 있음.
사용하려면 다음과 같이 가져와야 함:
```
from collections import deque
```
이후 dq = deque() 로 덱 객체 생성.

2️⃣ `dq = deque()` vs `dq = deque` 차이

dq = deque → 클래스 자체를 변수에 저장 (❌)
dq = deque() → 실제 덱 객체(인스턴스) 생성 (✅)
즉, 괄호 () 가 빠지면 메서드 호출 불가 (append, pop 등 에러 발생).

3️⃣ `self.deque` vs `self.deque()`

self.deque : deque 객체 그 자체
self.deque() : 함수 호출처럼 실행하려는 시도
→ TypeError: 'collections.deque' object is not callable 에러 발생.

정리하면,

덱은 함수가 아니라 자료구조 객체니까 괄호 붙이면 안 된다.

4️⃣ `sys.stdin.readline` 사용 시 괄호 주의

올바른 입력 최적화 방식:
```
import sys
input = sys.stdin.readline
```
❌ input = sys.stdin.readline() 이렇게 괄호를 붙이면
input 에 문자열 하나가 들어가버려서
나중에 input() 호출 시 TypeError 발생.

✅ 요약

항목	잘못된 예	올바른 예
`deque` 임포트	`import deque`	`from collections import deque`
덱 생성	`dq = deque`	`dq = deque()`
객체 접근	`self.deque()`	`self.deque`
입력 함수	`input = sys.stdin.readline()`	`input = sys.stdin.readline`

Leejaegun

Lee_AA

이전 포스트

[복습] 파이썬 배우기 50~100

다음 포스트

[복습] 알고리즘 기초 1/2 200-자료구조1

코딩테스트 시리즈

1. stack

⚠️ 실수한 부분과 원인

(1) `empty(self, x)`

(2) `.split()`과 `.strip()` 순서 오류

(3) `s = []` 로 스택 선언

🧠 추가 개념: self란 무엇인가?

📚 정리 요약

2. 단어 뒤집기

3. 큐

🧱 큐(Queue) 정리

✅ 핵심 메서드 동작 원리

⚠️ 실수 및 교정

(1) `self.empty` vs `self.empty()`

(2) `.pop()`의 기본 동작 방향

🧠 큐 vs 스택 비교

📘 요약

4. 괄호

5. 스택수열

6.에디터

🧠 핵심 아이디어

📚 배운 점 정리

7. 요시푸스문제

🧩 요세푸스 문제 학습 정리

1️⃣ 처음의 착각

2️⃣ 해결 방법 — 양방향 원형 연결 리스트로 전환

3️⃣ 배운 점 요약

💡 최종 깨달음

8. 덱

🧩 덱(Deque) 문제 구현하면서 배운 점 정리

1️⃣ `deque` 임포트 방법

2️⃣ `dq = deque()` vs `dq = deque` 차이

3️⃣ `self.deque` vs `self.deque()`

4️⃣ `sys.stdin.readline` 사용 시 괄호 주의

✅ 요약

[복습] 파이썬 배우기 50~100

[복습] Python 배우기 100~150

0개의 댓글

[복습] 알고리즘 기초 1/2 200-자료구조1

코딩테스트 시리즈

1. stack

⚠️ 실수한 부분과 원인

(1) empty(self, x)

(2) .split()과 .strip() 순서 오류

(3) s = [] 로 스택 선언

🧠 추가 개념: self란 무엇인가?

📚 정리 요약

2. 단어 뒤집기

3. 큐

🧱 큐(Queue) 정리

✅ 핵심 메서드 동작 원리

⚠️ 실수 및 교정

(1) self.empty vs self.empty()

(2) .pop()의 기본 동작 방향

🧠 큐 vs 스택 비교

📘 요약

4. 괄호

5. 스택수열

6.에디터

🧠 핵심 아이디어

📚 배운 점 정리

7. 요시푸스문제

🧩 요세푸스 문제 학습 정리

1️⃣ 처음의 착각

2️⃣ 해결 방법 — 양방향 원형 연결 리스트로 전환

3️⃣ 배운 점 요약

💡 최종 깨달음

8. 덱

🧩 덱(Deque) 문제 구현하면서 배운 점 정리

1️⃣ deque 임포트 방법

2️⃣ dq = deque() vs dq = deque 차이

3️⃣ self.deque vs self.deque()

4️⃣ sys.stdin.readline 사용 시 괄호 주의

✅ 요약

[복습] 파이썬 배우기 50~100

[복습] Python 배우기 100~150

0개의 댓글

(1) `empty(self, x)`

(2) `.split()`과 `.strip()` 순서 오류

(3) `s = []` 로 스택 선언

(1) `self.empty` vs `self.empty()`

(2) `.pop()`의 기본 동작 방향

1️⃣ `deque` 임포트 방법

2️⃣ `dq = deque()` vs `dq = deque` 차이

3️⃣ `self.deque` vs `self.deque()`

4️⃣ `sys.stdin.readline` 사용 시 괄호 주의