3개월간의 부트캠프가 거의끝나간다 !!!!
면접준비를 하며 그날그날 공부한 내용을 정리해보자!
시간복잡도와 공간복잡도
(Time Complexity Space Complexity))
시간 복잡도(Time Complexity)
알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기한것
공간 복잡도(Space Complexity)
프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양
시간복잡도와 공간복잡도는 알고리즘의 성능을 판단하는 복잡도 들이다.
데이터의 양이 많지 않을때는 상관이 없으나, 데이터의 양이 많아지면,
알고리즘에 따라 효율성 차이가 커질 수 밖에 없다.
효율적인 알고리즘이란?
알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 것
스택, 큐
stack,que
Stack
스택은 쌓다라는 의미로 데이터를 차곡차곡 쌓은 형태의 자료구조이다
Que
큐는 스택과 다르게 선입선출 방식의 자료구조이다.
stack의 특징
스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고,
top으로 정한 곳을 통해서만 접근할 수 있다.
top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며,
삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는
구조적 특징을 가지게 된다.
이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.
스택의 활용 예시
웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
후위 표기법 계산
수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
Que의 특징
선입선출(FIFO, First in first out) 방식
정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여
각각의 연산작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.
큐의 활용 예시
큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
은행 업무
콜센터 고객 대기시간
프로세스 관리
너비 우선 탐색(BFS, Breadth-First Search) 구현
캐시(Cache) 구현
