알고리즘 관련 면접 질문 정리 ①

Q1.  Dynamic Programming이란? 장점은?

 

A1. 이전의 결과값들을 저장해서 처리 속도를 향상시키는 프로그래밍 기법 ex) 피보나치

---

 

Q2. map, hashmap, set에 대해서 설명하세요

 

A2.

Hash의 정의 : 특정 input값을 주어지면 항상 동일값을 보장해주는 것

 

Map의 정의 : 기본적으로, put과 get을 가지고 있는 인터페이스로, 추가하고, 값을 가져 올 수 있는 인터페이스

종류로는 HashMap, TreeMap, LinkedHashMap이 있다.

 

HashMap의 정의 : Hash 형식을 가지고 있는 key-value의 Map

 

Set의 정의 : array나 list처럼 순열 자료구조. but 순서라는 개념이 존재하지 않음. 보통 해쉬값 기반으로 저장함

 

**HashTable은 HashMap과 비슷한 Collection이지만, Thread-safe한 특징이 있다.

https://gompangs.tistory.com/entry/Hashtable%EC%97%90-%EA%B4%80%ED%95%B4%EC%84%9C?category=537219 

Hashtable에 관해서

---

 

Q3. 배열의 최대값 / 최솟값 을 구하세요

 

A3. 코드상으로, max와 min을 저장해두고 한개씩 값을 비교해보면서 저장 -> 시간복잡도 O(n), 공간복잡도 O(1)

 

더 빠른 방법 - 2개씩 보기

def optimization_find_small_and_largest_number_in_array(A):
    _max = _min= A[0]

    for idx in range(0, len(A), 2):
        first = A[idx]
        second = A[idx + 1]
        if first < second:
            if first < _min: _min = first
            if second > _max: _max = second
        else:
            if second < _min: _min = second
            if first > _max: _max = first
    return _max, _min

 

---

참조 : https://github.com/brave-people/brave-tech-interview/blob/main/contents/algorithm.md

GitHub - brave-people/brave-tech-interview: 🙋 핵심을 질문하다. 그리고 용감하게 대답하다. 국내 IT기업부