너비우선탐색(BFS)이번 포스트에서는 그래프 탐색 알고리즘 중 하나인 너비우선탐색(BFS)에 대해서 알아보겠습니다.너비우선탐색(BFS)이란?시작 정점에서 가까운 정점부터 차례대로 탐색하는 알고리즘즉, 먼저 방문한 정점의 이웃 노드들을 모두 탐색한 뒤 레벨별로 넘어갑니다.주로 같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰입니다.수도 코드(Pseudo Code)u: 탐색 시작 정점visited[]: 각 정점의 방문 여부를 저장하는 배열 (중복 방문 방지)Q: 탐색할 정점을 순서대로 담아두는 큐 (FIFO 구조)v: 현재 큐에서 꺼낸 정점w: 현재 정점 v의 인접 정점들BFS(u): visited[u] ← true // 시작 정점 u 방문 표시 Q ← e..

깊이우선탐색(DFS)이번 포스트에서는 그래프 탐색 알고리즘 중 하나인 깊이우선탐색(DFS)에 대해서 알아보겠습니다.깊이우선탐색(DFS)이란?그래프에서 한 방향으로 가능한 깊이까지 계속 탐색 -> 더 이상 갈 수 없으면 다시 돌아와서 다른 방향을 탐색하는 방식의 그래프 순회 알고리즘입니다.스택(Stack) 자료구조의 동작 원리(LIFO)를 따릅니다. -> 재귀 함수 또는 명시적 스택으로도 구현 가능수도 코드(Pseudo Code)u: 현재 탐색 중인 정점v: u의 인접한 정점adj[u]: 정점 u에 인접한 모든 정점들의 리스트visited: 각 정점의 방문 여부를 기록하는 배열 또는 집합DFS(u): visited[u] ← true // 시작 정점 u 방문 표시 u 처리 ..

그래프 이론 기초이번 포스트에서는 그래프 알고리즘을 배우기 앞서 그래프 이론 기초에 대해서 알아보겠습니다.그래프(Graph)란?정점(Vertex)과 간선(Edge)으로 이루어진 자료구조정점은 데이터를, 간선은 정점 간의 관계를 나타냅니다.예를 들어, 도시 간 도로 연결, 사람 간 관계, 네트워크 구조 등 현실 세계의 많은 구조를 그래프로 모델링할 수 있습니다.그래프의 종류그래프는 다양한 기준에 따라 여러 종류로 나뉩니다.구분종류설명방향성방향 그래프간선에 방향이 있는 그래프 (A → B) 무방향 그래프간선에 방향이 없는 그래프 (A — B)순환성순환 그래프정점에서 출발해 다시 돌아오는 경로가 존재 비순환 그래프(DAG)순환이 없는 방향 그래프가중치가중치 그래프간선에 비용 또는 길이 등의 값이 있는 그래프연..

공간복잡도이번 포스트에서는 알고리즘 성능 분석 방법 중 하나인 공간복잡도에 대해서 알아보겠습니다.공간복잡도란?입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양입력 크기(N)에 따라 알고리즘이 얼마나 많은 메모리를 사용하는지를 수학적으로 표현하는 개념정적변수 선언 이외에도 동적으로 할당된 공간를 포함하여 Array, Map, Set 등 요소들을 담을 공간이면 모두 적용할 수 있습니다.공간복잡도의 필요성공간복잡도를 고려하는 것은 효율적인 알고리즘 설계와 시스템 안정성 확보를 위해 매우 중요합니다.컴퓨터 시스템에는 한정된 메모리 자원이 존재합니다.특히 서버, 임베디드 시스템, 모바일 환경처럼 메모리가 제한된 환경에서는 공간복잡도를 고려하지 않으면 프로그램이 메모리 초과(Memory Limi..

시간복잡도이번 포스트에서는 알고리즘 성능 분석 방법 중 하나인 시간복잡도에 대해서 알아보겠습니다.시간복잡도란?입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간주요로직의 반복횟수를 중점으로 측정됩니다.입력이 커질수록 실행 시간이 어떻게 늘어나는지를 수학적으로 표현하며 주로 O(빅오 표기법)을 사용해서 나타냅니다. 시간복잡도가 존재하는 이유는?효율적인 코드로 개선하는데 쓰이는 척도가 되기 때문입니다. 코딩 테스트나 실제 개발 현장에서는 정답을 빠르고 효율적으로 구하는 것이 더 중요합니다.아무리 문제를 풀어냈다고 해도 입력이 조금만 커지면 시간이 터져버린다거나 서버나 프로그램이 멈추는 상황이 발생하면 그 코드는 실질적으로 사용할 수 없는 코드가 됩니다. ❓ 그렇다면 시간복잡도를 측정하기 위해서 항상 시..

순열과 조합이번 포스트에서는 완전탐색 종류 중 하나인 순열과 조합에 대해서 알아보겠습니다.순열이란?순서를 고려해서 n개 중 r개를 뽑는 경우공식은 다음과 같습니다. $$ nPr = n! / (n-r)! $$예시[A, B, C] 중에서 2개를 뽑아 줄을 세운다면:(A, B), (A, C), (B, A), (B, C), (C, A), (C, B) -> 총 6가지 경우순서를 고려하기 때문에 (A, B)와 (B, A)는 서로 다른 경우입니다. 조합이란?순서를 고려하지 않고 n개 중 r개를 뽑는 경우공식은 다음과 같습니다. $$ nCr = n! / r!(n-r)! $$예시[A, B, C] 중 2개를 뽑는다면:(A, B), (A, C), (B, C) -> 총 3가지 경우순서를 고려하지 않기 때문에 (A, B)와 ..