코딩테스트/알고리즘 (6) 썸네일형 리스트형 app에서의 정렬과 db에서의 정렬 좋습니다!“애플리케이션에서 sort를 사용할 때 vs DB에서 ORDER BY를 사용할 때**퀵 정렬 / 병합 정렬 / 힙 정렬이 각각 어떤 역할과 특성을 갖는지”**를한눈에 볼 수 있도록 표로 깔끔하게 정리해드릴게요.✅ 애플리케이션 vs DB 정렬 알고리즘 비교표구분Quick SortMerge SortHeap Sort공통 시간복잡도 (평균)O(n log n)O(n log n)O(n log n)공간복잡도O(log n) (재귀 스택)❌ O(n) (보조 배열)✅ O(1)정렬 안정성❌ 불안정✅ 안정 정렬❌ 불안정캐시 효율성 (메모리)✅ 좋음 (인플레이스, 근접 접근)❌ 보조 배열 교차 접근❌ 불연속적 힙 접근디스크 효율성 (DB)❌ 랜덤 접근 → 디스크 비효율✅ 순차 접근 → 디스크 친화❌ 랜덤 접근으로 부적.. 힙정렬 vs 퀵정렬 vs 병합정렬 캐시 효율성 관련 정리 좋은 질문이야. 이건 실제로 정렬 알고리즘을 선택할 때 성능 최적화와 밀접하게 관련된 부분이야.결론부터 말하면:✅ 퀵 정렬이 실제 환경에서 가장 많이 사용됨,이유는 단순히 공간복잡도가 아니라 캐시 효율성과 평균 속도에서 우수하기 때문이야.🔸 힙 정렬 vs 퀵 정렬 vs 병합 정렬 – 왜 퀵 정렬이 많이 쓰일까?정렬 알고리즘 비교힙 정렬퀵 정렬병합 정렬평균 시간복잡도O(n log n)O(n log n)O(n log n)공간복잡도✅ O(1) (최소)O(log n) (재귀 스택)❌ O(n) (보조 배열)캐시 효율성❌ 낮음 (불연속적 접근)✅ 높음 (인접 메모리 접근)❌ 낮음 (배열 분산 접근)정렬 안정성❌ 불안정❌ 불안정✅ 안정 정렬실제 성능느림빠름 (실제로 가장 빠름)중간사용 예특수 상황, 우선순위 큐 내.. BFS vs DFS vs 다익스트라 알고리즘 비교 훌륭한 질문이야! 면접에서 정말 많이 나오는 포인트고, 신입 개발자들이 자주 혼동하는 부분이기도 해.결론부터 말하면:✅ BFS는 간선 가중치가 모두 동일할 때 최단 거리를 찾는 데 사용✅ 다익스트라는 가중치가 있는 그래프에서 최단 거리를 찾을 수 있음🔍 핵심 차이 요약항목 BFS DFS 다익스트라탐색 방식너비 우선깊이 우선최단 거리 우선사용 조건간선 가중치가 모두 1경로 탐색/백트래킹간선 가중치가 0 이상자료구조큐스택/재귀우선순위 큐 (Heap)최단 거리 보장✅ (가중치 1일 때)❌✅ (모든 가중치)주 용도미로 탈출, 레벨 탐색조합, 경로의 존재 여부지도 앱, 네트워크 비용 계산 등📘 예시로 설명해줄게🎯 BFS 예시: 미로 탈출한 칸 이동할 때마다 비용이 모두 1이라면,BFS는 가장 먼저 도달한 경.. 대표적 알고리즘 정리 🔎 개발자가 꼭 알아야 할 핵심 알고리즘/자료구조 정리📌 1. 정렬 알고리즘알고리즘 개념 요약 평균 시간복잡도 특이점선택 정렬가장 작은 값을 찾아 맨 앞으로 보냄O(n²)단순하지만 느림삽입 정렬앞에서부터 하나씩 정렬된 곳에 삽입O(n²)거의 정렬된 경우 빠름버블 정렬옆에 있는 값과 비교해 큰 걸 뒤로 보냄O(n²)교육용으로 주로 사용병합 정렬반으로 나눠 정렬 후 병합O(n log n)안정 정렬, 메모리 사용 ↑퀵 정렬피벗을 기준으로 분할O(n log n) (최악: O(n²))평균적으로 가장 빠름힙 정렬힙 자료구조 이용O(n log n)추가 공간 사용 적음📌 2. 탐색 알고리즘알고리즘 개념 요약 시간복잡도 특이점선형 탐색순차적으로 하나씩 비교O(n)정렬 필요 없음이진 탐색정렬된 배열에서 절반씩 탐색O.. 백트래킹 백트래킹(Backtracking)은 문제를 해결하는 과정에서 가능한 모든 경우를 시도하는 방법입니다. 쉽게 말해, 여러 선택지를 하나씩 시도해보면서 조건을 만족하는 해를 찾는 과정입니다. 만약 어떤 선택이 조건을 어긴다면, 그 선택을 취소하고 다른 선택을 시도하는 방식으로 진행됩니다.백트래킹의 기본 개념상태(State): 현재 선택한 값이나 설정.목표(Goal): 문제의 해결책.유효성 검사: 현재 상태가 목표를 만족하는지 확인.재귀 호출: 다음 상태로 넘어가는 과정.되돌아가기(Backtrack): 더 이상 진행할 수 없는 경우 이전 상태로 돌아가는 과정.예시: 부분집합 구하기부분집합 문제는 주어진 집합의 모든 부분집합을 구하는 문제입니다. 예를 들어, 집합 {1, 2, 3}의 모든 부분집합을 찾아보겠습니.. 코딩테스트 알고리즘 - BFS, DFS 그래프 탐색어떤 것들이 연속해서 이어질 때 모두 확인하는 방법Graph : Vertex(어떤것. 노드) + Edge(이어지는 것. 연결선)BFS너비 우선 탐색 : 자기 자식 우선 탐색시작점에 연결된 vertex찾기 -> 찾은 vertex를 queue에 저장DFS깊이 우선 탐색 : 자식의 자식을 우선 탐색 깊이 우선 탐색 : 자식의 자식을 우선 탐색연결된 vertex 찾기 -> 찾은 vertex를 stack에 저장시간복잡도알고리즘이 얼마나 오래 걸리는지Big-OBFS : O(V+E)사용 자료구조BFS검색할 그래프방문 여부 확인(재방문 금지 목적)Queue : BFS 실행 이전 1 다음
