[기술 면접] 스터디 방법부터 예상 면접 질문까지

Chaejung·2024년 3월 3일
CS면접
3

기술면접대비_CS

목록 보기
8/8
post-thumbnail

이번 포스트는 기술 면접을 준비하는 신입 개발자를 위해 작성했다. 어디서부터 시작해야할지 모르겠거나, 무엇을 공부해야할지 모르는 사람들을 위해 기술 면접 준비 및 스터디 준비 가이드라인을 제시했다. 더불어 필자가 스터디를 하면서 준비한 것을 바탕으로 예상 면접 질문에 대한 답변도 작성했기에 이번 포스트는 아주 긴 포스트가 될 예정이다.

많은 사람들에게 도움이 되길 바라며, 동시에 미래의 나에게 도움이 되길 바라며 시작하겠다!

면접 준비는 어떻게?

기술 면접 준비는 왕도(王道)가 없다. 어느 형태의 기업을 준비하느냐에 따라 준비할 필요도 없을 수도 있고, 벼락치기가 불가능할 정도의 범위를 가지고 있으며, 직무에 따라 물어볼 수 있는 방향성이 또 달라지기 때문이다.

지금까지 몇 면접을 겪으면서 기술 면접 경험을 정리하자면 다음과 같다.

  • 대기업: 대체로 기본 사항을 묻지는 않았다, 경험과 관련있는 경우 심도있게 물어보는 편
    ex) 웹팩/번들러 문제: 브라우저에서 코드를 숨기는 법을 아시나요?
    관련 포스팅: 배포 시 React 코드 노출_우리 코드 절대 지켜
    ex) JavaScript 문제: AJAX가 무엇인지 아시나요?
    관련 포스팅: AJAX_SPA 구현의 핵심

  • 개발 인원 10인 이상: 천차만별이다. 자료구조/알고리즘부터 물어보는 경우 또는 자바스크립트 동작 원리를 물어보는 경우 또는 거의 물어보지 않은 경우

  • 개발 인원 10인 미만: 거의 물어보지 않았다.

그래서 다음과 같은 우선순위로 기술 면접을 준비하는 것이 그나마 전략이라고 할 수 있겠다.

  1. 개인 별 경험에 대한 기술을 깊게 파보자.
    • 프론트엔드의 경우 웹과 관련된 기술(웹팩, 자바스크립트), 특히나 개인이 직접 시도해본 것들에 대해 확실하게 공부한다.
  2. 기출 CS 면접 질문에 대해 키워드를 각자 선정해보자.
    • 이미 실력자들이 기출 질문에 대해 정리한 자료들이 참 많다.
    • 이런 자료들도 이미 충분한 범위를 가지고 있기에, 스스로 판별 기준을 세워 어떤 것을 가져갈 것인지 추려내는 것이 필요하다.
  3. 다하고도 시간이 남는다면 2번에서 제외시킨 키워드를 마저 공부하면 된다.
    • 그런데 여기까지 올 시간이 있기가 어려울 것이다!
    • 시간이 남는다면... 정말 대단한 사람! Respect 합니다

스터디 준비는 어떻게?

다른 기술 스터디와는 달리, 면접은 꼭 스터디를 하는 것을 추천한다. 그 이유는 일반 기술 스터디를 하는 이유로는 기술 공부 및 직접 적용이 크다. 그래서 의지만 있다면 혼자서도 충분히 할 수 있다. 그런데 면접은 사람 대 사람으로 진행하는 상황을 대비하는 것이기에 다른 사람과 직접 모의 면접을 하면서 대비하는 것이 필요하다.

필자는 긴장하면 얼굴에 열이 오르는 편인데, 이를 매주 스터디 때마다 구글 미트를 통해 모의 면접으로 예방 주사를 맞으니 실제 면접에서는 긴장 안 한 척을 할 수 있었다.

그래서 면접 준비를 해야겠다는 마음이 정해지면 스터디를 모집하든, 모집하는 스터디에 참여하든 사람을 만나는 것이 중요하다는 말을 전하고 싶다.

지금까지 했던 면접 스터디에서는 대략적으로 다음과 같은 프로세스를 가졌다.

  1. 매주 공부할 범위를 정한다.
    1) 기술 면접 레포지토리 또는 도서

    2) 스터디원이 한 직무로만 이루어져 있다면 매주 새롭게 키워드를 정한다.
    ex) 프론트엔드: 자바스크립트 실행컨텍스트 -> React 컴포넌트 -> 렌더링 방식

  2. 공부할 범위에 대해 예상 면접 질문을 준비해온다.

  3. 매주 만날 시간을 정한다.
    인원은 4-5명이 적당하다. 더 적으면 부담스럽고, 더 많으면 만날 시간을 정하기가 어렵거니와 스터디 시간이 길어진다. 보통은 1시간 이내로 끝내는 것이 적당한 것 같다.

  4. 만나서 모의 면접을 진행한다.
    1) 일 대 다(1:N)
    한 사람이 질문을 던진 다음 다른 사람 모두가 질문에 대한 답변을 한다. 답변하는 방식은 discord/slack의 스레드 내지 github repository issue 또는 code review를 활용하는 등 다양하다.
    장점👍: 한 사람이 많은 질문에 대한 답변을 할 수 있어 준비해온 것에 대한 복습을 하기 좋다.
    단점👎: 다른 사람들의 답변끼리 비교되어 실제 모의 면접을 구현하기 어렵다.
    2) 일 대 일(1:1)
    A -> B -> C -> D -> A -> B ... 식으로 순환 고리 형태로 모의 면접을 진행한다.
    장점👍: 실제 면접과 유사한 상황으로 면접 대비에 가장 적절하다.
    단점👎: 매주 긴장된다...

  5. 질문 답변 이후 질문의 의도, 답변에 대한 피드백을 한다.
    각자 중요하게 생각한 부분이 다를 수 있고, 답변자가 기술에 대한 핀트를 잘못 잡을 수도 있기에 이 과정을 통해 개선 방향을 제시하는 것이 중요하다.

필자는 이번에 글또(개발자 글쓰기 커뮤니티)에서 모집하는 기술 면접 스터디에 참여하게 되었다. 다른 스터디원 분들은 <백엔드/AI/데이터 엔지니어>여서 직무별 CS 교집합이 비교적 적은 편이었지만 그래도 기본 CS를 한 번 광범위하게 다뤄보고 싶고, 정보처리기사를 대비하고 싶어서 약 한 달 넘게 스터디를 진행했다.

[운영체제-자료구조-알고리즘-데이터베이스-네트워크] 순으로 매주 모의 면접을 진행했으며, 네트워크만 남겨두고 있는 상태이다.

예상 면접 질문

다음은 지금껏 스터디를 위해 준비한 면접 질문과 예상 답변이다. 예상 면접 질문은 앞부분에 기재한 기술 레포지토리를 참고한 부분이 있다. 답변의 경우 정보처리기사 도서, 기술 레포지토리, 공식 문서 등 다양한 참고 자료를 취합하여 작성했다.

혹시나 틀린 부분이나, 정정해야할 부분이 있다면 댓글로 남겨주길 바란다.

운영 체제

운영체제에 대해 아는대로 설명해보세요.

운영체제는 컴퓨터의 하드웨어와 소프트웨어 자원들을 효율적으로 관리하며 작업을 할 수 있는 환경을 제공해주는 시스템 소프트웨어입니다.
예를 들어 프로세스 관리 영역 중의 스케줄링은 여러 응용 프로그램이 동시에 실행되는 상황에서 CPU 자원을 효율적으로 할당하는 역할을 합니다. 이 밖에 운영체제의 대표적인 역할로는 메모리 및 파일 시스템과 같은 저장장치 관리, TCP/IP 및 기타 프로토콜와 관련한 네트워킹, 사용자의 계정 및 접근권한 관리 그리고 기기의 input, output 드라이버를 관리하는 역할이 있습니다.

이러한 기능은 소프트웨어 자원을 효율적으로 활용하여 전체적인 시스템 안정성과 성능을 유지하는 데 도움이 됩니다.

운영체제의 종류에는 Windows, UNIX, LINUX, MacOS, MS-DOS 등이 있습니다.

참고: tech-interview-for-developer : gyoogle github repository

시스템 콜에 대해 아는대로 설명해보세요.

시스템 콜은 운영체제와 응용 프로그램 간의 상호작용을 위한 인터페이스로, 응용 프로그램이 운영체제의 기능을 활용할 수 있도록 돕습니다. 이러한 시스템 콜은 프로세스 제어, 파일 조작, 장치 관리, 정보 유지, 통신, 보호 등 여러 유형으로 나뉩니다.

