[Interview] 면접 예상 질문 대비 - 1

December 21, 2022

면접 예상 질문 대비 자료 - 1

시간 복잡도와 공간 복잡도

알고리즘의 성능을 판단하는 두 가지 기준을 말한다.

시간 복잡도 (Time Complexity)

알고리즘을 수행하는데 이루어진 연산의 횟수이며 여기에서 연산의 종류는 산술, 대입, 비교, 이동을 말한다. 연산의 횟수는 보편적으로 입력한 데이터의 개수(n)에 따라 계산되며 수식으로 아래와 같이 표현한다. \(T(n)\) sum = a + a 의 수식은 대입연산 1회, 덧셈 연산 1회, 총 2회의 연산이 이루어졌다. 하나의 연산에 t만큼의 시간이 필요하다고 가정하면 아래와 같이 표현할 수 있다. \(2t(n)\) 동일한 알고리즘이라도 입력되는 데이터에 따라 다른 실행시간을 보일 수 있다. 예를 들어 정렬 알고리즘의 경우 대부분 정렬되어있는 데이터와 그렇지 않은 데이터의 시간 복잡도가 크게 차이날 수 있다. 이 때 데이터의 집합에 따라 세가지 경우에 따라 나누어 평가한다.

최선의 경우(Best Case) : 실행 시간이 가장 적은 경우를 말한다.
평균적인 경우(Average Case) : 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균 수행 시간을 말한다.
최악의 경우(Worst case) : 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 말한다.

시간 복잡도를 계산할 때에는 최악의 경우를 주로 사용한다.

빅오 표기법 (big-oh notation)

시간/공간 복잡도 함수에서 불필요한 연산을 제거하여 보다 간편하게 시간/공간 복잡도를 표기하는 방법이다.

빅오 표기법은 정확한 연산의 갯수가 아니라 알고리즘의 일반적인 증가 추세를 표현한다. 알고리즘이 n에 정비례하여 실행 시간을 가질 경우 시간 복잡도가 O(n)이라 표시하고 ‘big-oh of n’이라고 읽는다.

자주 쓰이는 표기법은 아래와 같다.

빅오 표기법	1	4	8	32
O(1)	1	1	1	1
O(logn)	0	2	3	5
O(n)	1	4	8	32
O(nlogn)	2	8	24	160
O(n^2)	1	16	64	1,024
O(n^3)	1	64	512	32,768
O(2^n)	2	16	256	4,294,967,296
O(n!)	1	24	40,326	26,313×10^33

공간 복잡도 (Space Complexity)

공간 복잡도란 프로그램의 실행~완료까지 필요로하는 자원 공간의 양을 말한다.

총 공간은 고정 공간 요구와 가변 공간 요구의 합으로 나타낼 수 있으며, 수식으로는 아래와 같이 표시한다. \(S(P) = c + S_p(n)\) 고정공간 : 코드 저장 공간, 단순 변수, 고정된 크기의 구조 변수, 상수를 말한다.

가변공간 : 해결하려는 문제의 인스턴스에 의존하는 크기를 가진 공간. 즉, 동적으로 필요한 공간을 말한다.

정리

좋은 알고리즘은 시간도 적게 걸리고 자원의 사용도 적어야 한다. 다만 시간과 공간은 반비례적인 경향이 있어 선택의 문제가 되는 경우도 있을 수 있다. 이 때 알고리즘의 척도는 시간 복잡도를 위주로 판단하는 편이다.

스택과 큐

스택과 큐는 자료구조의 일종이다. 자료구조란 자료의 사용 방법이나 성격에 따라 효율적으로 사용할 수 있도록 조직하고 저장하는 방법이다. 크게 선형과 비선형으로 나누어지며 스택과 큐는 선형 자료구조의 일종이다.

스택 (stack)

스택은 후입선출(LIFO)형 자료구조이다. 원소의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서 수행되며 삽입/삭제가 일어나는 리스트의 끝을 top, 그 반대를 bottom이라 지칭한다.

큐 (Queue)

