[20주차 - DAY5] 알고리즘 리뷰

 

 

Stack

스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 후입선출(가장 나중에 들어간 것이 가장 먼저 나오는) 방식이다.

위 그림은 push('a'), push(1), push(3.14)를 실행한 예시이며, pop을 세 번 실행하면 3.14, 1, 'a' 순으로 나오게 된다.

대표적인 스택의 활용 예시는 컴퓨터 프로그램의 콜 스택이다. 콜 스택은 컴퓨터 프로그램의 서브 루틴에 대한 정보를 저장하는 역할을 한다.

• 장점: 구현이 간단하며, 데이터 쓰기/읽기 속도가 빠르다.
• 단점: 데이터 최대 개수를 미리 정해야 하며, 저장 공간에 낭비가 발생할 수 있기 때문에 미리 최대 개수만큼 저장 공간을 확보해 놓아야 한다.

스택이 사용되는 문제 유형은 다음과 같다.

1. 쌍을 이루는 요소를 찾는 문제
   • ex) 괄호의 왼쪽 오른쪽 쌍이 맞는지
2. 커서를 기준으로 커서의 위치나 값을 조정하는 문제
3. 리스트(배열)를 탐색하면서 자신의 값과 비교해야 하는 문제
   • ex) 자기보다 오른쪽에 있는 수들 중 자기보다 크고, 가장 왼쪽에 있는 수를 구하는 문제

 

Map

map은 key-value 쌍을 다루는 자료구조이다.

키 값을 해시 함수에 넣어서 나온 값에 value를 저장해 놓는 방식이다.

 

정렬되어 있지 않은 배열에서 한 값을 탐색한다고 가정해 보면 선형 탐색을 해야 하기 때문에 시간복잡도가 O(n) 일 것이다.

하지만 map의 경우에는 key를 해시로 계산해서 접근하기 때문에 시간복잡도는 O(1)이다.

 

따라서 배열 형식의 자료형을 사용하기에는 탐색해야할 일이 너무 많거나, 중복된 값에 대한 처리를 해주어야 할 경우에 많이 사용한다.

• 장점: 조회, 저장, 삭제가 빠르다.
• 단점: map 사이즈를 작게 잡을 경우에 너무 많은 저장이 일어나면 속도가 느려질 수 있다.

 

 

+) 3, 4번은 어떻게 푸는지 감이 안와서 어떤 알고리즘을 쓰는지 잘 모르겠다..