예를 들어 , 파일 조작 시스템 콜은 파일을 열거나, 읽고 쓰는 동작을 수행할 수 있게 합니다. 이러한 시스템 콜은 응용 프로그램이 파일 시스템과 상호작용할 수 있도록 해줍니다.

시스템 콜이 실행되면 프로세스는 사용자 모드에서 커널 모드로 전환됩니다. 이러한 전환은 운영체제의 보호된 영역에 접근하여 필요한 작업을 수행하도록 합니다. 즉, 프로세스가 하드웨어에 직접 접근해서 필요한 기능을 할 수 있도록 도와주는 역할을 합니다.

자바스크립트는 브라우저 환경에서 실행되는 언어로, 일반적인 운영체제 수준의 시스템 콜에 직접적으로 접근하는 것은 불가능합니다. 하지만 브라우저 환경에서 제공하는 다양한 API를 통해 파일 조작 등의 작업을 수행할 수 있습니다. File API, XMLHttpRequest 또는 Fetch API로 파일을 읽고 쓰거나 업로드 및 다운로드를 할 수 있습니다.

Paging이 왜 나오게 되었고, 개념에 대해 설명해 주세요.

Paging은 외부 단편화 문제를 줄이고, 효율적인 메모리 할당을 위한 메모리 관리 기법입니다.

Paging이란 process가 할당받은 메모리 공간을 일정한 page 단위로 나누어, 물리 메모리에서 연속되지 않는 서로 다른 위치에 저장합니다. 각 processs는 주소 변환을 위해 page table을 갖게 되며, 이 page table을 통해 가상 주소가 실제 물리 메모리 주소로 변환됩니다.

Paging 기법 사용시 발생할 수 있는 메모리 단편화(Memory fragmentation) 문제에 대해 설명해 주세요.

메모리 단편화 문제는 저장 공간이 비효율적으로 관리되어, 용량과 성능이 저하되는 문제입니다. 그중에서 메모리 상의 비어있는 공간의 크기가 작아서, 빈 메모리 공간임에도 활용되지 못하는 문제가 외부 단편화 문제입니다. 반면 프로세스가 필요한 양보다 더 큰 메모리가 할당되어서 메모리 공간이 낭비되는 문제는 내부 단편화 문제입니다.

Paging 기법에서는 각 process의 논리적 주소 공간과 물리적 메모리가 같은 크기의 page 단위로 나누어지기 때문에 외부 단편화 문제가 발생하지 않습니다. 하지만 process 주소 공간의 크기가 page 크기의 배수라는 보장이 없기 때문에, process의 주소 공간 중 가장 마지막에 위치한 page에서는 내부 단편화 문제가 발생할 가능성이 있습니다.

Paging과 Segmentation의 차이점에 대해 설명해 주세요.

둘 다 연속되지 않는 물리 메모리 공간을 process에 할당하는 메모리 관리 기법입니다. Paging은 일정한 크기인 page 단위로, Segmentation은 code, data, heap, stack과 같이 논리적 의미 단위로 나누는 것이 차이점입니다.

Paging의 경우 메모리 분할 공간이 일정하여 내부 메모리 단편화의 문제가 발생할 수 있고, 이에 반해 Segmentation은 서로 다른 크기의 segment들이 메모리에 적재되고 제거되는 일이 반복되면 외부 메모리 단편화의 문제가 발생할 수 있습니다.

Multi process에 대해 설명해보세요.

Multi process는 2개 이상의 process가 동시에 실행되는 개념을 나타냅니다. 각 process는 실행파일이 memory에 적재되어 CPU에 의해 독립적으로 실행됩니다. Multi process 환경에서의 동시는 동시성(concurrency)와 병렬성(parallelism) 두 가지를 의미합니다.

동시성은 CPU core가 1개일 때, 여러 process를 짧은 시간동안 번갈아 가면서 연산을 하게 되는 시분할 시스템으로 실행되는 것이고, 병렬성은 CPU core가 여러 개일 때, 각각의 core가 각각의 process를 연산하여 process가 동시에 실행되는 것입니다.

Multi process 환경에서는 프로세스 간 통신과 협력이 중요한 역할을 합니다. 공유 메모리, 메시지 큐의 메커니즘을 활용하여 프로세스 간 데이터 교환과 협력이 이루어집니다. 이러한 방식으로서 다양한 작업을 동시에 처리할 수 있습니다.

Multi process와 Multi thread의 차이를 설명해보세요.

두 개념 보두 동시성을 달성하는 데 사용되는 주요 방법입니다. Multi thread란 하나의 process가 동시에 여러 개의 일을 수행할 수 있도록 하는 것입니다. 즉, 하나의 process에서 여러 작업을 병렬로 처리하기 위해 Multi thread를 사용합니다. Multi process는 각각 독립된 메모리 공간을 가집니다.

  • Multi thread는 Multi process보다 적은 메모리 공간을 차지하고 Context Switching 시 캐시 메모리를 초기화할 필요가 없어 속도가 빠릅니다. 하지만 여러 thread가 동일한 자원에 동시 접근 하여 의도치 않은 값을 읽거나 수정하는 동기화 문제와 하나의 thread 장애로 전체 thread가 종료될 위험이 있습니다.
  • Multi process는 하나의 process가 죽더라도 다른 process에 영향을 주지 않아 안정성이 높습니다. 반면 Multi thread와 달리 process를 생성하고 자원을 할당하는 등의 system call이 있기 때문에 많은 메모리 공간과 CPU 시간을 차지합니다.
    따라서 시스템 설게 시 작업의 특성과 환경에 따라 다르게 선택해야 합니다. 예를 들어 웹 서버에서는 Multi process를 사용하여 안정성을 확보하고, 데이터베이스 서버에서는 Multi thread를 활용하여 빠른 응답을 제공하는 것이 효과적일 수 있습니다.

Multi process 환경에서 process 간 데이터를 어떻게 주고 받는지 설명해보세요.

원칙적으로 process는 독립적인 주소 공간을 갖기 때문에 다른 process의 주소 공간을 참조할 수 없습니다. 하지만 경우에 따라 운영체제는 process 간의 자원 접근을 위한 메커니즘, IPC(Inter Process Communication)를 제공합니다.

이러한 프로세스 간 통신 방법으로는 pipe, 소켓, 공유 메모리 등이 있습니다.
pipe는 단뱡향으로 데이터를 전송할 수 있으며 주로 부모-자식 프로세스 간 통신에 사용됩니다.

소켓은 네트워크 통신을 위한 IPC 방법으로 사용되며, 클라이언트와 서버 사이에서 데이터를 주고 받을 수 있습니다.

공유 메모리는 통신이 아닌, 데이터 자체를 공유하도록 지원합니다. 프로세스 간 메모리 영역을 공유해서 사용하도록 허용해주는 역할을 합니다.

IPC 방법을 선택할 때는 상황에 따라 다릅니다. 파이프는 간단한 통신에, 소켓은 네트워크 통신에 적합합니다. 공유 메모리는 성능을 우선시하고자 할 때 유용합니다. 보안 측면에서는 소켓이나 파이프보다는 공유 메모리가 더 취약할 수 있습니다.

참고: tech-interview-for-developer : gyoogle github repository

process 생애 주기에 대해 설명해보세요.

하나의 process는 여러 가지 상태를 가지며, 주로 실행-준비-대기 상태 등이 있습니다. process는 처음에 준비 상태에서 시작하여 CPU를 할당 받아 실행 상태로 전환됩니다. 그 후 input output 작업이나 이벤트 발생 등으로 대기 상태에 전환될 수도 있고, 다른 process가 CPU를 요청할 때 준비 상태도 전환될 수 있습니다.

이때 process는 매우 짧은 시간동안 CPU를 점유하여 일정 부분의 명령을 수행하고, 다른 process에게 넘깁니다. 그 후 차례가 되면 다시 CPU를 점유하여 명령을 수행합니다. 따라서 이전에 어디까지 수행했고, register에는 어떤 값이 저장되어 있었는지에 대한 정보가 필요하게 되는데 이런 총제적인 정보가 바로 context입니다. context는 PCB(Process Control Block)에 저장됩니다.

PCB는 운영 체제가 프로세스를 표현한 자료구조입니다. 프로세스 상태, 고유 번호, 다음 실행할 명령어 주소, register 값, 메모리 제한 등 프로세스의 중요한 정보가 담겨 있어 보호된 메모리 영역 안에 저장됩니다.