큐는 선입선출(FIFO)형 자료구조이다. 원소의 삽입이 일어나는 끝을 rear, 원소의 삭제가 일어나는 끝을 front라고 지칭한다.

입력한 순서대로 출력되는 작업에 사용된다. 버퍼는 Queue의 구조를 이용하는 대표적인 방식이다.

배열과 링크드리스트

배열과 링크드 리스트는 모두 데이터를 순차적으로 나열하여 저장하는 방식이다. 단, 구조적으로 차이가 있다.

배열 (Array)

데이터 뿐 아니라 데이터가 저장된 물리적 주소 또한 순차적이다. 인덱스를 통해 원하는 데이터에 한번에 접근이 가능하지만 삽입/삭제를 위해서는 일부 배열을 밀고 당기는 위치 변경이 발생하여 시간이 오래 걸린다.

링크드 리스트(Linked list)

데이터는 순차적으로 저장되나 데이터가 저장된 물리적 주소는 순차적이지 않다. 인덱스가 없어 원하는 데이터에 한번에 접근할 수 없으며, 현제 데이터가 다음 데이터의 주소를 가지고 있기에 연결된 링크를 따라 원하는 데이터에 접근 해야한다. 데이터 간 연결 링크의 변경으로 데이터의 삽입/삭제가 가능하다.

예상하건데, 수정/삭제가 잦은 경우 링크드 리스트를 사용하는 편이 유리하겠다.

CORS란 무엇이며 어떻게 허용할 수 있는가?

CORS (Cross-origin resource sharing) 직역하면 교차 출처 리소스 공유이며, 웹 페이지 상의 제한된 리소스를 최초 자원이 서비스된 도메인 밖의 다른 도메인으로부터 요청할 수 있게 허용하는 구조이다.

일반적으로 자료를 제공하는 도메인에서 CrossOrigin 어노테이션을 통해 허용할 출처(origin)를 등록하여 사용한다. CORS는 브라우저에서 임의로 체크하는 것이므로 브라우저의 실행옵션이나 플러그인 등을 통해 동일 출처 정책을 회피하는 방법이 있다.

사용자 패스워드를 전송하고 보관하는 방법

클라이언트에서 패스워드를 수집하여 서버로 전송하면 단방향 또는 양방향으로 암호화를 진행한다.

단방향 암호화 방식은 암호화 이후 평문으로 복호화를 할 수 없는 방식을 말한다. 대표적으로 해쉬 함수를 사용하는 방식이 있는데, 이는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다.

양방향 암호화 방식은 암호화와 복호화가 모두 가능한 방식을 말한다. 대칭키와 비대칭키 암호화 방식이 이에 해당한다.

대칭키 방식은 암호화/복호화 시 동일한 키가 사용된다. 비대칭키 암호화 방식에 비해 속도가 빠르지만 대칭키를 안전하게 관리하는 것이 중요하다. 대칭키 암호화 알고리즘으로는 DES, IDEA, AES가 있다.

비대칭키 방식은 공개키 암호화 방식이라고도 표현하며 암호화/복호화를 위한 키가 다르다. 대칭키 암호화 방식에 비해 속도가 느리지만 보안상 안전하다. 비대칭키 암호화 알고리즘 방식에는 DH, ECC, RSA가 있다.

var, let, const

세 가지는 모두 Javascript의 변수 선언 방식이다.

가장 큰 차이는 재선언/재할당에 있다. var 는 재선언과 재할당이 모두 가능하고 let 은 재선언은 불가하나 재할당이 가능하며, const는 재선언과 재할당이 모두 불가하다.

또한 호이스팅에도 다소의 차이가 있는데, var로 선언한 변수는 호이스팅 시 선언/초기화 단계가 한번에 이루어지므로 선언/할당 코드 전에 호출하여도 Error가 출력되지 않는다. let과 const는 호이스팅 시 선언과 초기화가 분리되어 진행된다. 때문에 변수 선언 코드 이전에 호출할 경우 Error가 출력된다.

Promise

Javascript에서의 간편한 비동기 처리를 위한 객체이다.

