코딩테스트 합격자 되기 스터디 2주차
https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9
스택
스택의 개념
- LIFO(Last In First Out), 가장 최근에 들어간 원소가 가장 먼저 나오는 자료 구조)
스택을 활용할 수 있는 문제를 알아보는 법:
- 가장 최근에 들어온 원소를 알 수 있다.
- 가장 최근에 들어온 원소 순으로 나온다.
ADT란?
- ADT(Abstract Data Type): 추상 데이터 타입의 약어
- 세부 사항을 숨기고 사용자에게 필요한 기능만 명시
- 세부 사항: 내부 자료구조, 프로그래밍 언어, 저장 공간의 크기
- 사용자에게 필요한 기능: 연산, 입력, 출력
- ADT를 사용하면?
복잡한 자료구조의 내부 구현을 감추고, 필요한 연산만 정의으로써 자료구조 동작 자체에 집중할 수 있음.
스택의 ADT
구분 정의 설명
| 연산 | boolean ifFull() | 스택에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환. 가득 차 있다면 True, 아니면 False. |
| 연산 | boolean isEmpty() | 스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환. 데이터가 하나라도 있으면 False, 아니면 True. |
| 연산 | void push(ItemType item) | 스택에 데이터를 푸시합니다. |
| 연산 | ItemType pop() | 스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환합니다. |
| 상태 | Int top | 스택에서 최근에 푸시한 데이터의 위치를 기록합니다. |
| 상태 | ItemType data(maxsize) | 스택의 데이터를 관리하는 배열. 최대 maxsize개의 데이터 관리. |
스택의 사용 예시
함수 호출
스택 동작 방식이 함수 호출 방식과 유사.
- 함수 호출 시, 현재 함수의 실행상태를 저장, 새로운 함수로 제어 이동.
! 가장 최근이라는 키워드를 계속 기억하기
웹페이지
페이지 전환 시 스택에 push, 이전 페이지로 갈 때 pop.
괄호 짝 맞추기
{, (, }, )로 이뤄진 문자열이 주어질 때, 괄호의 짝이 맞는지 확인.
<aside> ⁉️ 물론 직관적으로 봐도 알 수 있지만, 직관을 좀 더 구체화 해보기.(괄호 짝이 맞다 틀리다 판단하는 과정 뜯어보기)
</aside>
열린 괄호는 자신과 가장 가까운 닫힌 괄호와 매칭
→ 열린 괄호 바로 다음 닫힌 괄호가 나오는 경우엔 구현도 큰 문제 없음.
→ 열열 닫닫 패턴은 그럼 어떻게 처리할 것인가? (O(N^2)인 경우 대부분 문제 TLE)
- 닫힌 괄호 기준 가장 최근의 열린 괄호와 매칭되게 하면 O(N)에 가능
방법
- 여는 괄호는 push
- 닫힌 괄호가 나오면, pop 한 후에, 상쇄 여부 확인 맞는 괄호 아니면 exit 맞는 괄호면 계속 진행
- 문자열 끝까지 수행 후 스택에 남은게 없으면 success, 있으면 fail
큐
큐의 개념
- FIFO(First In First Out), 가장 먼저 들어간 원소가 가장 먼저 나오는 자료 구조.
큐의 ADT
구분 정의 설명
| 연산 | boolean ifFull() | 큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환. 가득 차 있다면 True, 아니면 False. |
| 연산 | boolean isEmpty() | 큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환. 데이터가 하나라도 있으면 False, 아니면 True. |
| 연산 | void push(ItemType item) | 큐에 데이터를 푸시합니다. |
| 연산 | ItemType pop() | 큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환합니다. |
| 상태 | Int front | 큐에서 가장 마지막에 팝한 위치 기록. |
| (가장 먼저 푸시된 원소의 위치) | ||
| 상태 | Int rear | 큐에서 최근에 푸시한 데이터의 위치 기록. |
| 상태 | ItemType data(maxsize) | 큐의 데이터를 관리하는 배열. 최대 maxsize개의 데이터 관리. |
큐의 사용 예시
줄 서기
요세푸스 문제
- N명의 사람들이 원형으로 둘러 앉고, 각 사람들 번호를 1~N으로 매김
- 시작 위치부터 K번째 사람 제거
- 제거한 위치부터 다시 K번째 사람 제거
- 3 과정을 한 명이 남을 때까지 반복
배열로 푼다면?
- 제거의 방향이 바뀜
- 제거 시 제거한 뒤의 원소가 모두 이동해야 함
시간 복잡도 O(N^2)
정리
- 스택: LIFO, 함수 호출 관리, 페이지 탐색, 괄호 짝 맞추기
- 큐: FIFO, 줄 서기, 요세푸스
- 스택의 경우 “가장 최근 원소”를 봐야 하는 경우에 사용
- 추후 DFS, 백트래킹에 사용
- 큐는 들어온 순서대로 나갈 때 사용
- 추후 BFS에서 사용