process끼리 CPU 제어권이 옮겨지는 것을 Context switch라고 합니다. 이때 이전의 프로세스 상태를 PCB에 저장하여 보관하고 새로운 프로세스의 PCB를 읽어서 보관된 상채를 복구하는 작업이 이루어집니다. Context switch의 비용을 최소화하기 위해서는 process 스케줄링 알고리즘의 효율적인 설계와 멀티코어 프로세싱을 활용하는 등의 방법이 사용됩니다.

deadlock은 언제 발생하게 되나요?

deadlock은 둘 이상의 process나 스레드가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말합니다.

dealock은 상호 배제, 점유 대기, 비선점, 순환 대기 조건이 동시에 성립해야 발생합니다. 상호 배제는 한번에 한 process만 점유할 수 있는 상황이고, 점유 대기는 process가 자원을 보유한 상태에서 다른 process가 해당 자원을 추가적으로 기다리고 있는 상황입니다. 비선점은 다른 process가 사용 중인 자원을 강제로 선점할 수 없는 상황이고, 순환 대기는 대기 중인 process들이 순환 형태로 자원을 대기하는 상황을 말합니다.

예를 들어 두 개의 프로세스 A, B가 각각 자원 X, Y를 보유하고, 서로가 가진 자원을 대기하면서 무한 대기 상태에 빠진다고 가정할 수 있습니다. 이때 A는 X를 가지고 있는 동시에 B가 가진 Y를 기다리고 있고, 반대로 B는 Y를 가지고 있는 동시에 A가 가진 X를 기다리고 있어 순환 대기 조건이 성립하게 됩니다.

deadlock은 어떻게 해결할 수 있나요?

deadlock의 해결방법으로는 무시, 예방, 회피, 탐지-회복이 있습니다.

무시는 deadlock 발생 확률이 낮은 시스템에서 아무런 조치를 취하지 않고 deadlock을 무시하는 방법입니다. 현대 시스템에서는 deadlock이 잘 발생하지 않고, 시스템 성능 저하가 없기 때문에 무시 기법이 많이 사용됩니다.

예방은 deadlock 상태 발생 조건 중 하나를 제거하는 기법입니다. 예를 들어 자원에 고유번호를 할당한 후 순서대로 자원을 요구하는 순환 대기 조건이 성립하지 않도록 하는 것이 가장 현실적입니다. 그러나 자원 사용의 효율성이 떨어지고 비용이 크다는 것이 단점입니다.

회피는 process가 앞으로 자원을 어떻게 요청할 지에 대한 정보를 통해 순환 대기 상태가 발생하지 않도록 자원을 할당하는 기법입니다. 대표적인 예로 은행원 알고리즘, 자원 할당 그래프 알고리즘을 사용하여 자원을 할당하여 deadlock을 회피합니다. 이 기법은 자원 요청에 대한 정보가 미리 알려져 있어야 하는 제약이 있습니다.

마지막으로 탐지-회복은 시스템 검사로 deadlock 발생을 탐지하고, 이를 회복하는 기법입니다. deadlock 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제시켜 회복합니다. 이 기법은 예방과 마찬가지로 자원 사용의 효율성이 떨어지고 비용이 크다는 것이 단점입니다.

이러한 방법은 각각의 장단점이 있으며, 상황과 시스템 요구에 따라 적절한 방법을 선택해야 합니다.

Race Condition에 대하여 간단한 예시를 들어 설명해 주세요.

Race Condition은 여러 프로세스나 스레드가 동시에 공유된 자원을 조작할 때 타이밍에 따라 결과가 달라질 수 있는 상황을 의미합니다.

예를 들어 동시에 실행되는 두 스레드 A, B가 공유 변수 balance에 동시에 접근하며, 각각의 스레드는 데이터에 입금 및 출금하는 로직을 수행한다고 가정하겠습니다. 만약 스레드 A가 balance를 읽고 200을 출금하려는 도중, 스레드 B가 balance를 읽고 100을 입금한다면 서로의 작업이 겹쳐서 balance에 대한 최종값이 예측 불가능해질 수 있습니다.

이러한 Race Condition을 방지하기 위해서는 동기화 메커니즘이 필요합니다. 대표적으로 뮤텍스를 사용할 수 있습니다. 뮤텍스는 상호배제를 제공하여 임계 구역에 대한 동시 접근을 막는 동기화 메커니즘입니다. 뮤텍스는 공유 자원을 점유하는 thread가 lock을 걸면, 다른 thread는 unlock 상태가 될 때까지 해당 자원에 접근할 수 없도록 합니다. 해당 기법을 통해 한 번에 하나의 스레드만이 공유 자원에 안전하게 접근할 수 있도록 만들 수 있습니다.

뮤텍스와 세마포어 차이점에 대해 설명해 주세요.

뮤텍스와 세마포어 둘 다 동기화 메커니즘으로, 여러 프로세스 또는 스레드 간에 공유된 자원에 안전하게 접근하기 위해 사용됩니다.

뮤텍스는 mutual exclusion, 상호 배제의 약어로, 임계 구역에 대한 동시 접근을 막는 데 사용됩니다. 공유 자원에 접근할 수 있는 프로세스 및 스레드 수를 1개로 제한합니다. 뮤텍스는 주로 lock, unlock의 두 가지 연산을 통해 구현됩니다.

세마포어는 공유 자원에 대한 접근을 여러 프로세스 또는 스레드로 제한할 수 있습니다. 변수 세마포에 접근 가능한 자원의 수를 저장하고 임계 영역 출입 여부에 따라 해당 변수를 제어합니다. 세마포어는 주로 P(wait), V(signal)의 두 가지 기본 연산을 통해 구현됩니다.

CPU 스케줄링은 왜 필요하나요?

스케줄링은 프로세스가 생성되고 실행될 떄 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미합니다. 실행되고 있는 프로세스에게 CPU가 공평하게 할당되고, 응답 시간과 반환 시간을 최소화하기 위해 필요한 작업입니다. 특히나 다중 프로그래밍 환경에서는 CPU는 한정된 자원이기 때문에 이 작업을 최대한 활용하려 대기 중인 프로세스들이 적절한 시간에 실행되도록 해야합니다.

요약하자면, CPU 스케줄링은 시스템의 공평성, 응답성, 효율성을 향상시키기 위한 핵심적인 관리 작업으로써 필요합니다.

CPU 스케줄링의 종류와 각 종류 별 예시를 하나 들어주세요.

스케줄링은 우선순위가 높은 프로세스가, 실행되고 있는 프로세스의 CPU를 강제로 뺴앗을 수 있는 여부에 따라 선점, 비선점으로 구분됩니다.

비선점 스케줄링은 프로세스 응답 시간의 예측이 용이하지만, 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생할 수 있습니다. 대표적인 예로 First Come First Served가 있습니다. 큐에 도착한 순서대로 CPU가 할당되는 것을 특징으로 가집니다.

선점 스케줄링은 우선순위가 높은 프로세스가 빠르게 처리되지만 많은 오버헤드를 발생시킬 수 있습니다. 대표적인 예로 Round Robin이 있습니다. 앞서 제시한 FCFS에 의해 프로세스들의 보내지면 각 프로세스는 동일한 시간의 최소 단위 시간만큼 CPU를 할당 받습니다. 즉, 할당 시간이 크면 FCFS와 동일하게 작동되고, 작으면 Context Switching이 잦아져서 오버헤드가 증가합니다.

스케줄링은 다양한 방식으로 CPU를 효과적으로 관리하고 각각의 장단점이 있습니다. 그래서 운영체제의 목적, 사용 환경에 따라 선택하는 종류가 달라집니다.

자료 구조

stack이 무엇이며, 어떤 상황에서 사용되는지 설명해 주세요.

stack은 LIFO(Last In First Out)의 자료구조입니다. 시간복잡도는 원소를 추가하는 push의 경우 O(1), 가장 마지막에 추가한 원소를 뽑아내는 pop의 경우 O(1)입니다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있습니다.

stack 두 개를 이용하여 queue를 구현해 주세요.

enqueue를 구현하는 stack을 instack, dequeue를 구현하는 stack을 outstack이라고 가정하겠습니다. 첫 번째로 enqueue하는 것은 stack의 push와 동일하게 구현할 수 있습니다. dequeue를 구현하기 위해서 instack을 pop한 것을 순서대로 outstack에 push합니다. instack이 빌 때까지 해당 작업을 수행한 뒤 outstack을 pop하면 dequeue를 구현할 수 있습니다.