state와 result 를 값으로 가지며 state는 Promise의 상태를 표시한다. 초기값은 pending(대기), resolve가 호출되면 fulfilled(이행), reject가 호출되면 rejected(거부) 값을 갖고, 둘 중 한가지로 완료된 이후에는 setteled 상태를 갖는다. result는 resolve가 호출되었을 때에는 함수에 전달되는 값을 갖는다.

fulfilled 혹은 rejected가 발생하면 .then메서드에 의해 먼저 관련 핸들러들이 콜백 큐로 삽입되고, 그 후 콜 스택이 비었을때 콜백큐에서 콜스택으로 push되고, 콜스택에 올라간 콜백함수는 나중에 pop되어 실행된다.

Hoisting

인터프리터가 변수와 함수의 메모리 공간을 선언 전에 미리 할당하는 것을 말한다.

함수와 var로 선언된 변수는 메모리 할당과 초기화를 함께 진행하며 let과 const로 선언된 변수는 메모리 할당 이후 초기화까지 TDZ(Temporal Dead Zone, 일시적 사각지대)에 속하며 이 때 호출 시 error가 발생한다.

Async/Await

Promise 객체를 사용한 비동기 처리를 좀 더 단순화할 수 있도록 도와주는 API이다.

Async는 함수 선언문에 사용되며 해당 함수가 Promise 객체를 반환하게 한다.

Await는 Async 함수와 함께 사용되며 반환되는 Promise 객체의 상태가 Settled가 될 때까지 기다린 후 값을 반환하게 한다.

Arrow Function

ES6 이후 지원하는 문법으로 익명 함수 선언을 단순화 한다. 호이스팅 되지 않으며, 언제나 상위 스코프의 this 바인딩을 참조한다.

‘==’와 ‘===’ 연산자의 차이

== 는 값을 비교하고 ===는 값과 변수의 유형 (type of)도 비교한다.

Virtual DOM과 Real DOM

DOM은 HTML페이지 내 요소를 트리 구조로 표현한 것이다. Real DOM은 이를 Virtual DOM과 분리하여 표현하기 위한 단어이다.

Virtual DOM은 React/Vue 에서 효율적인 Rendering 연산을 위해 생성하는 객체이다. Real DOM과 동일한 요소, 구성을 가지고 있어 React/vue에서 Re-rendering이 발생할 때 렌더링 전/후의 virtual DOM을 비교하여 변경된 Element만 추출하여 Real DOM에 적용시킨다.

useRef()

React hook 중 하나로 ref 객체를 생성할 수 있다.

생성된 ref 객체는 HTML element에 접근할 때 사용할 수 있고 불필요한 렌더링을 발생시키지 않는 값을 관리해야할 때 사용할 수 있다. Re-rendering 시 함수가 재실행되며 내부의 변수 값이 초기화 될 수 있는데, ref 객체는 Re-rendering 시 값이 초기화되지 않으며, 값 변경 시 rendering을 발생시키지 않아야하며 이와 같은 조건의 값을 다루는데 유용하게 사용된다.

리액트 컴포넌트의 라이프사이클

크게 Mounting(생성) - Updating(리렌더링) - Unmounting(해제)으로 구분된다. 클래스형 컴포넌트는 componentDidMount, componentDidUpdate, componentWillUnmount 등의 함수로 라이프 사이클에 따라 실행되는 함수를 추가할 수 있고, 함수형 컴포넌트는 useEffect 함수로 추가할 수 있다.

추가 : https://roses16-dev.github.io/react/componentLifecycle/

JSX

Javascript를 확장한 문법. 리액트 컴포넌트를 작성할 때 사용되며 마크업과 로직을 모두 구성할 수 있게 하는 문법이다.

세션(Session)과 쿠키(Cookie)

HTTP는 기본적으로 Stateless, 즉 무상태한 프로토콜이다. 이는 클라이언트-서버간 통신에서 서버는 클라이언트의 상태를 알 수 없다는 것을 의미한다. 이는 서버가 클라이언트의 Request에 Response를 반환하면 서로의 연결이 끊어진다는 특성에 기반한다.

하지만 이와 같은 특징에도 서버에서 클라이언트의 상태를 알아야하는 경우가 있고 ( ex: 인증 ) 이 때 사용하는 것이 쿠키와 세션이다.

