기술 면접 스터디
✅ Stack과 Queue 그리고 Array와 Linked List 자료구조에 대해 말씀해주시고 차이점에 대해 설명해주세요.
1) Stack
스택(stack)이란 쌓아 올린다는 것을 의미한다.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.
📌 스택의 특징
스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고,
top으로 정한 곳을 통해서만 접근할 수 있다.
top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며,
삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는
구조적 특징을 가지게 된다.
이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.
그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,
스택이 넘치는 경우 stack overflow라고 한다. (그 유명한 사이트 "stack overflow " 의 이름이 여기서 유래 된 것!)
📌 스택의 활용 예시
스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
2)Queue
Queue 의 사전적 의미는
1. (무엇을 기다리는 사람, 자동차 등의) 줄 ,
2. 줄을 서서 기다리는 것을 의미한다.
따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이
선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.
📌 큐의 특징
정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
이때 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear)로 정하여
각각의 연산 작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입 연산을 인큐(enQueue)
프론트에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 부른다.
- 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
- 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
- 접근방법은 가장 첫 원소와 끝 원소로만 가능
- 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며,
리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.
📌 큐의 활용 예시
큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
🌠 비교 분석
👀 참고 블로그
3) Array
ArrayList는 기본적으로 배열을 사용한다. 하지만 일반 배열은 처음에 메모리를 할당할 때 크기를 지정해주어야 하지만, ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다.
📌 조회
Index를 가지고 있어 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한 번에 가져올 수 있다.
📌 데이터 추가·삭제
데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다.
위의 사진으로 예를들면 5개의 데이터가 있을 때 맨 앞의 2를 삭제했다면 나머지 뒤의 4개를 앞으로 한칸씩 이동해야 한다.
삽입과 삭제가 많다면 ArrayList는 비효율적이다.
4) Linked List
LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어 참조하려는 원소에 따라 처음부터 정방향 또는 역순으로 순회 가능하다. (배열의 단점을 보완하기 위해 LinkedList가 고안되었다.)
📌 조회
LinkedList는 순차적 접근이기 때문에 검색의 속도가 느리다.
📌 데이터 추가·삭제
LinkedList는 데이터를 추가·삭제시 가리키고 있는 주소 값만 변경해주면 되기 때문에 ArrayList에 비해 상당히 효율적이다.
위의 사진으로 예를 들면 2번째 값을 삭제하면 1번째 노드가 3번째 노드를 가리키게 하기만 하면 된다.
각 원소마다 앞,뒤 원소의 위치 값을 가지고 있다.
🌠 비교 분석
이처럼 조회 시에는 Array List가 우위에 있지만,
삽입/삭제 시에는 Linked List가 뛰어난 성능을 보여준다.
소량의 데이터를 가지고 사용할 때는 사실 큰 차이가 없지만,
정적인 데이터를 활용하면서 조회가 빈번하다면 Array List를 사용하는 것이 좋고,
동적으로 추가/삭제 요구사항이 빈번하다면 Linked List를 사용하는 것이 좋다.
👀 참고블로그
✅ 절차지향 / 객체지향 / 함수형 프로그래밍이란 무엇이고 차이점은 무엇인가?
1) 절차 지향 프로그래밍(Procedural Programming)
일이 진행되는 순서대로 프로그래밍하는 방법
- 장점
코드의 가독성이 좋음.
컴퓨터의 처리구조와 비슷해 실행 속도가 빠름. - 단점
각각의 코드가 순서에 민감하게 연결 되어있어, 유지보수 및 분석이 어려움.
2) 객체 지향 프로그래밍(Object Oriented Programming)
모든 데이터를 객체(Object)로 취급하고,
객체가 처리 요청을 받았을 때, 객체 내부에 있는 기능을 사용해 처리하는 방법
서로 연관되어있는 함수와 변수들을 객체라는 것으로 그룹핑.
그 객체에 들어있는 함수들을 호출해서 다른 함수들과 분리/구분해줌.
- 4가지 특징
1) 추상화 : 공통적인 속성이나 기능을 묶어서 이름을 붙이는 것
2) 캡슐화 : 데이터를 은닉하고 데이터 기능을 노출시키지 않음.
3) 상속성 : 상위 부모 객체의 속성과 특징을 하위 객체가 물려 받는 것.(만약 어떠한 객체가 이미 존재하는 객체의 특성을 가지고 있다면, 기존 객체의 특성을 상속시켜 만들 수 있음.)
4) 다형성 : 같은 함수가 있어도 매개변수에 따라 각자 다른 일을 하는 것
- 장점
코드의 재사용이 가능.(확장, 유지보수에 용이!)
분석과 설계의 전환이 쉬움.
- 단점
처리 속도가 상대적으로 다소 느림.
설계에 많은 시간이 소요됨.
- 객체지향 프로그래밍 언어: 자바, 스몰토크
3) 함수형 프로그래밍
- "순수 함수"를 사용해, 상태를 제어하기보단, 빨리 처리하는데 초점을 둔 방법
실행 순서를 지정할 필요가 없기 때문에 비절차형 언어라고도 함!
- 순수 함수란?
- 동일한 입력값을 넣었을 때 항상 동일한 리턴값을 반환하며 외부에 영향을 받지 않는 함수
외부에 영향을 받지않음. - 함수의 실행이 프로그램에 영향을 주지 않음.
- 비상태 불변성 유지.
(전달된 데이터를 변경하는 것이 아니라 새로운 버전, 새로운 오브젝트를 만들어서 결과값으로 전달해야함)
👉 여러가지 동시다발적인 멀티쓰레딩 환경에서도 안정적으로 동작할 수 있음
- 동일한 입력값을 넣었을 때 항상 동일한 리턴값을 반환하며 외부에 영향을 받지 않는 함수
- 장점
함수의 동작부가 간결해지기 때문에, 객체지향 프로그래밍에 비해 코드 이해도와 가독성이 좋아짐.
테스트가 쉬움.
- 단점
외부 데이터 혹은 내부 데이터의 상태를 조작할 수 없음.
- 함수형 프로그래밍 언어: Haskell, OCaml 등
C++, Python, JavaScript, Java와 같은 언어의 최신버전에 함수형 프로그래밍의 특징들이 더해짐.
4) 차이점
📌 절차형 프로그래밍과 객체 지향 프로그래밍의 차이
절차형 프로그래밍 다음으로 객체지향 프로그래밍이 탄생.
절차형 프로그래밍이 갖고 있는 부족함을 객체지향 프로그래밍이 보완해주는 역할.
절차형 프로그래밍은 함수가 있고, 객체지향 프로그래밍 또한 함수가 있지만 '객체'라는 개념이 등장함.
📌 객체 지향 프로그래밍과 함수형 프로그래밍의 차이
1) 함수형 프로그래밍에서는 함수(Function) 자체가 일급 객체가 되지만, 객체지향 프로그래밍에서는 클래스(또는 객체, Object)가 일급 객체가 됨.
- 일급 객체란?
다른 요소들과 아무런 차별이 없는 객체.
즉, 함수의 인자로도 넘겨질 수 있고, 변수에 대입도 가능한 객체를 일급 객체. - 일급 객체의 명확한 정의-
모든 일급 객체는 함수의 실질적인 매개변수가 될 수 있다.
모든 일급 객체는 함수의 반환값이 될 수 있다.
모든 일급 객체는 할당의 대상이 될 수 있다.
모든 일급 객체는 비교 연산(==, equal)을 적용할 수 있다.
2) 객체 지향 프로그래밍에서는 프로그램을 상호작용(interaction)하는 객체들의 집합으로 볼 수 있지만, 함수형 프로그래밍에서는 상태 값을 지니지 않는 함수들의 연속으로 볼 수 있음.
- 객체지향 프로그래밍의 경우
클래스 디자인과 객체들의 관계를 중심으로 코드 작성이 이루어짐.
따라서, 상태, 멤버변수, 메서드 등이 긴밀한 관계를 가지고 있음.
특히, 멤버변수가 어떤 상태를 가지고 있는가에 따라 결과가 달라짐. - 함수형 프로그래밍의 경우
값의 연산 및 결과 도출 중심으로 코드작성이 이루어짐.
함수는 인자로 받은 값을 별도로 저장하지 않고, 간결한 과정으로 처리하고 매핑하는데에 주 목적을 둠. - 어느 하나가 우위에 있다고 말할 수 있다기보다는 필요에 따라 합쳐서 사용하기도 하고 원하는 목표에 따라 적절한 것을 잘 골라 사용해야함.
👀 참고 블로그