// javascript
class Queue {
  constructor() {
    this.instack = [];
    this.outstack = [];
  }
  enqueue(element) {
    this.instack.push(element);
  }
  dequeue() {
    if (this.outstack.length === 0) {
      if (this.instack.length === 0) {
        throw new Error("Cannot dequeue, already empty");
      }
      while (this.instack.length > 0) {
        this.outstack.push(this.instack.pop());
      }
    }
    return this.outstack.pop();
  }
}
# python
class Queue(object):
  def __init__(self):
    self.instack=[]
    self.outstack=[]

  def enqueue(self,element):
    self.instack.append(element)

  def dequeue(self):
    if not self.outstack:
        if not self.instack:
          raise Exception("Cannot dequeue, already empty")
        while self.instack:
          self.outstack.append(self.instack.pop())
    return self.outstack.pop()

stack을 사용하여 괄호 검사를 수행하는 알고리즘에 대해 설명해 주세요.

검사할 문자열을 처음부터 하나씩 꺼내 여는 괄호(()에 해당하면 stack에 push합니다. 만약 닫는 괄호())에 해당하면 stack에 여는 괄호를 pop합니다. 이 경우 stack이 비어 있다면 올바른 괄호로 이루어진 문자열이 아닌 것을 파악할 수 있습니다.

해당 알고리즘은 코드 편집기나 컴파일러에서 괄호의 쌍을 확인하여 문법 오류를 방지하는 데 활용할 수 있습니다.

원형 queue와 일반 queue의 차이점에 대해 설명해 주세요.

원형 queue는 크기가 정해져 있는 array-based queue를 구현할 때 주로 쓰는 형식입니다.

front가 가장 첫 인덱스로 고정되어 있지 않고, dequeue에 따라서 이동합니다. rear 또한 enqueue에 의해 뒤로 이동하며 인덱스가 queue의 크기를 넘어설 경우 0으로 이동하여 구현합니다. 따라서 enqueue와 dequeue 과정에서 남는 메모리가 생길 수 있습니다.

일반 queue는 크기가 정해져 있지 않는 list-based이며 재할당이나 메모리 낭비의 걱정을 할 필요가 없습니다.

우선순위 큐에 대해 설명하고, 어떤 상황에서 이를 활용할 수 있을지 설명해 주세요.

시간순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 queue가 priority queue입니다.

활용 예시로는 하나의 자원을 공유하는 프린터나, CPU task scheduling, Cache구현, 너비우선탐색(BFS) 등이있습니다.

queue 두 개를 이용하여 stack을 구현해 주세요.

queue1, queue2가 있다고 가정하겠습니다. push를 구현하기 위해 queue1에 enqueue합니다. pop을 구현하기 위해서는 queue1의 원소의 개수가 1이 될 때까지 queue1을 dequeue하여 queue2에 enqueue합니다. queue1에 하나 남은 원소를 dequeue하여 pop의 결과를 반환합니다. 마지막으로 queue1과 queue2를 swap하여 다음 pop을 대비하면 됩니다.

// javascript
class Stack(){
  constructor(){
    this.queue1 = []
    this.queue2 = []
  }
  push(element){
    this.queue1.push(element)
  }
  pop(){
    if (this.queue1.length === 0){
      throw new Error("Cannot pop, alreay empty")
    }
    while (this.queue1.length > 1){
      this.queue2.push(this.queue1.shift())
    }
    const poppedElement = this.queue1.shift()
    [this.queue1, this.queue2] = [this.queue1, []]
    return poppedElement
  }
}

# python
import queue

class Stack(object):
  def __init__(self):
    self.q1 = queue.Queue()
    self.q2 = queue.Queue()

  def push(self, element):
    self.q1.put(element)

  def pop(self):
    if self.q1.qsize() == 0:
      raise Exception("Cannot pop, alreay empty")
    while self.q1.qsize() > 1:
      self.q2.put(self.q1.get())

    popped_element = self.q1.get()
    self.q1, self.q2 = self.q2, queue.Queue()

    return popped_element

동적 배열(Dynamic Array)의 개념과 장점에 대해 설명하고, 내부 구현 방식에 대해 이야기해 주세요.

정적 배열인 Array는 size가 고정되어 있어, 선언시에 설정한 size보다 많은 갯수의 요소를 추가할 수 없습니다. 이때, 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 메모리 블록에 할당합니다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제합니다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 합니다.

Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하기 때문에 size를 예측할 수 없는 상황에서 유용합니다.

연결 리스트(Linked List)의 특징과 배열(Array)과의 비교점에 대해 설명해 주세요.

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조입니다. Linked List는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다.

그래서 각 operation의 시간복잡도가 다릅니다. 데이터 조회는 Array의 경우 O(1), Linked List는 O(n)의 시간복잡도를 갖습니다. 삽입/삭제에서 Array의 경우 O(n), Linked List는 O(1)의 시간복잡도를 갖습니다.

따라서 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회를 많이 한다면 Array를 사용하는 것이 좋습니다. 반면에 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked List를 사용하는 것이 유리합니다.

Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.

Linked List와 비교했을 때, Dynamic Array의 장점은 데이터 접근과 할당이 O(1)로 굉장히 빠릅니다. 이는 index 접근하는 방법이 산술적인 연산 [배열 첫 data의 주소값] + [offset]으로 이루어져 있기 때문입니다. 그리고 Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠릅니다.(O(1))

Linked List와 비교했을 때, Dynamic Array의 단점은 Dynamic Array의 맨 끝이 아닌 곳에 data를 삽입 또는 제거할 때, 느린 편입니다(O(n)). 느린 이유는 메모리상에서 연속적으로 데이터들이 저장되어 있기 때문에, 데이터를 추가 삭제할 때 뒤에 있는 data들을 모두 한칸씩 shift 해야되기 때문입니다. 그리고 Dynamic Array의 특성 상 resize를 해야할 때, 예상치 못하게 현저히 낮은 performance가 발생합니다. resize에 시간이 많이 걸리므로 필요한 것 이상 memory공간을 할당받습니다. 따라서 사용하지 않고 있는 낭비되는 메모리공간이 발생합니다.

단일 연결 리스트와 이중 연결 리스트의 차이에 대해 설명하고, 각각의 장단점을 언급해보세요.

Linked List는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 이루어진 자료 구조입니다. 이때 가리키는 방향이 다음 노드 뿐일 때, 단일 연결 리스트라 말하고, 가리키는 방향이 이전 노드도 포함되어 있을 때 이중 연결 리스트라고 말합니다.

단일 연결 리스트는 메모리를 효율적으로 사용하고 삽입 및 삭제가 간편하지만 역방향 탐색이 어렵다는 단점을 가지고 있습니다. 이중 연결 리스트는 양방향 탐색이 가능하고 역방향으로 노드를 삽입하고 삭제하기 용이합니다. 반면 단일 연결 리스트와 비교하여 메모리 사용량이 더 많고 복잡한 구현이 필요하다는 단점을 가지고 있습니다.

// javascript
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class DoubleNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}
# python
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

class DoubleNode:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

연결 리스트를 사용하여 역순으로 노드를 출력하는 알고리즘에 대해 설명해 주세요.

# python
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

def reverse_and_print(head):
  prev = None
  current = head

  while current:
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node

  while prev:
    print(prev.data)
    prev = prev.next

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
reverse_and_print(head)
// javascript
class Node {
  constructor(data) {
    this.data = data;
    self.next = null;
  }
}

function reverseAndPrint(head) {
  let prev = null;
  let current = head;

  while (current) {
    let nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }

  while (prev) {
    console.log(prev.data);
    prev = prev.next;
  }
}

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
reverseAndPrint(head);

힙(Heap)의 개념을 설명하고, 최소 힙(Min Heap)과 최대 힙(Max Heap)의 차이에 대해 이야기해보세요.

Heap은 우선순위큐(priority queue)로 만들어진 자료구조입니다. Heap은 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 등에 활용될 수 있습니다.

Heap은 완전이진트리 구조를 가집니다. 트리는 보통 Linked list로 구현하지만 Heap은 tree임에도 불구하고 array를 기반으로 구현해야 합니다. 그 이유는 새로운 node를 힙의 ‘마지막 위치’에 추가해야 하는데, 이 때 array기반으로 구현해야 이 과정이 수월해지기 때문입니다. 예를 들어 부모 노드의 인덱스가 i라면 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1가 됩니다.

Heap이 되기 위한 조건은 최소 힙인지 최대 힙인지에 따라 나뉩니다. 최소 힙일 경우 첫째, 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다. 둘째, root node에 저장된 값이 가장 작은 값이 된다. 최대 힙일 경우 반대가 됩니다. 따라서 dequeue를 할 때마다 최소 힙일 경우 항상 트리 내의 가장 작은 값이 도출되고, 최대 힙일 경우 항상 트리 내의 가장 큰 값이 도출됩니다.

