반응형
기술 면접 치트 시트 (Tech Interview Cheat Sheet)
이 문서는 기술 면접과 관련된 주제에 대한 빠른 안내서 및 참고 자료입니다. 놓쳤거나 잊어버렸을 수 있는 컴퓨터 과학 개념을 요약한 것입니다.
점근적 표기법 (Asymptotic Notation)
정의
점근적 표기법은 알고리즘의 시간 및 공간 복잡도를 표현하는 하드웨어 독립적인 방법으로, 본질적으로 주어진 입력에 대한 메모리 사용량과 실행 시간을 측정합니다.
복잡도 (Complexities)
다음은 최선에서 최악 순으로 다양한 점근적 성장률 목록입니다.
O(1)- 상수 성장 (실행 시간이 n에 따라 증가하지 않음)O(log n)- 로그 성장 (실행 시간이 n에 대해 로그적으로 증가)O(n)- 선형 성장 (실행 시간이 n에 정비례하여 증가)O(n log n)- 선형로그 성장 (실행 시간이 n에 비례하고 로그적으로 증가)O(n^c)- 다항 성장 (n을 기반으로 이전보다 빠르게 실행 시간이 증가)O(c^n)- 지수 성장 (n을 기반으로 다항보다 훨씬 빠르게 실행 시간이 증가)O(n!)- 팩토리얼 성장 (실행 시간이 가장 빠르게 증가하며 작은 n에 대해서도 금방 사용 불가능해짐)
Big-O 표기법
시간 또는 공간 복잡도의 상한을 나타내며, 최악의 실행 시간 시나리오를 의미합니다.
Big-Ω (Big-Omega) 표기법
시간 또는 공간 복잡도의 하한을 나타내며, 최선의 실행 시간 시나리오를 의미합니다.
Big-θ (Big-Theta) 표기법
시간 또는 공간 복잡도의 엄밀한 경계(tight bound)를 나타내며, 보장된 실행 시간 복잡도를 의미합니다.
알아야 할 것
Big-O와 Big-Theta가 일반적으로 사용됩니다. 이 표기법들은 본질적으로 최악, 평균 또는 최선의 경우 시나리오를 의미하는 것이 아니라 특정 시나리오에 대한 성능을 나타냅니다. Big-O가 전부는 아니며 실제 성능은 이론과 다를 수 있다는 점에 유의해야 합니다.
자료 구조 (Data Structures)
배열 (Array)
정의
순차적인, 보통 0부터 시작하는 인덱스를 기반으로 데이터 요소를 저장하며, 가장 오래되고 가장 일반적인 데이터 구조 중 하나입니다.
알아야 할 것
인덱싱에는 최적이지만, 검색, 삽입, 삭제(맨 끝 제외)에는 비효율적입니다. 선형(정적 크기), 동적(크기 조절 가능), 다차원 배열로 구분됩니다.
시간 복잡도
| 연산 | 선형/동적 배열 |
|---|---|
| 인덱싱 | O(1) |
| 검색 | O(n) |
| 최적화된 검색 | O(log n) |
| 삽입/삭제 | O(n) |
연결 리스트 (Linked List)
정의
다른 노드를 가리키는 노드를 사용하여 데이터를 저장하며, 사슬을 형성합니다.
알아야 할 것
삽입 및 삭제에 최적화되어 있지만, 인덱싱 및 검색에는 느립니다. 이중 연결 리스트, 원형 연결 리스트, 스택(LIFO), 큐(FIFO)를 다룹니다.
시간 복잡도
| 연산 | 시간 복잡도 |
|---|---|
| 인덱싱 | O(n) |
| 검색 | O(n) |
| 추가 (Append/Prepend) | O(1) |
| 삽입/삭제 | O(1) (위치를 알 경우) |
해시 테이블 또는 해시 맵 (Hash Table or Hash Map)
정의
키-값 쌍으로 데이터를 저장하며, 해시 함수를 사용하여 각 키에 대한 고유한 메모리 주소를 반환합니다.
알아야 할 것
검색, 삽입, 삭제에 최적화되어 있습니다. 해시 충돌과 그 해결 방법을 논의하며, 연관 배열 및 데이터베이스 인덱싱에 해시의 중요성을 강조합니다.
시간 복잡도
| 연산 | 시간 복잡도 (평균) |
|---|---|
| 검색 | O(1) |
| 삽입 | O(1) |
| 삭제 | O(1) |
이진 트리 (Binary Tree)
정의
각 노드가 최대 두 개의 자식(왼쪽 및 오른쪽)을 갖는 트리와 같은 데이터 구조입니다.
알아야 할 것
검색 및 정렬에 최적화되어 있습니다. 편향 트리(degenerate tree)와 이를 사용하여 이진 탐색 트리를 만드는 방법을 언급합니다. 이진 탐색 트리는 비교 가능한 키를 사용하여 자식을 구성합니다(왼쪽 자식은 더 작고, 오른쪽 자식은 더 큼).
시간 복잡도 (이진 탐색 트리)
| 연산 | 시간 복잡도 (평균) | 시간 복잡도 (최악) |
|---|---|---|
| 검색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
알고리즘 (Algorithms)
알고리즘 기초 (Algorithm Basics)
재귀 알고리즘 (Recursive Algorithms)
정의: 자기 자신을 다시 호출하는 알고리즘으로, 재귀를 유발하는 재귀 케이스(recursive case)와 재귀를 멈추는 기본 케이스(base case)가 특징입니다.
알아야 할 것: "stack level too deep" 또는 "stack overflow" 오류에 주의해야 하며, 이는 잘못된 기본 케이스나 과도한 메모리 사용을 나타냅니다. 깊이 우선 탐색(DFS)에서 자주 사용됩니다.
반복 알고리즘 (Iterative Algorithms)
정의: 유한한 횟수만큼 반복적으로 호출되는 알고리즘으로, 종종 데이터를 점진적으로 이동하는 데 사용됩니다.
알아야 할 것: 일반적으로 루프(for, while, until 문)로 나타납니다. 배열을 순회하는 데 자주 사용됩니다.
재귀 vs. 반복 (Recursion Vs. Iteration)
재귀는 보통 더 표현력이 풍부하고 구현하기 쉽지만, 반복은 메모리를 덜 사용합니다. 함수형 언어는 재귀를, 명령형 언어는 반복을 사용하는 경향이 있습니다.
탐욕 알고리즘 (Greedy Algorithms)
정의: 실행 중에 특정 기준을 충족하는 정보를 선택하는 알고리즘으로, 후보 집합, 선택 함수, 실행 가능성 함수, 목표 함수, 해결책 함수의 다섯 가지 일반적인 구성 요소를 가집니다.
알아야 할 것: 신속하지만 최적이 아닌 해결책을 찾는 데 사용되며, 원하는 결과를 충족하는 비율이 작은 데이터 집합에서 자주 사용됩니다. 알고리즘의 Big O를 줄이는 데 도움이 될 수 있습니다.
탐색 알고리즘 (Search Algorithms)
너비 우선 탐색 (Breadth First Search - BFS)
정의: 루트에서 시작하여 레벨별로 트리(또는 그래프)를 검색하며, 자식 노드를 추적합니다.
알아야 할 것: 넓고 얕은 트리에 최적입니다. 큐(Queue)를 사용하므로 깊이 우선 탐색(DFS)보다 메모리를 많이 사용합니다.
시간 복잡도: O(V + E) (V는 정점, E는 간선)
깊이 우선 탐색 (Depth First Search - DFS)
정의: 각 브랜치를 따라 가능한 한 깊이 탐색한 후 백트래킹하여 트리(또는 그래프)를 검색합니다.
알아야 할 것: 깊고 좁은 트리에 최적입니다. 스택(Stack)을 사용하므로 너비 우선 탐색(BFS)보다 메모리를 적게 사용합니다.
시간 복잡도: O(V + E) (V는 정점, E는 간선)
정렬 알고리즘 (Sorting Algorithms)
| 알고리즘 | 시간 복잡도 (최선/평균/최악) | 공간 복잡도 (최악) | 설명 |
|---|---|---|---|
| 선택 정렬 (Selection Sort) | O(n²)/O(n²)/O(n²) | O(1) | 가장 작은 요소를 반복적으로 찾아 정렬된 부분의 왼쪽에 배치하는 비교 기반 알고리즘. 제자리 정렬. |
| 삽입 정렬 (Insertion Sort) | O(n)/O(n²)/O(n²) | O(1) | 왼쪽에서 오른쪽으로 반복하며 현재 요소를 왼쪽의 정렬된 위치에 삽입하는 비교 기반 알고리즘. 제자리 정렬. |
| 병합 정렬 (Merge Sort) | O(n log n)/O(n log n)/O(n log n) | O(n) | 배열을 단일 요소 하위 집합으로 재귀적으로 나눈 다음 병합하고 정렬하는 분할 정복 알고리즘. |
| 퀵 정렬 (Quicksort) | O(n log n)/O(n log n)/O(n²) | O(log n) | 피벗을 기준으로 데이터셋을 분할하여 작은 요소를 왼쪽, 큰 요소를 오른쪽으로 배치한 후 재귀적으로 정렬하는 분할 정복 알고리즘. 제자리 정렬. |
참고 사이트 (Reference Sites)
- https://www.f5.com/ko_kr/glossary/load-balancer
- https://velog.io/@vino661/Database-Cache-%ED%99%9C%EC%9A%A9-%EC%A0%84%EB%9E%B5
- https://velog.io/@courage331/%EC%BA%90%EC%8B%B1-%EC%A0%84%EB%9E%B5
- https://velog.io/@hann1233/%EC%BA%90%EC%8B%B1%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%84%B1%EB%8A%A5-%EC%B5%9C%EC%A0%81%ED%99%941-%EC%BA%90%EC%8B%B1%EA%B3%BC-%EC%A0%84%EB%9E%B5
- https://velog.io/@xogml951/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC
- https://velog.io/@tngus0325/%EC%9B%B9%EC%82%AC%EC%9D%B4%ED%8A%B8-%EC%BA%90%EC%8B%B1-%EC%86%8D%EB%8F%84%EC%99%80-%ED%9A%A8%EC%9C%A8%EC%84%B1-%ED%96%A5%EC%83%81
- https://velog.io/@newdana01/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BFS-DFS
- https.tistory.com/192
- https://velog.io/@maxkmh/%EC%BA%90%EC%8B%9C-%EC%BA%90%EC%8B%B1
- https://velog.io/@frombozztoang/Java-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity-Big-O#:~:text=%F0%9F%99%84%20%EC%B5%9C%EC%95%85%EC%9D%98%20%EA%B2%BD%EC%9A%B0%20%3A%20Big,O%20Notation%20(%EB%B9%85%2D%EC%98%A4)&text=(%EC%83%81%EC%88%98%20%EB%B9%84%EC%9C%A8%EC%9D%98%20%EC%B0%A8%EC%9D%B4%EB%8A%94,%ED%95%A8%EC%88%98%EC%99%80%20%EA%B0%99%EA%B1%B0%EB%82%98%20%EC%A2%8B%EB%8B%A4.&text=%EB%B9%85%EC%98%A4%20%ED%91%9C%EA%B8%B0%EB%B2%95%EC%9D%80%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8%20%EC%8B%A4%ED%96%89,%EC%9E%90%EC%A3%BC%20%EC%82%AC%EC%9A%A9%EB%90%98%EB%8A%94%20%ED%91%9C%EA%B8%B0%EB%B2%95%EC%9D%B4%EB%8B%A4.
- https://velog.io/@airoca/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94-Hash-Table-Chaining-Open-Addressing
- https.tistory.com/57
- https://velog.io/@gillog/Algorithm-%EC%9E%AC%EA%B7%80%EC%99%80-%EB%B0%98%EB%B3%B5%EB%AC%B8
- https.tistory.com/32
- https://velog.io/@gyuzic/Hashing-Chaning
- https://velog.io/@widrns15/Unit1-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88
- https://velog.io/@suu07/%EC%BA%90%EC%8B%B1-%EC%BA%90%EC%8B%B1-%EC%A0%84%EB%9E%B5
- https://velog.io/@dlskawns/CS-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC-%EB%B2%84%EB%B8%94-%EC%84%A0%ED%83%9D-%EC%82%BD%EC%9E%85-%ED%80%B5-%EB%B3%91%ED%95%A9
- https://velog.io/@bluejoyq/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%80%B5-%EC%A0%95%EB%A0%ACquick-sort-vs-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%ACmerge-sort
- https://velog.io/@miretta96/Array-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90
- https://velog.io/@mxnzx/system-design-interview1-ch3
- https://velog.io/@ez0ez0/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B8%B0%EC%B4%88
- https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94-Hash-Table-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC-wb6g3iw0
- https://velog.io/@coin46/Big-O-Notation
- https://velog.io/@cksgml1914/%EB%B9%85-%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95-Big-O-notation
- https://velog.io/@haero_kim/%EC%95%88%EC%A0%95%EC%A0%81-%EA%B7%B8-%EC%9E%90%EC%B2%B4-Merge-Sort
- https.tistory.com/102
- https://github.com/TSiege/Tech-Interview-Cheat-Sheet
- https://github.com/kangbada0728/study-system-design-interview
- https://www.youtube.com/watch?v=5Ky59iblLBI&pp=0gcJCdgAo7VqN5tD
- https://www.reddit.com/r/sysadmin/comments/1dw4rar/write_back_vs_write_through_ssd_raid/
- https://www.reddit.com/r/leetcode/comments/1el083l/the_best_way_to_prepare_for_system_design/?tl=ko
- https://www.reddit.com/r/ExperiencedDevs/comments/163q1n1/how_do_you_approach_sys_design_interviews_as_the/?tl=ko
- https://www.ibm.com/kr-ko/topics/load-balancing
- https://www.geeksforgeeks.org/write-through-and-write-back-in-cache/
- https://www.dell.com/community/en/conversations/poweredge-hddscsiraid/difference-between-write-back-and-write-thru/647e3277f4ccf8a8de7266e0
- https://www.cwn.kr/news/articleView.html?idxno=3896
- https://www.aitimes.com/news/articleView.html?idxno=129809
- https://www.smileshark.kr/post/what-is-a-load-balancer-a-comprehensive-guide-to-aws-load-balancer
- https://www.nossi.dev/436b3b11-fa77-4dcc-9d24-f6b034d6770e
- https://stackoverflow.com/questions/27087912/write-back-vs-write-through-caching
- https://docs.johnsoncontrols.com/americandynamics/r/American-Dynamics/en-US/VideoEdge-External-Storage-System-Administration-Guide/B/System-concepts/Volume-cache-options/Using-write-back-or-write-through-caching
- https://docs.aws.amazon.com/whitepapers/latest/database-caching-strategies-using-redis/welcome.html
- https://docs.aws.amazon.com/whitepapers/latest/database-caching-strategies-using-redis/caching-patterns.html
- https://d1.awsstatic.com/whitepapers/Database/database-caching-strategies-using-redis.pdf
- https://aws.amazon.com/ko/what-is/load-balancing/
- https://aws.amazon.com/ko/caching/
- https://aws.amazon.com/caching/best-practices/
- http://www.aistudy.com/biology/genetic/application_moon.htm
- https://gfxcourses.stanford.edu/cs149/fall20/lecture/cachecoherence/slide_6
- https://medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80-%EB%AF%B8%EC%B9%9C%EC%A7%93%EC%9D%B4%EB%8B%A4/5-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4-%EB%8F%99%EC%A0%81-%EB%B0%B0%EC%97%B4-7b2b3eb939a2
- https://medium.com/@rajapurohit_c/caching-strategies-in-aws-elasticache-using-redis-78d52a5eb1a8
- https://anand-guptaa.medium.com/exploring-caching-strategies-and-patterns-with-aws-elasticache-serverless-a3bc0467ba5b
- https://brunch.co.kr/@toughrogrammer/12
- https://yozm.wishket.com/magazine/questions/share/IMbhOxsBH6BpLGUi/
- https://yozm.wishket.com/magazine/questions/share/CyhD953m9Zyzddqe/
- https://jonghoonpark.com/2023/05/10/%EC%8B%9C%EC%8A%A4%ED%85%9C-%EC%84%A4%EA%B3%84-%EB%A9%B4%EC%A0%91-%ED%8C%81
- https://rosweet-ai.tistory.com/54
- https://limecoding.tistory.com/76#:~:text=%EC%9E%AC%EA%B7%80%20%ED%95%A8%EC%88%98%EC%99%80%20%EB%B0%98%EB%B3%B5%EB%AC%B8%EC%9D%98%20%EC%B0%A8%EC%9D%B4&text=%EB%B0%98%EB%B3%B5%EB%AC%B8%EC%9D%80%20%EB%B0%98%EB%B3%B5%20%ED%9A%9F%EC%88%98%EB%A5%BC,%EB%8B%A8%EC%A0%90%EC%9D%84%20%EA%B0%96%EC%A7%80%EA%B3%A0%20%EC%9E%88%EB%8B%A4.
- https://limecoding.tistory.com/76
- https://thesauro.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B3%B5%EB%B6%80-1-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
- https://luna-archive.tistory.com/47
- https://loosie.tistory.com/800
- https://kghworks.tistory.com/181
- https://kjw1313.tistory.com/78
- https://junuuu.tistory.com/767
- https://junvelee.tistory.com/153#:~:text=%ED%95%B4%EC%8B%9C%20%ED%85%8C%EC%9D%B4%EB%B8%94%EC%9D%80%20%ED%82%A4(key,%ED%95%98%EA%B3%A0%20%EA%B2%80%EC%83%89%ED%95%98%EB%8A%94%20%EB%B0%A9%EC%8B%9D%EC%9D%B4%EB%8B%A4.
- https://jino-dev-diary.tistory.com/36
- https://hongjw1938.tistory.com/192
- https://hazel-developer.tistory.com/173
- https://greyfolk.tistory.com/17
- https://gbdai.tistory.com/16
- https://eunajung01.tistory.com/37
- https://eckrin.tistory.com/59
- https://easy-code-yo.tistory.com/13
- https://econo-my.tistory.com/42
- https://elisha0103.tistory.com/24
- https://dream-and-develop.tistory.com/52
- https://devuna.tistory.com/32
- https://devjourney7.tistory.com/121
- https://comlini8-8.tistory.com/100
- https://codingslime.tistory.com/8
- https://chanos.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%88%9C%EC%B0%A8%EC%A0%81-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4%EA%B3%BC-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EC%9D%B4%ED%95%B4
- https://butter-shower.tistory.com/64
- https://boogalle91-cs.tistory.com/46
- https://brightstarit.tistory.com/57
- https://ardentdays.tistory.com/11
- https://ssdragon.tistory.com/100
- https://soobing.github.io/cs/6-caching-strategies/
- https://sunho-doing.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS
- https://shbae.tistory.com/42
- https://seongonion.tistory.com/28
- https://sdcodebase.tistory.com/34
- https://prodo-developer.tistory.com/111
- https://pro-jm.tistory.com/63
- https://plas.tistory.com/150
- https://paparoni-story.tistory.com/26
- https://nueahx7674.tistory.com/8
- https://noahlogs.tistory.com/27
- https://mindock.github.io/algorithm/stable-unstable-sort/
- https://mikiplace.tistory.com/160
- https://myeongju00.tistory.com/101
- https://mangkyu.tistory.com/102
- https://yoo11052.tistory.com/63
- https://yoongrammer.tistory.com/78
- https://yoongrammer.tistory.com/43
- https://yeonjewon.tistory.com/80
- https://yunyoung1819.tistory.com/86
- https://yabmoons.tistory.com/250
- https://4z7l.github.io/2020/09/02/sort-2.html
- https://cctimes.kr/news/articleView.html?idxno=710194
- https://hoehen-flug.tistory.com/28
반응형
'정보' 카테고리의 다른 글
| 면접을 위한 준비 정리 (4) | 2025.07.13 |
|---|---|
| 면접을 위한 요약 정리 (6) | 2025.07.12 |
| 내 대출한도 계산기 (0) | 2025.07.04 |
| curl 심층 분석 (4) | 2025.07.03 |
| AI 시대의 전략적 리더십 가이드 (1) | 2025.07.01 |