첫 Request가 서버로 전달되면 서버는 세션을 생성한 후 세션의 ID만 Response로 반환한다. 이 후 인증이 필요한 때 Session ID가 포함된 Cookie를 Request에 담아 전달하면 서버에서 쿠키의 Session ID를 통해 클라이언트를 식별할 수 있다.

쿠키는 브라우저에 저장되는 { key: value } 형태의 데이터이다. 세션에 비해 속도가 빠르고 보안에 취약하며 브라우저가 종료되어도 데이터가 유지된다. 세션은 서버에 저장되는 데이터이다. 보안에 좋지만 비교적 속도가 느리며 브라우저가 종료되면 데이터가 소멸된다.

브라우저에서 이용할 수 있는 스토리지

Cookie : 만료 기한이 있는 { key: value } 형태의 저장소

Local storage : 브라우저를 닫더라도 데이터가 유지되는 저장소. 도메인이 같을 경우 브라우저가 달라도 데이터에 접근할 수 있다.

Session storage : 브라우저를 닫을 경우 데이터가 삭제된다. 브라우저/탭이 다를 경우 데이터에 접근할 수 없다.

Context API

React에서 제공하는 API. 전역적으로 사용되어야하는 Data들을 여러 컴포넌트에서 쉽게 공유할 수 있도록 하는 기능을 제공한다.

최상위 컴포넌트에서 `<context.Provider value={값}>의 형태로 정의하고 필요한 컴포넌트에서 useContext(context)를 통해 사용할 수 있다. context value가 변경되면 내부 컴포넌트는 모두 리렌더링 되므로 데이터 변경 시 주의가 필요하다.

useReducer와 함께 사용하면 react-redux와 비슷한 형태로 사용할 수 있다.

이분탐색과 그 시간 복잡도

이분 탐색이란 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

데이터가 정렬되어있어야만 사용할 수 있으며 start, end, mid 변수를 사용하여 탐색한다.

단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 시간 복잡도는 O(logN)이다.

트리, 그래프

트리와 그래프는 모두 비선형 데이터 구조의 일종이다.

그래프는 노드와 노드를 연결하는 간선으로 구성된 자료구조이다. 연결된 노드 간의 관계를 표현할 수 있다. 순환 혹은 비순환 구조를 이루며 방향이 있는 그래프와 없는 그래프가 있다. 2개 이상의 경로가 가능하다.

트리는 그래프와 같이 노드와 노드를 연결하는 간선으로 구성된 자료구조이다. 단, 두 개의 노드 사이에는 1개의 경로만을 가지며 사이클이 존재하지 않는 방향성을 가진 그래프이다. 이러한 특성으로 ‘최소 연결 트리’라고도 불리운다. 최상위 Root node를 가지며 부모-자식 관계가 성립하는 계층형 모델이다. 최대 간선의 수는 노드의 갯수 -1개 이며 전위순회(Root-L-R)/중위순회(L-Root-R)/후위순회(L-R-Root) 의 3가지 방식으로 탐색할 수 있다.

📌 출처

https://madplay.github.io/post/time-complexity-space-complexity
https://terms.naver.com/list.naver?cid=42344&categoryId=42344
https://medium.com/@Aaron__Kim/%EA%B8%B0%EC%88%A0-%EB%A9%B4%EC%A0%91-%EC%A4%80%EB%B9%84-db-os-nw-e03cdfe07966
https://bohyeon-n.github.io/deploy/web/cors.html
https://developer.mozilla.org/
https://ko.reactjs.org/
https://velog.io/@damiano1027/CS-%EC%BF%A0%ED%82%A4Cookie%EC%99%80-%EC%84%B8%EC%85%98Session
https://youtu.be/LwvXVEHS638
https://velog.io/@suhyun-guri/React-%EC%83%81%ED%83%9C-%EA%B4%80%EB%A6%AC (📌 코드 적어보면서 한번 더 읽어봐야함 )
https://velog.io/@kimdukbae/이분-탐색-이진-탐색-Binary-Search

Rose