해시 테이블(Hash Table)을 사용하여 데이터를 검색하는 과정과 시간 복잡도를 설명해보세요.

Hash Table은 효율적인 탐색을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다. Hash Function에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다. 삽입, 삭제, 검색의 시간복잡도는 모두 O(1)입니다.

해시 함수(Hash Function)의 역할과 특징을 설명해보세요.

Hash Function은 Hash Table에서 key값을 인자로 하고 메모리 슬롯 index, 즉 해시값을 반환하는 함수로, 데이터 값을 해시 값으로 매핑하는 역할을 가지고 있습니다.

각 상황마다 좋은 Hash Function은 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 합니다.

해시 충돌(Hash Collision)이 발생하는 경우의 해결 방법에 대해 설명하고, 각 방법의 장단점을 언급해보세요.

Hash Collision이란 서로 다른 key의 해시값이 똑같은 경우를 말합니다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이 때 collision이 발생했다고 합니다.

따라서 collision이 최대한 적게 나도록 Hash Function을 잘 설계해야하고, 어쩔 수 없이 collision이 발생하는 경우 연결리스트로 노드를 계속 추가해나가는 seperate chaining 방법을 선택할 수 있습니다. 쉽고 간단하게 구현이 가능하지만 메모리 소비가 증가하는 단점을 가지고 있습니다. 또는 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용하는 open addressing등의 방법을 사용하여 해결합니다. 이는 추가적인 메모리 사용이 적지만 클러스터링과 선형 검색에 의한 성능 저하가 발생할 수 있습니다.

트리(Tree)의 기본 개념을 설명하고, 이진 트리(Binary Tree)의 특징에 대해 이야기해보세요.

트리는 계층 구조를 표현하는 자료구조로, 값을 가진 node와 노드들을 이어주는 edge로 이루어집니다. 트리에는 사이클이 존재할 수 없고, 루트에서 어느 노드로 가는 경로는 유일합니다. 그리고 노드의 개수가 N개 이면 간선은 N-1개로 정해져 있습니다.

이진 트리는 각 노드가 최대 두 개의 자식 노드을 가지는 트리 구조입니다. 이진 트리 높이가 h라면, 노드의 수는 최소 h, 최대 2^(h+1)-1개 입니다. 이진 트리는 정렬된 데이터를 효율적으로 탐색하기 위해 사용될 수 있습니다.

이진 탐색 트리(Binary Search Tree)의 개념과 장점에 대해 설명하고, 탐색 연산에 대한 시간 복잡도를 언급해보세요.

이진 탐색 트리는 이진 트리 자료구조에서 두 가지 특징을 더한 자료구조입니다. 첫째, 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 커야 합니다. 둘째, 중복된 노드가 없어야 합니다. 이진 탐색 트리의 순회는 왼쪽-루트-오른쪽 순인 중위순회 방식을 가집니다.

탐색 연산에서 균등 트리일 경우 O(logn)을 가지고, 편향 트리인 경우 O(n)을 시간 복잡도로 가집니다.

트리 순회(Tree Traversal) 방법 중 중위(In-order) 순회에 대해 설명하고, 어떤 상황에서 유용한지 알려주세요.

중위 순회는 왼쪽-루트-오른쪽 순으로 순회하는 방식입니다. 이 순회 방식은 이진 탐색 트리에서 노드를 오름차순으로 방문할 수 있게 합니다.

알고리즘

Binary Search에 대해 아는대로 설명해 주세요.

Binary search는 탐색 범위를 두 부분으로 분할하면서 찾는 방식으로 O(N)의 시간복잡도를 갖는 완전탐색에 비해 O(logN)의 시간복잡도를 가져 효율적입니다. 정렬된 상태에서만 사용 가능한데, 이는 중간값을 찾아내어 찾고자 하는 값이 중간값보다 작으면 왼쪽 부분, 크면 오른쪽 부분으로 범위를 좁혀가는 방식으로 동작하기 때문입니다.

탐색 범위를 양 끝을 의미하는 left, right pivot을 정하고 중간값에 해당하는 middle의 값을 구하고자 하는 값과 비교합니다. 이 때 구할 값이 middle보다 큰 경우 left= middle+1, 구할 값이 middle보다 낮은 경우 right=middle-1로 지정합니다. 이를 left가 right의 값을 넘어설 때까지 반복합니다.

Bubble Sort에 대해서 아는대로 설명해 주세요.

Bubble Sort는 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다.

1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 마지막-1 번째 원소와 마지막 번째 원소를 비교하여 조건에 맞지 않으면 교환합니다. 1회전을 수행하면 가장 큰 원소가 맨 뒤로 이동하므로 2회전은 마지막-2 번째 원소와 마지막-1 번째 원소까지만 비교합니다.

// javascript
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 1; j < arr.length - i; j++) {
      if (arr[j - 1] > arr[j]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      }
    }
  }
  return arr;
}
# python
def bubbleSort(arr):
  for i in range(len(arr)):
    for j in range(1, len(arr)-i):
      if arr[j-1] > arr[i]:
        arr[j-1], arr[j] = arr[j], arr[j-1]
  return arr

bubble sort의 시간복잡도는 O(N^2)입니다. 기존 원소의 정렬 유무와 관계 없이 전체 탐색을 통해 원소를 비교하므로 최선, 평균, 최악의 경우 모두 시간복잡도가 동일합니다. 공간복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)입니다.

구현이 간단하고, 제자리 정렬로 별도의 메모리 공간을 필요로 하지 않는 것이 장점이지만, 시간복잡도가 전부 O(N^2)이므로 비효율적입니다.

Selction Sort에 대해서 아는대로 설명해 주세요.

Selection Sort는 정렬 순서에 따라 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 정렬 알고리즘입니다.

오름 차순 정렬이라고 가정하겠습니다. 주어진 배열 중에 최솟값을 찾고 그 값을 맨 앞에 위치한 값과 교체합니다. 그런 다음 맨 처음 위치를 뺀 나머지 배열을 동일한 방법으로 교체합니다.

// javascript
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    [arr[minIdx], arr[i]] = [arr[i], arr[minIdx]];
  }
  return arr;
}
# python
def selectionSort(arr):
  for i in range(len(arr)-1):
    minIdx = i
    for j in range(i+1, len(arr)):
      if arr[j] < arr[minIdx]:
        minIdx = j
    arr[minIdx], arr[i] = arr[i], arr[minIdx]
  return arr

selection sort의 시간복잡도는 O(N^2)입니다. 최선, 평균, 최악의 경우도 동일합니다. 공간복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)입니다.

정렬을 위한 비교 횟수는 많지만 실제 교환 횟수는 최솟값을 N번 교환하기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다. 또한 제자리 정렬로 별도의 메모리 공간을 필요로 하지 않는 것이 장점입니다. 반면 시간복잡도가 비효율적이며 불안정 정렬입니다.

Insertion Sort에 대해서 아는대로 설명해 주세요.

Insertion Sort는 두 번째 원소부터 시작하여 앞의 원소와 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기면서 지정된 자리에 삽입하여 정렬하는 알고리즘입니다.

// javascript
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let prev = i - 1;
    while (prev >= 0 && arr[prev] > temp) {
      arr[prev + 1] = arr[prev];
      prev -= 1;
    }
    arr[prev + 1] = temp;
  }
  return arr;
}
# python
def insertionSort(arr):
  for i in range(len(arr)):
    temp = arr[i]
    prev = i - 1
    while prev >=0 and arr[prev] > temp:
      arr[prev+1] = arr[prev]
      prev -= 1
    arr[prev+1] = temp
  return arr

Insertion Sort의 시간복잡도는 평균, 최악의 경우 O(N^2)입니다. 그러나 모두 정렬이 되어있는 경우 한 번씩만 비교를 하므로 O(N)의 시간복잡도를 가집니다. 공간복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)입니다.
단순하고, 이미 정렬된 경우 매우 효율적입니다. 제자리 정렬이자 안정 정렬인 것이 장점입니다. 평균과 최악의 경우 O(N^2)의 시간복잡도로 비효율적인 것이 단점입니다.

Quick Sort에 대해서 아는대로 설명해 주세요.

Quick sort는 분할 정복 알고리즘 중 하나입니다.

리스트 가운데서 하나의 원소를 고르고, 해당 원소를 피벗으로 설정합니다. 피벗 앞에는 피벗보다 작은 모든 원소들이, 뒤에는 피벗보다 큰 모든 원소들이 오도록 리스트를 둘로 나눕니다. 이러한 분할 작업 이후에는 피벗을 고정시켜 놓고, 두 분할된 리스트에 대해 재귀적으로 이 과정을 반복합니다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복합니다.

