Intro.
안녕하세요 Pu드로이드 입니다^^
취업차.. 코딩테스트 준비를 위해 1일 1백준 알고리즘 풀이를 꾸준히 하고 있는데요!
더 나은 문제 접근을 위해 유튜브 바킹독님의 영상으로 알고리즘 기본기를 다질 계획이며,
동시에 블로그 포스팅을 통해 정보를 기록하고 공유하려 합니다!
궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!
자료구조란?
데이터들이 모여있는 약속된 구조 + 자료의 삽입 삭제등에 규칙이 존재하기 때문에 상황에 따라 매우 효율적.
자료구조는 컴공 학과라면 가장 초반에 배우는 내용 중 하나로
정말 기초이지만 다양한 알고리즘 문제 풀이에서 사용될 수 있더라구요!!
예를들어
괄호 문제(백준 4949)에는 스택 자료구조가 유용하게 쓰이고
BFS(너비 우선 탐색 유형) 등에서는 큐 자료구조가 유용하게 쓰입니다!
너무 간단하고 기본적인 내용이지만 필요한 상황에서 알맞게 쓰는건 매우 어려운것같아요.
(결국 많은 문제를 풀어보는수밖에는..)
스택
LIFO (Last In First Out)
마지막으로 들어간 데이터가 첫번째로 나간다!
스택의 시간복잡도
- 원소 추가 O(1)
- 원소 제거 O(1)
- 제일 상단 원소 확인 O(1)
- 제일 상단이 아닌 원소들의 확인 변경은 원칙적으로 불가
백준 예시문제~
https://www.acmicpc.net/problem/4949
4949번: 균형잡힌 세상
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에
www.acmicpc.net
큐
FIFO (First In First Out)
첫번째로 들어간 녀석이 첫번째로 나가는 자료구조!
큐의 시간복잡도
- 원소 추가 O(1)
- 원소 제거 O(1)
- 제일 앞 뒤 원소 확인 O(1)
- 제일 앞 뒤가 아닌 원소들의 확인 변경은 원칙적으로 불가
백준 예시문제 ~
https://www.acmicpc.net/problem/10845
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
덱
양쪽 끝 모두 삽입과 삭제가 가능한 자료구조!
덱의 시간복잡도
- 원소 추가 O(1)
- 원소 제거 O(1)
- 제일 앞 뒤 원소 확인 O(1)
- 제일 앞 뒤가 아닌 원소들의 확인 변경은 원칙적으로 불가
'알고리즘' 카테고리의 다른 글
| [알고리즘] DFS - 깊이 우선 탐색이란? (4) | 2023.12.21 |
|---|---|
| [알고리즘] BFS - 너비 우선 탐색이란? (0) | 2023.12.21 |
| [알고리즘] 배열, 연결리스트 with Kotlin (0) | 2023.12.12 |
| [알고리즘] 시간복잡도, Kotlin 자료형 (0) | 2023.12.11 |
