[ TIL - CS ] 면접을 위한 CS 공부 3편 - 자료구조와 알고리즘 -

🚌 2024년 11월 4일~ 2024년 11월 11일까지의 주제는 자료구조와 알고리즘이다.

 

💡 공통으로 준비한 질문

1️⃣ 첫번째 접은 글은 내 말로 풀어쓴 정답
2️⃣ 두번째 접은 글은 해석 또는 공부한 내용 또는 추가적으로 궁금한 내용

 

 

- 📗 자료 구조 편 -

 

1. Array와 LinkedList의 차이점에 대해 설명해 주세요.

• Array는 인덱스로 값을 찾는데 빠르지만, LinkedList는 값의 삽입과 삭제가 빠릅니다.
  또한, Array는 배열을 선언할 때 크기와 데이터 타입을 지정해야 하며, 중간에 데이터를 삽입하거나 삭제할 시 매우 비효율적입니다. LinkedList는 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어 있어 삽입과 삭제 시 주소값만 바꾸어 연결해주기 때문에 빠르게 진행이 가능합니다.

1. 전체 내용 참고 

Array vs ArrayList vs LinkedList | 👨🏻‍💻 Tech Interview

 

2. Array와 LinkedList 그림으로 보는 차이

[CS/자료구조] Array와 LinkedList 정의, 차이점

 

 

2. Stack과 Queue의 개념 및 사용 사례를 설명해 주세요.

• 스택이란?
  • LIFO 형식을 사용합니다.
  • 사용 사례로는 함수의 콜스택, 문자열 역순 출력, 연산자 후위 표기법 때 많이 사용합니다.

  • 

    나중에 들어온 게 먼저 나가는 방식

• 큐란?
  • FIFO 형식을 사용합니다.
  • 사용 사례로는 버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, BFS 입니다.
  •  

먼저 들어온 것이 먼저 나가는 방식

 

1. stack과 queue 자세한 코드

스택 & 큐 | 👨🏻‍💻 Tech Interview

 

2. 면접할 때 간단하게 알면 좋을내용

tech-interview/contents/datastructure.md at master · WeareSoft/tech-interview

 

3. 그림 참고

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

 

 

3. Priority Queue 및 Heap에 대해 설명해 주세요.

• 우선순위 큐란?
  • 데이터들이 우선 순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나갑니다.
  • 배열, 연결리스트, 힙으로 구현하며 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산에 사용됩니다.
• 힙이란?
  • 완전 이진 트리의 일종으로, 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조입니다.
  • 힙의 종류로는 최대힙과 최소 힙이 있습니다.

1. 힙이란?

힙(Heap) | 👨🏻‍💻 Tech Interview

 

2. 코드로 보는 차이

우선순위 큐와 힙의 차이

 

3. 활용

우선순위 큐와 힙 자료 구조의 이해

 

 

4. Hash Table과 Hash Collision 해결 방법에 대해 설명해 주세요.

• 해시 테이블이란?
  • Key-Value 쌍으로 값을 저장하는 자료구조입니다.
  • 해시 테이블에 key로 접근했을 때 hash function에서 나온 hash 값을 저장소의 인덱스로 활용합니다. 그렇기에 시간 복잡도 O(1)을 보장합니다.
• Hash Collision이란?
  • 다른 데이터가 같은 해시 값으로 충돌나는 현상을 말합니다.
  • 해결 방법은 
    • 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식
    • Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용
    • 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
    • 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
  • 가 있습니다.

1. 해시 테이블이란?

해시(Hash) | 👨🏻‍💻 Tech Interview

 

2. 해시 테이블 충돌 해결 방법

tech-interview/contents/datastructure.md at master · WeareSoft/tech-interview

 

3. 비둘기집 예시

[면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ① 자료구조

 

 

- 📘 알고리즘 편 -

 

1. 동적 계획법(DP, Dynamic Programming)에 대해 설명해주세요.

• DP란? 
  • 한 가지 문제에 대해서, 단 한번만 풀도록 만들어주는 알고리즘입니다.
  • 똑같은 연산을 반복하지 않도록 만들어주고, 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘입니다.

1. DP란?

동적 계획법(Dynamic Programming) | 👨🏻‍💻 Tech Interview

 

 

2. 퀵 정렬(Quick Sort)에 대해 설명해주세요.

• 퀵 정렬이란?
  
  • 분할 정복 방법을 통해 주어진 배열을 정렬합니다.
    • 분할정복이란? 문제를 작은 2개의 문제로 분리하고 각각 결한 다음, 결과를 모아서 원래의 문제를 해결하는 방법
  • 정렬 과정은 피벗을 기준으로 왼쪽에는 피벗보다 작은 수를, 오른쪽에는 피벗보다 큰 수를 놓습니다. 피벗을 기준으로 나뉜 두 배열에서 각각 피벗을 정리해서 앞과정과 같이 정리합니다. 더 이상 나눌 수 없을 때까지 반복하여 정렬합니다.
  • 장점으로는 속도가 빠르며, 추가 메모리 공간을 필요로 하지 않습니다. 단점은 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸립니다.

1. 그림으로 보는 자료

퀵 정렬(Quick Sort) | 👨🏻‍💻 Tech Interview

 

2. 장단점

tech-interview-study/contents/algorithm.md at master · devham76/tech-interview-study

 

 

3. Big-O 표기법의 시간 복잡도 크기 순서를 말해주세요.

• O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ⁿ) < O(N!)

1. 정답

신입 개발자 기술면접 질문 정리 - 알고리즘

 

 

4. 재귀 알고리즘에 대해 설명해주세요.

• 재귀 알고리즘이란 함수 내부에서 함수가 자기 자신을 또 다시 호출하여 해결하는 알고리즘입니다. 자기자신을 계속해서 호출하여 끝없이 반복되게 하므로 반복을 중단할 조건이 필요합니다.

1. 반복문과 재귀의 차이

[알고리즘] 재귀 함수 (Recursion)

 

2. 재귀 실제 코드

알고리즘 정리4 : 재귀