// javascript
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}
# python
def quickSort(arr):
  if len(arr) <= 1:
    return arr

  pivot = arr[0]
  left = [x for x in arr[1:] if x < pivot]
  right = [x for x in arr[1:] if x >= pivot]

  return quickSort(left) + [pivot] + quickSort(right)

Quick sort의 시간복잡도는 최선과 평균의 경우 O(N*logN)이며, 최악의 경우 O(N^2)가 될 수 있습니다. 공간복잡도는 최선과 평균의 경우 O(logN)이며, 최악의 경우 O(N)가 될 수 있습니다.

Quick sort는 평균적으로 매우 빠르며 제자리 정렬이라는 특징을 가지고 있습니다. 하지만 불안정 정렬이라는 단점을 가지고 있습니다.

참고: Algorithms — Quick Sort - Medium

Quick sort가 최악의 시간 복잡도를 가지는 경우 해결방안은 무엇인가요?

Quick sort는 피벗 선택이 최악의 경우, 리스트가 이미 정렬되어 있거나 피벗이 항상 최대 또는 최소값을 선택하는 경우 최악의 시간 복잡도를 가질 수 있습니다.

이런 경우 피벗을 무작위로 선택하거나 리스트 내의 중간값을 선택하는 방법을 통해 최악의 경우를 피할 수 있습니다.

Merge Sort에 대해서 아는대로 설명해 주세요.

Merge sort는 분할 정복 방법으로 구현되는 정렬 알고리즘입니다.

리스트를 더 작은 서브리스트로 나누는 분할 단계 다음, 각 서브리스트를 정렬하고 합병하는 과정을 재귀적으로 가집니다.

// javascript
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex += 1;
    } else {
      result.push(right[rightIndex]);
      rightIndex += 1;
    }
  }
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergesort(right));
}
# python
def merge(left, right):
  result = []
  leftIndex = rightIndex = 0

  while leftIndex < len(left) and rightIndex < len(right):
    if left[leftIndex] < right[rightIndex]:
      result.append(left[leftIndex])
      leftIndex += 1
    else:
      result.append(right[rightIndex])
      rightIndex += 1

  return result + left[leftIndex:] + right[rightIndex:]

def mergeSort(arr):
  if len(arr) <=1:
    return arr

  middle  = len(arr) // 2
  left = arr[:middle]
  right = arr[middle:]

  return merge(mergeSort(left), mergeSort(right))

Merge sort의 시간복잡도는 O(N*logN)이며 공간복잡도는 O(N)입니다.
최악의 경우에도 O(N*logN)의 시간복잡도를 가져 효율적인 편이고, 안정 정렬에 해당됩니다. 순차적인 비교로 정렬을 진행한다는 점에서 LinkedList의 정렬이 필요할 때 사용하면 효율적입니다. 하지만 병합된 서브리스트들을 저장하는 별도의 메모리가 필요해 공간 복잡도에서 비교적 비효율적일 수 있으며 작은 데이터셋에서는 다른 알고리즘에 비해 높은 시간 복잡도를 가집니다.

참고: Merge Sort – Data Structure and Algorithms Tutorials - geeksforgeeks

Heap Sort에 대해서 아는대로 설명해 주세요.

Heap sort는 Heap 자료구조를 기반으로 하는 정렬 알고리즘입니다. Heap은 완전 이진 트리로 구성되며 최대 힙 또는 최소 힙의 성질을 가집니다.

최대 힙을 사용하는 경우를 기준으로 힙 정렬 알고리즘에 대해 설명하겠습니다. 최대 힙을 생성한 후 루트 노드와 배열의 마지막 노드를 교환합니다. 힙의 크기를 1 감소시킨 다음 루트 노드에 대해 heapify를 재귀 호출하여 전체 트리를 최대 힙으로 만듭니다. 이 과정을 힙의 크기가 1이 될 때까지 반복합니다. 이 과정을 반복하면 정렬된 배열을 만들 수 있습니다.

// javascript
function heapify(arr, n, i) {
  let largest = i;

  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[largest] < arr[left]) {
    largest = left;
  }
  if (right < n && arr[largest] < arr[right]) {
    largest = right;
  }

  if (i !== largest) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

function heapSort(arr) {
  const n = arr.length;

  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }

  return arr;
}
# python
def heapify(arr, n, i):
  largest = i

  left = 2 * i + 1
  right = 2 * i + 2

  if left < n and arr[largest] < arr[left]:
    largest = left
  if right < n and arr[largest] < arr[right]:
    largest = right

  if i != largest:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

  return arr

def heapSort(arr):
  n = len(arr)

  for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)

  for i in range(n - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)

  return arr

Heap sort는 항상 O(N*logN)의 시간 복잡도를 가집니다. 힙 생성 단계에서 O(N), 각 heapify 단계에서 O(logN)의 시간이 소요되기 때문입니다. 힙 정렬은 추가적인 메모리 공간이 필요하지 않고 주어진 배열 자체에서 정렬을 수행하므로 공간 복잡도는 O(1)입니다.

Heap sort는 배열 자체에서 정렬을 수행하는 제자리 정렬이고 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도가 낮은 특성을 가집니다. 다만 숫자가 같은 경우에도 교환 및 heapify가 수행될 수 있기 때문에 Quick sort와 함께 불안정 정렬에 해당됩니다.

참고: 자료구조 개념 이해하기 '힙과 힙 정렬 알고리즘' - 요즘 IT [곰씨네 IT 블로그]

Radix Sort에 대해서 아는대로 설명해 주세요.

비교 정렬은 수학적인 한계로 최선의 시간복잡도가 O(N*logN)보다 개선될 수 없습니다.
그래서 비교하지 않고 수의 특성을 이용해 sort를 하는 것으로 시간복잡도를 개선시킬 수 있습니다.

Radix sort는 일의 자리부터 시작해 각 자릿수 별로 정렬한 결과를 0-9까지의 버킷에 담는 그룹화를 진행합니다. 목록으로 다시 구성할 때에는 버킷에 이미 있는 순서대로 두는 것을 최대 수의 자릿 수만큼까지 반복합니다. 자릿수를 선택하는 기준은 가장 큰 자릿수부터 그룹화하는 Most Significant Digit과 가장 작은 자릿수부터 그룹화하는 Least Significant Digit이 있습니다.

Radix sort는 k가 수의 자릿수일 때항상 O(N*k)의 시간복잡도를 가집니다. 공간복잡도는 O(N+k)만큼을 가집니다.
(여기서 모든 수가 고유하고 무작위로 분산된 데이터를 다룰 경우에는 k는 logN과 동일하게 작동됩니다.)

Radix Sort는 정수에 대해서 주로 사용되며, 음수 또는 부동 소수점 수와 같은 다른 형태의 숫자에는 적합하지 않을 수 있습니다. 또한, 알고리즘이 각 자릿수에 따라 정렬하기 때문에 정수의 자릿수가 크면 성능이 떨어질 수 있습니다.

Radix Sort의 장점은 안정성과 시간 복잡도의 선형성입니다. 그러나 데이터가 정수이어야 하며, 다른 정렬 알고리즘에 비해 상대적으로 느린 성능을 보일 수 있습니다. 이를 통해 Radix Sort의 특징과 한계를 잘 이해하면서 적절한 상황에서 사용할 수 있습니다.

Count Sort에 대해서 아는대로 설명해 주세요.

Count sort는 Radix sort과 마찬가지로 정수 내지 정수로 표현할 수 있는 자료에 대한 정렬 알고리즘 중 하나로, 비교 없이 특정 범위의 정수 자료를 정렬하는 데 효과적입니다.

먼저 정렬하는 데이터의 범위를 기반으로 각 값의 빈도를 저장하는 카운트 배열을 생성합니다. 입력 배열을 순회하면서 각 값의 빈도를 카운트 배열에 저장합니다. 그런 다음 카운트 배열의 요소를 누적합의 결과로 덮어씌워 각 값의 마지막 인덱스를 저장합니다. 입력 배열을 뒤에서부터 순회하면서 해당 값의 빈도를 이용해 정렬된 배열을 구성합니다. 정렬된 배열을 생성하면서 해당 값의 빈도를 감소시킵니다.

Count sort의 시간복잡도는 O(N*k)이고, 공간복잡도는 O(k)입니다.

안정 정렬이고 효율적인 시간복잡도를 가지지만 데이터가 정수 또는 정수로 표현 가능한 자료여야합니다.

데이터베이스

