본문 바로가기

분류 전체보기54

DFS(깊이 우선) vs BFS(너비 우선) 탐색 차이 복잡한 미로에 갇혔다고 상상해 봅시다. 출구를 찾기 위해 여러분은 어떤 전략을 사용하시겠습니까? 한쪽 길을 정해서 막다른 벽이 나올 때까지 무조건 직진해 보시겠습니까, 아니면 현재 서 있는 갈림길에서 갈 수 있는 모든 방향을 한 걸음씩 확인하며 신중하게 나아가시겠습니까? 이 두 가지 전략이 바로 그래프 탐색의 양대 산맥인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)입니다. 개발자 면접이나 코딩 테스트에서 이 두 알고리즘의 차이를 묻는다면, 단순히 탐색 순서뿐만 아니라 사용되는 자료구조(스택 vs 큐)와 해결할 수 있는 문제의 종류가 다르다는 점을 명확히 설명해야 합니다.1. DFS (Depth-First Search): 깊이 우선 탐색DFS는 이름 그대로 '깊이(Depth)'를 우선시하는 탐색 방.. 2026. 2. 11.
선형 탐색 vs 이진 탐색 속도 비교 (업다운 게임) 프로그래밍의 본질은 결국 '데이터 저장'과 '데이터 검색'입니다. 그중에서도 검색(Search)은 사용자가 느끼는 서비스 속도에 직결되는 매우 중요한 기능입니다. "데이터를 찾는 게 다 똑같지 않나?"라고 생각할 수 있지만, 어떤 알고리즘을 사용하느냐에 따라 100만 개의 데이터에서 원하는 값을 찾는 데 1시간이 걸릴 수도, 0.001초가 걸릴 수도 있습니다. 오늘은 가장 기본이 되는 두 가지 검색 방법인 선형 탐색(Linear Search)과 이진 탐색(Binary Search)을 비교하고, 왜 개발자들이 '이진 탐색'을 찬양하는지 그 속도의 비밀을 업다운(Up-Down) 게임에 비유해 설명해 드리겠습니다.1. 선형 탐색 (Linear Search): 무식하지만 확실한 방법선형 탐색은 이름 그대로 데이.. 2026. 2. 11.
트리와 그래프의 차이점 3가지 (순환, 방향성) 자료구조를 공부하다 보면 "트리(Tree)도 노드와 간선으로 되어 있고, 그래프(Graph)도 노드와 간선으로 되어 있는데 도대체 둘은 뭐가 다른 거야?"라는 의문이 생깁니다. 결론부터 말씀드리면 "트리는 그래프의 특수한 형태(부분 집합)이다"라고 정의할 수 있습니다. 즉, 모든 트리는 그래프이지만, 모든 그래프가 트리는 아닙니다.하지만 실무나 면접에서는 이 둘을 엄격하게 구분해야 할 때가 많습니다. 데이터 모델링을 할 때 순환 참조를 허용할 것인지, 부모-자식 관계를 강제할 것인지에 따라 선택이 달라지기 때문입니다. 오늘은 트리와 그래프를 구분 짓는 결정적인 차이점 3가지를 명확하게 비교해 드리겠습니다.1. 첫 번째 차이: 순환(Cycle)의 유무트리와 그래프를 가르는 가장 큰 기준은 바로 '돌고 도는.. 2026. 2. 11.
그래프(Graph) 기초 용어 완벽정리 (정점, 간선) 우리가 매일 사용하는 지하철 노선도, 페이스북이나 인스타그램의 친구 관계, 내비게이션의 최단 경로 찾기. 이들의 공통점은 무엇일까요? 바로 점과 선으로 연결된 네트워크 구조를 가지고 있다는 것입니다. 컴퓨터 과학에서는 이러한 연결 망을 수학적으로 모델링하여 그래프(Graph)라고 부릅니다. 그래프는 단순히 그림을 그리는 것이 아니라, 복잡하게 얽힌 데이터 간의 관계를 표현하고 문제를 해결하는 가장 강력한 도구입니다. 오늘은 그래프 이론의 기초가 되는 핵심 용어들과 그 구조적 특징을 완벽하게 정리해 드리겠습니다.1. 그래프(Graph)란 무엇인가?그래프는 사물(Entity)과 그 사물 간의 관계(Relationship)를 표현하는 비선형 자료구조입니다. 수학적으로는 $G = (V, E)$로 표현합니다. 여.. 2026. 2. 10.
우선순위 큐(Priority Queue) 쉬운 설명 (응급실 비유) 자료구조 큐(Queue)를 배울 때 우리는 '선입선출(FIFO)', 즉 "먼저 온 사람이 먼저 나간다"는 공평한 줄 서기 원칙을 배웠습니다. 하지만 현실 세계가 항상 선착순으로만 돌아갈까요? 어떤 상황에서는 늦게 왔더라도 더 급하고 중요한 일이 먼저 처리되어야 할 때가 있습니다. 이때 필요한 자료구조가 바로 우선순위 큐(Priority Queue)입니다. 일반적인 큐의 규칙을 깨고, 오직 '중요도(Priority)'에 따라 처리 순서를 결정하는 이 스마트한 대기열에 대해 알아보겠습니다.1. 우선순위 큐란? (응급실의 법칙)우선순위 큐를 가장 완벽하게 설명하는 예시는 바로 종합병원의 응급실입니다.일반 큐 (은행 창구): 아침 9시에 온 사람이 10시에 온 사람보다 무조건 먼저 업무를 봅니다. (시간 순서).. 2026. 2. 10.
힙(Heap)이 뭔가요? (최댓값, 최솟값 관리) 수많은 데이터 중에서 "가장 큰 값(최댓값)"이나 "가장 작은 값(최솟값)"을 최대한 빨리 찾아내야 한다면 어떤 방법을 쓰시겠습니까? 아마도 데이터를 정렬(Sorting)한 뒤 맨 앞이나 맨 뒤를 가져오는 방법을 떠올릴 것입니다. 하지만 정렬은 꽤 비용이 많이 드는 작업(O(n log n))입니다. 데이터가 수시로 추가되고 삭제되는 상황에서 매번 정렬을 다시 하는 것은 시스템 성능을 갉아먹는 주범이 됩니다.이때 등장하는 구세주가 바로 힙(Heap)입니다. 힙은 "완벽하게 정렬할 필요 없이, 대장(최댓값/최솟값)만 빨리 뽑자!"라는 철학으로 만들어진 자료구조입니다. 우선순위 큐를 구현하는 핵심 엔진이기도 한 힙의 원리를 파헤쳐 봅니다.1. 힙(Heap)이란? (완전 이진 트리 기반)힙은 완전 이진 트리(C.. 2026. 2. 10.

티스토리툴바