[자구, 알고] 복잡도, 빅오, 스택, 큐 질문답변

 

 

 

 

● 시간복잡도와 공간복잡도에 대해 설명해 주세요.

 - 시간복잡도 : 알고리즘을 수행하는데 시간이 얼마나 걸리는가를 표기하는 것
 - 공간복잡도 : 알고리즘을 수행하는데 얼만큼의 공간(그러니까 RAM이나 하드디스크의 메모리 같은 곳)이 필요한가를 표기하는 것

 

● 빅오, 빅오메가, 빅세타

 - 빅 오(Big-Oh) 표기법 : 최악의 경우
 - 빅 오메가(Big-Omega) 표기법 : 최선의 경우
 - 빅 세타(Theta) 표기법 : 빅 오와 빅 오메가의 공통부분. 최소와 최악의 중간인 평균적인 복잡도
https://vaert.tistory.com/117

 

● 다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

 - 현실에서는 항상 최악의 경우를 생각해야 하기 때문. 빅-오메가나 빅 세타를 이용해서 자원을 할당했는데 최악의 상황이 발생하면 아무 의미가 없다.

 

 

 

● 스택과 큐에 대해 설명해주세요. 사용사례를 알려주세요

 - 스택
    - 후입선출 LIFO(Last In First Out)
    - 마지막에 들어온 데이터가 먼저 나오는 자료구조
    - 바구니
    - top을 가리켜서 삽입(push), 삭제(pop) 수행
    - 사용 사례 : 웹 브라우저 뒤로가기, 실행 취소, 컨트롤 제트, 역순 물자열 만들기, 후위 표기법 계산
 - 큐
    - 선입선출 FIFO(First In First Out)
    - 먼저 들어온 데이터가 먼저 나가는 자료구조
    - 터널
    - 삭제가 수행되는 맨 앞은 front, 삽입이 수행되는 맨 뒤는 rear를 사용 
    - 또는 head, tail
    - 사용 사례 : 은행업무, 서비스센터

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

● Circular Queue

 - 선형 큐의 문제점을 보완하기 위한 자료구조
 - 문제는 rear이 배열의 마지막 인덱스를 가르키게 되면 앞에 남아있는 (삽입 중간에 Dequeue 되어 비어있는 공간) 공간을 활용 할 수 없게 됨
 - rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입한다.

https://lktprogrammer.tistory.com/59

● 스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.

 - 스택 2개로 큐 만들기
    - 스택 한개는 InBox, 한 개는 OutBox 용도
    - push : InBox 스택에 넣는다.
    - pop : InBox 스택에서 OutBox 스택으로 모두 옮기고 맨위에 것을 뺀다.
    - push : OutBox 스택에서 InBox 스택으로 모두 옮기고 맨 위에 넣는다.
    - O(N)

 - 큐 2개로 스택 만들기
    - 큐 한 개는 메인 큐, 다른 큐는 임시 큐
    - push : 메인 큐에 넣는다. 
    - pop : 메인 큐에 1개의 원소가 남을 때까지 꺼내고 그 값을 임시 큐에 넣는다.
    - 하나 남은 값을 꺼낸다.
    - 임시큐에서 다시 메인큐로 다 넣는다.
    - O(N)

● Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산하는 방법에 대해 설명해 주세요.

 - infix     : 연산자가 가운데 [a+b]
 - prefix   : 연산자가 왼쪽 [+ab]
 - postfix : 연사자가 오른쪽[ab+] 
 - 사칙연산과 같이 괄호안을 먼저 하고 그다음 * /, 다음 + - 수행

https://kcoder.tistory.com/entry/%ED%91%9C%EA%B8%B0%EB%B2%95-infix-prefix-postfix-%EA%B0%9C%EC%9A%94%EC%99%80-%EA%B0%84%EB%8B%A8%EC%98%88%EC%A0%9C

● Deque는 어떻게 구현할 수 있을까요?

 - double-ended queue
 - 앞에서 데이터 삭제하고 뒤에서 데이터 삽입했던 선형 큐와는 달리 앞뒤에서 모두 삽입, 삭제가 가능
 - 데이터 삽입 시 front 감소, rear 증가 / 삭제 시 front 증가, rear 감소

https://yjg-lab.tistory.com/116