데이터 베이스에서 사용되는 키 다섯 가지를 설명해 주세요.

데이터 베이스에서의 키는 조건에 만족하는 레코드를 찾거나 정렬할 때 기준이 되는 속성 또는 속성의 집합을 뜻합니다. 이는 유일성, 최소성, 참조에 따라 다섯 가지가 있습니다.

슈퍼 키(Super Key)는 유일성만을 보장하는 키입니다. 어떤 속성의 조합이든 각 레코드를 구별할 수 있다면 해당 속성을 슈퍼 키가 될 수 있습니다.

후보 키(Candidate Key)는 유일성과 최소성을 모두 만족하는 키입니다. 슈퍼 키 중에서 최소성을 가진 키가 후보 키가 됩니다.

기본 키(Primary Key)는 릴레이션에서 각 레코드를 유일하게 식별하는 주요 키입니다. 후보 키 중 선택되며, 반드시 유일하고 NOT NULL입니다.

대체 키(Alternate Key)는 후보 키 중 기본 키는 제외한 나머지 모든 키입니다.

외래 키(Foreign Key)는 다른 릴레이션의 기본 키를 참조하는 키입니다. 외래 키를 통해 테이블간 관계 표현이 가능합니다.

DB에서 인덱스를 쓰는 이유에 대해 설명해 주세요.

인덱스는 데이터를 빠르게 찾을 수 있는 수단으로서, 테이블에 대한 조회 속도를 높여주는 자료 구조입니다. 테이블의 특정 레코드 위치를 빠르게 알려주는 용도로 쓰게 됩니다.

또한 인덱스를 사용하면 데이터가 정렬된 상태로 저장되므로 정렬된 결과를 빠르게 반환할 수 있습니다. 그리고 유니크 인덱스를 생성하여 중복된 값을 허용하지 않게 함으로써 데이터 무결성을 유지할 수 있습니다.

hash 테이블 시간복잡도는 O(1)로 트리보다 빠른데 왜 트리를 사용할까요?

hash 테이블은 일대일 대응 연산에만 특화되어 있어 범위 연산이 자주 사용되는 DB 검색에는 적합하지 않습니다. 더불어서 multi column index의 경우 전체 attributes에 대해 조회를 해야 합니다. 그리고 hash 충돌이 발생할 수 있기에 이를 위한 추가적인 작업이 필요할 수도 있습니다.

데이터베이스에서 정규화의 목적을 설명해 주세요.

가장 큰 목표는 테이블 간 중복된 데이터를 최소화하여 이상 현상을 방지하는 것입니다. 이를 통해 데이터 무결성을 유지하고, 불필요한 데이터를 최소화시킬 수 있습니다. 또한 테이블 구성을 논리적이고 직관적으로 할 수 있습니다. 마지막으로 데이터베이스 구조 확장이 용이해집니다.

제 1정규화에 대해 설명해 주세요.

테이블 컬럼이 하나의 값을 갖도록 테이블을 분리시키는 것을 말합니다. 어떤 릴레이션에 속한 모든 도메인이 원자값으로만 되어 있어야합니다.

제 2정규화에 대해 설명해 주세요.

제 1 정규형을 만족하고, 테이블의 모든 컬럼이 완전 함수적 종속을 만족하도록 분리시키는 것을 말합니다. 즉 기본 키에 종속적이지 않거나 기본 키 일부 컬럼들에만 종속적인 컬럼은 분리되어야 합니다.

제 3정규화에 대해 설명해 주세요.

제 2 정규형을 만족하고, 테이블에서 이행적 종속을 없애기 위해 분리시키는 것을 말합니다. 속성에 종속적인 속성은 분리되어야 합니다.

이상 현상에 대해 설명해 주세요.

이상 현상이란 릴레이션 조작 시 예기치 않게 발생하는 곤란한 현상입니다. 이상 현상의 종류로 삽입, 삭제, 갱신 이상이 있습니다.

삽입 이상은 릴레이션에 데이터를 삽입할 때 의도와는 상관없이 원하지 않은 값들도 함께 삽입되는 현상입니다. 예를 들어 어떤 테이블에 직원의 정보를 저장하는데, 특정 부서에 아직 소속되지 않은 직원의 데이터를 삽입할 때 부서 정보가 없어 삽입이 불가능한 경우를 들 수 있습니다.
삭제 이상은 릴레이션에서 한 레코드를 삭제할 때 의도와는 상관없는 값들도 함께 삭제되는 연쇄가 발생하는 현상입니다. 예를 들어 부서 정보가 특정 직원에게만 연결돼 있고 그 직원이 퇴사하면서 부서 정보도 함께 삭제되는 경우가 있을 수 있습니다.

갱신 이상은 릴레이션에서 레코드에 있는 속성값을 갱신할 때 일부 레코드의 정보만 갱신되어 정보의 모순이 생기는 현상입니다. 예를 들어 부서 정보가 여러 직원에게 중복되어 저장되어 있고, 부서 정보를 수정할 때 일부 직원만 수정되어 일관성이 깨질 수 있습니다.

ERD에 대해 설명해 주세요.

ERD(Entity Relationship Diagram)는 요구 분석 사항에서 얻은 엔티티와 속성들의 관계를 그림으로 나타낸 개체-관계 모델입니다.

엔티티는 정의 가능한 사물 또는 개념을 의미하고 이는 곧 데이터베이스의 테이블이 됩니다.
엔티티 속성은 개체가 가지고 있는 속성을 포함합니다. 이는 곧 테이블의 각 필드가 됩니다.

ERD 엔티티 관계에 대해 설명해 주세요.

엔티티 관계는 외래 키를 어떤 것으로 갖느냐에 따라 식별자/비식별자 관계로 먼저 구분할 수 있습니다. 부모 자식 관계에서 자식의 외래 키가 부모의 기본 키를 그대로 따르면 식별자 관계로 표현할 수 있습니다. 반면 부모의 기본 키를 외래 식별자로 참조해서 일반 속성으로 사용할 경우 비식별자 관계로 표현할 수 있습니다.

한 개체에서 발생할 수 있는 횟수인 카디널리티에 따라서도 일대일/일대다/다대다 관계로 구분할 수 있습니다.

데이터 무결성 세 가지에 대해 설명해 주세요.

데이터 무결성은 데이터베이스에서 데이터의 정확성과 일관성을 유지하고 보장하는 중요한 개념입니다. 이 유형에는 개체 무결성, 참조 무결성, 도메인 무결성이 있습니다.

개체 무결성은 모든 테이블이 기본 키를 가져야 하며 기본 키로 선택된 속성은 고유하여야 하고, NOT NULL임을 규정합니다.

참조 무결성은 외래 키의 개념과 관련있으며 모든 외래 키 값은 기본 키 값을 참조함을 규정합니다.

도메인 무결성은 데이터의 모든 열이 정의된 범위에서 선언되도록 규정합니다. (예시. 나이는 음수가 될 수 없음)

트랜잭션에 대해서 설명해 주세요.

트랜잭션은 데이터베이스의 상태를 변화시키기 위해 수행하는 작업 단위입니다. 트랜잭션은 ACID 특징을 갖고 있습니다. Atomicity, 원자성은 트랜잭션을 구성하는 연산 전체가 DB에 모두 반영되거나 혹은 취소되어야 하는 성질입니다. Consistency, 일관성은 시스템이 가지고 있는 고정요소는 트랜잭션 수행 전과 후의 상태가 같아야 하는 성질입니다. Isolation, 독립성은 둘 이상의 트랜잭션이 동시에 병행 실행되고 있을 때 서로의 연산에 끼어들 수 없는 성질입니다. Durability, 지속성은 트랜잭션이 성공적으로 완료되었으면 결과는 영구적으로 반영되어야 하는 특징입니다.

트랜잭션 연산에 대해 설명해 주세요.

트랜잭션 연산에는 Commit과 Rollback이 있으며 두 연산에 의해 원자성을 보장받습니다. Commit은 하나의 트랜잭션이 성공적으로 끝나고, DB가 일관성 있는 상태에 있거나 하나의 트랜잭션이 끝났을 때 사용하는 연산입니다. Rollback은 하나의 트랜잭션이 비정상적으로 종료되어 트랜잭션 원자성이 깨질 경우 처음부터 다시 시작하거나 부분적으로 연산을 취소하는 연산입니다.

트랜잭션이 Isolation을 보장하는 방법에 대해 설명해 주세요.

다른 트랜잭션이 현재의 데이터에 대한 무결성을 해치지 않기 위해 잠금을 설정하는 격리 수준을 정할 수 있습니다. 격리 수준은 여러 트랜잭션이 동시에 실행될 때 발생할 수 있는 문제를 제어하기 위한 메커니즘입니다.

