알고리즘 공부 2일차

Queue

queue는 시간순서상 먼저 입력된 값이 먼저 출력되는 FIFO 형식으로 저장하는 자료구조
rear에 데이터를 추가하는 것을 enqueue라고 하고 빼는것을 dequeue라고 한다

코딩테스트에서 단독으로 사용하진 않는다

Stack

코딩테스트에 자주 나오는 Stack

stack은 시간 순서상 가장 최근에 추가한 데이턱 가장 먼저 나오는 후입선출 LIFO 형식으로 저장하는 자료구조
stack에 데이터를 추가하는 것을 push 추출하는것을 pop이라고한다

stack 문제 풀이

stack 문제는 보통 List로 진행하기에 n보다 더 좋은 시간복잡도를 하긴 어렵다 List 자체가 O(n)이기 때문이다

1. input output 확인하기 정수, 값크기, 마이너스, 소수 , 자료형 ,문자열인지

2. input size N 확인

3. 제약조건 확인 시간 복잡도 및 알고리즘 무엇을 사용해야하는지

4. 예상할 수 있는 오류 파악 상황을 가정하면서 오류를 찾는다

문제 접근방법

직관적으로 생각하기

보통 완전탐색으로 시작
문제상황을 단순화하여 생각하기
문제 상황을 극한화 하여 생각하기

자료구조와 알고리즘 활용

문제이해에서 파악한 내용을 토대로 어떤 자료구조를 사용하는게 가장 적합한지 결정
대놓고 특정 자료구조와 알고리즘을 묻는 문제도 많음
자료구주에 따라 선택할 수 있는 알고리즘 문제에 적용

메모리 사용

시간복잡도를 줄이기 위해 메모리를 사용하는 방법
대표적으로 헤시테이블