레벨 0의 격리 수준은 Read Uncommitted에 해당합니다. 트랜잭션이 처리 중이거나, 아직 Commit되지 않은 데이터를 다른 트랜잭션이 읽는 것을 허용합니다. 이는 DB의 일관성을 유지하는 것이 불가능하기 때문에 Dirty Read, Non-repeatable Read, Phantom Read 문제가 발생할 수 있습니다.

레벨 1의 격리 수준은 Read Committed에 해당합니다. 트랜잭션이 수행되는 동안 다른 트랜잭션이 데이터에 접근할 수 없어 대기하게 됩니다. Commit이 이루어진 트랜잭션만 조회가 가능한 수준입니다. 따라서 Dirty Read는 발생하지 않지만 여전히 Non-repeatble Read는 발생할 수 있습니다.

레벨 2의 격리 수준은 Repeatable Read에 해당합니다. 이는 다른 사용자가 트랜잭션 영역에 해당되는 데이터에 대해 수정을 불가능하게 합니다. 트랜잭션이 범위 내에서 조회한 데이터 내용이 항상 동일함을 보장합니다. 따라서 Non-repeatble Read는 방지됩니다.

마지막 Serializable은 다른 사용자가 트랜잭션 영역에 해당되는 데이터에 대한 수정, 입력을 불가능하게 합니다. 완벽한 읽기 일관성 모드를 제공하여 Phantom Read를 방지합니다.

트랜잭션 격리 수준을 선택하는 기준에 대해 설명해 주세요.

Read Uncommitted는 성능이 중요하고 데이터 일관성이 크게 중요하지 않은 경우에 사용될 수 있습니다.

Read Committed는 대부분의 시스템에서 기본적으로 사용되며, 일반적인 요구 사항을 충족합니다.

Repeatble Read 또는 Serializable은 데이터 일관성이 매우 중요하며, 동시에 여러 트랜잭션이 발생할 가능성이 높은 경우 선택됩니다.

각 격리 수준은 일관성과 성능 간의 트레이드오프를 나타내며, 특정 상황에 맞게 선택되어야 합니다.

RDB의 특징에 대해 설명해 주세요.

RDB, 관계형 데이터베이스는 데이터가 하나 이상의 열과 행의 테이블에 저장되어 서로 다른 데이터 구조가 어떻게 관련되어 있는지 쉽게 파악하고 이해할 수 있도록 구성된 데이터 베이스입니다.

참고: 관계형 데이터베이스란 무엇인가요? - Google Cloud

RDB의 장점으로는 정형화된 데이터를 저장하기 때문에 스키마에 따라 데이터의 형태와 크기를 미리 정할 수 있다는 것이 있습니다. 그리고 트랜잭션을 통해 ACID를 보증하여 안정적인 데이터 관리가 가능합니다. JOIN과 같이 복잡한 조건을 포함하는 데이터 검색이 가능합니다. 데이터 무결성을 개선하는 정규화 기법을 사용할 수 있습니다.

NoSQL이 나오게 된 이유와 종류에 대해 설명해 주세요.

웹의 성장에 따라 멀티미디어 데이터와 같은 비정형 데이터가 빠른 속도로 대량 생산되고 있습니다. 이런 환경에서 RDB를 적용하면, 데이터의 스키마가 이미 정해져 있어 속성을 자주 추가하고 조정하기에 적합하지 않습니다. 또한 관계를 맺고 있기 때문에 JOIN이 많은 복잡한 쿼리가 만들어질 수 있습니다.

즉 대량의 비정형 데이터의 저장과 유연한 처리를 위해 새로운 대안으로 제시된 것이 NoSQL입니다.

NoSQL 종류에는 대표적으로 MongoDB, Redis 등이 있습니다. MongoDB는 JSON을 통해 데이터에 접근할 수 있고, Document 기반의 DB입니다. 스키마를 정해 놓지 않고 데이터를 삽입할 수 있기 때문에 확장성이 뛰어납니다. Document를 생성할 때마다 고유한 ObjectID가 생성됩니다. Redis는 인메모리 DB이자 key-value 데이터 모델 기반의 DB입니다. 문자열, set, sorted set, hash, list 데이터를 지원하고, 높은 성능을 제공하며 데이터의 영속성을 옵션으로 지원합니다.

Redis을 적용하면 적합한 경우에 대해 설명해 주세요.

일반적인 DB가 하드 디스크나 SSD에 저장하는 것과는 달리 Redis는 RAM에 데이터를 저장합니다. 이는 디스크 스캐닝이 필요없어 매우 빠르다는 장점을 가집니다.

데이터 구조가 간단하고 key-value 저장이 적합한 경우 Redis를 적용하기에 적합하다고 볼 수 있습니다. 복잡한 쿼리나 RDB의 JOIN이 필요 없는 간단한 구조에서 효과적으로 사용됩니다.

이전에 검색하거나 계산한 것을 재사용하는 캐싱에 적용하면 빠르게 액세스할 수 있습니다. 이를 통해 반복적인 요청에 대한 응답 시간을 크게 단축할 수 있습니다.

실시간 데이터 처리가 필요한 경우에도 적합합니다. 온라인 광고 노출, 게임 순위표와 같은 상황에서 Redis는 매우 빠른 응답 시간을 제공하여 실시간으로 데이터를 업데이트하고 조회하는 데에 적합합니다.

참고: 인 메모리 데이터베이스란 무엇인가요? - AWS

RDB와 NoSQL을 비교해서 설명해 주세요.

RDB와 NoSQL은 데이터베이스의 다른 형태로 특징과 용도에 따라 선택됩니다.

RDB는 명확하게 정의된 스키마가 존재하고, 데이터 무결성을 보장할 수 있다는 장점이 있습니다. 이러한 특징때문에 덜 유연한 편이고, 관계를 맺고 있어서 조건에 따라 JOIN이 많은 복잡한 쿼리가 만들어질 수 있습니다.

NoSQL은 스키마가 없어서 유연하여, 저장된 데이터를 쉽게 조정하고 새로운 필드를 추가하는 데 용이하다는 장점을 가집니다. 그러나 유연하다는 특징때문에 데이터 수정 시 모든 컬렉션에서 수행해야 하고, 데이터 중복을 계속 업데이트해야한다는 단점을 가지고 있습니다.

따라서 관계를 맺고 있는 데이터가 자주 변경되거나, 데이터의 스키마가 변경될 여지가 적은 경우 RDB를 선택하는 것이 적합합니다. 반대로 데이터 구조가 변경될 가능성이 크고 데이터 변경에 비해 읽기, 삽입이 많은 경우 NoSQL을 선택하는 것이 적합합니다.

느낀 점

이번 스터디를 하면서 솔직하게 말하자면, 프론트엔드 개발자가 이렇게 깊게 운영 체제/데이터베이스를 알아야 하는가에 대한 의문이 계속 생겨났었다.
그런데 공부를 하면 할수록, 프론트엔드 개발자인 것은 둘째치고, 비전공자가 전공자와의 차이를 메꾸려면, 즉 스스로 전공자만큼의 실력을 갖추었다고 증명하고 싶다면 이 정도는 기본적으로 알고 있어야겠다는 깨달음을 얻었다. 다른 스터디원 분들의 질문 수준 및 키워드를 보면서 가장 크게 느꼈다.

여담으로 지난 3월 1일, 정보처리기사 2024년 1회차 필기를 봤었다. 원래 계획으로는 3회독에다가 기출을 돌리고 시험장에 입장할 계획이었지만, 1회독을 못 했었다. 4과목까지는 1회독을 했는데, 마지막 5과목을 못했었다.(그런데 5과목이 90점으로 점수가 가장 높았다) 총 순 공부 시간이 궁금해서 데스크탑 트래킹앱을 확인했는데, 10시간 정도 공부를 했다. 1회독을 할 때, 이번에 기술 면접 스터디를 하면서 준비했던 것들이 정말 많이 도움됐다. 그래서 겸사겸사 기술 면접 준비를 하면서 정보처리기사도 준비한 게 된 것이다.

혹여나 기술 면접 준비를 하면서 공부하는 것에 대한 회의를 느끼고 있다면, 정보처리기사를 준비하는 것도 좋은 선택지가 될 수 있음을 전하고 싶다.

profile
Chaejung
프론트엔드 기술 학습 및 공유를 활발하게 하기 위해 노력합니다.
이전 포스트

[면접을 위한 CS 전공 지식 노트] 01-2 프로그래밍 패러다임

0개의 댓글