알고리즘과 자료구조의 관계

알고리즘과 자료구조의 관계

• 알고리즘: 이 문제를 효율적으로 풀기 위해 어떤 순서로, 어떤 데이터에 접근할 것인가? → 절차, 로직
• 자료구조: 어떻게 데이터를 배치해야 그 절차가 효율적으로 돌아갈까 → 물리적 저장 형태

즉, 자료구조는 알고리즘이 필요로 하는 데이터 접근 순서를 물리적으로 구현해주는 수단이다. 생각해보면 값을 저장하는 것 자체는 배열에 쭉 저장해도 가능하다. 하지만 그렇게 하면 알고리즘이 다음 단계에서 원하는 결과에 바로바로 접근하지 못하게 된다.

 

메모리 자체는 사실 단순하다. 그냥 번지수가 붙은 저장 공간이 일렬로 늘어서 있을 뿐이다. 이 위에 "어떻게 배치하면 특정 연산이 빨라질까"를 사람이 고민해서 만든 설계 패턴이 배열, 연결리스트, 해시테이블, 트리, 힙 같은 것들이다. 그런데 모든 연산을 다 잘하는 자료구조는 없다. 배열은 인덱스 접근은 빠르지만 중간 삽입/삭제는 느리다. 연결리스트는 그 반대다. 따라서 문제를 풀 때 "이 문제에서 반복적으로 필요한 연산이 뭔가"를 먼저 파악하고, 거기에 맞는 효율적인 자료구조를 고르고, 그 위에서 알고리즘을 설계하는 순서로 사고해야 한다.

---

알고리즘에 적합한 자료구조 찾기

DFS는 왜 스택을 쓸까?

DFS(깊이 우선 탐색)의 목표: "한 방향으로 끝까지 파고들다가, 막히면 가장 최근에 갈라졌던 지점으로 돌아간다."

이 "가장 최근 것부터 되돌아간다"는 특성이 바로 LIFO(Last In First Out)다. 그리고 LIFO를 구현한 자료구조가 정확히 스택이다.

DFS의 요구사항: "가장 최근에 방문한 갈림길로 되돌아가고 싶다"
                          ↓
스택의 특성: "가장 나중에 넣은 걸 가장 먼저 꺼낸다"
                          ↓
→ 완벽히 일치 그래서 DFS = 스택 (혹은 재귀 호출 스택)

재귀 자체도 내부적으로 함수 호출 스택(call stack)을 쓰고 있다. 그래서 재귀로 짠 DFS는 "암묵적으로 스택을 쓰고 있는" 셈이다. 재귀를 명시적 스택으로 바꿔써도 DFS가 똑같이 동작하는 이유가 여기 있다.

BFS는 왜 큐를 쓸까?

BFS(너비 우선 탐색)의 목표: "가까운 것부터 순서대로, 먼저 발견한 것부터 처리한다."

이건 FIFO(First In First Out)다. 그리고 FIFO를 구현한 자료구조가 큐다.

BFS의 요구사항: "먼저 발견한 노드를 먼저 처리하고 싶다 (계단식으로 넓게)"
                          ↓
큐의 특성: "먼저 넣은 걸 먼저 꺼낸다"
                          ↓
→ 완벽히 일치! 그래서 BFS = 큐

 

DFS와 BFS는 사실 코드가 거의 똑같다. 자료구조를 스택으로 쓰느냐 큐로 쓰느냐 그 차이 하나가 전체 탐색 방식을 완전히 바꿔버린다. 이게 바로 "자료구조 선택이 알고리즘의 행동을 결정한다"는 걸 가장 극명하게 보여주는 예시다.

DP는 왜 배열(테이블)을 쓸까?

DP의 요구사항: "이미 계산한 부분 문제의 답을 나중에 즉시 꺼내 쓰고 싶다."

이러려면 "인덱스(또는 키)로 즉시 접근 가능한" 자료구조가 필요하다. 배열은 인덱스로 O(1) 접근이 가능하고, 딕셔너리도 키로 O(1) 근사 접근이 가능하다.

DP의 요구사항: "dp[3]을 나중에 즉시 다시 꺼내쓰고 싶다"
                          ↓
배열/딕셔너리의 특성: "인덱스/키로 즉시 접근 가능"
                          ↓
→ 그래서 DP = 배열(또는 딕셔너리) 기반 메모

 

만약 배열 대신 연결 리스트를 썼다면? 특정 인덱스에 접근하려면 처음부터 순회해야 하니 O(n)이 걸린다. DP의 핵심(빠른 재사용)이 무너지는 것이다. 자료구조를 잘못 고르면 알고리즘의 시간복잡도 자체가 망가진다.

다익스트라는 왜 우선순위 큐(힙)를 쓸까?

다익스트라의 요구사항: "지금까지 발견한 노드들 중, 거리가 가장 짧은 노드를 매번 즉시 꺼내고 싶다."

일반 배열이나 리스트로 이걸 하려면 매번 전체를 훑어서 최솟값을 찾아야 한다 (O(n)). 근데 우선순위 큐(힙)를 쓰면 최솟값을 O(log n)에 꺼낼 수 있다.

다익스트라의 요구사항: "가장 급한(가까운) 걸 즉시 꺼내고 싶다"
                          ↓
힙의 특성: "최솟값(또는 최댓값)을 빠르게 꺼낼 수 있다"
                          ↓
→ 그래서 다익스트라 = 그래프 + 우선순위 큐

정리

알고리즘 절차	필요한 데이터 접근 패턴	적합한 자료구조
DFS: 최근 것부터, 되돌아가기	LIFO	스택
BFS: 먼저 온 것부터, 순서대로	FIFO	큐
DP: 인덱스/키로 즉시 재사용	랜덤 접근	배열, 딕셔너리
가장 급한(작은/큰) 것 즉시	최솟값/최댓값 빠른 추출	힙(우선순위 큐)
관계·연결 표현	노드 간 이동	그래프

 

---

같은 알고리즘도 자료구조에 따라 효율이 달라진다

같은 로직(알고리즘)이라도 어떤 자료구조 위에서 돌아가느냐에 따라 시간복잡도가 완전히 달라질 수 있다.

• DP를 배열 대신 연결 리스트로 구현?
  → 인덱스 접근에 O(n)이 걸려서 DP의 이점이 사라짐
• 다익스트라에서 "가장 가까운 노드 찾기"를 배열 순회(O(n))로 하느냐, 힙(O(log n))으로 하느냐?
  → 전체 알고리즘의 시간복잡도 자체가 바뀜(O(V²) vs O(E log V))
• DFS/BFS는 로직이 거의 동일하지만 스택이냐 큐냐에 따라 탐색 순서(깊게 vs 넓게)가 완전히 달라짐

즉, 알고리즘의 "논리"와 그 논리를 뒷받침하는 "자료구조"는 분리해서 생각할 수 있지만, 실제 성능은 이 둘의 조합으로 결정된다.

최근 공부한 사례: DFS/BFS의 visited를 무엇으로 관리할 것인가?

visited 자료구조	조회	속도	제약 조건
리스트 + in	if node not in visited:	O(n)	없음 (근데 느림)
불리언 배열	if not visited[node]:	O(1)	노드가 0~n-1 정수여야 함
set(해시)	if node not in visited: (set)	O(1) 평균	없음 (가장 유연하면서 빠름)

 

visited는 "이미 방문했는가?"를 확인하는 역할을 한다. 그런데 같은 DFS/BFS 로직이라도 이 조회를 어떤 자료구조로 하느냐에 따라 속도가 달라진다. 리스트로 visited를 관리하면 in 연산이 매번 처음부터 끝까지 훑어야 해서 O(n)이 걸린다. visited 체크는 탐색 도중 아주 여러 번 반복되는 연산이기 때문에, 이걸 리스트로 짜면 원래 O(V+E)여야 할 전체 탐색이 O(V*E)까지 느려질 수 있다. 반면 인덱스 기반 배열이나 set을 쓰면 조회가 O(1)이라 이런 문제가 없다.

 

참고로 노드가 정수 인덱스로 딱 떨어지면(예: 0~n-1) 불리언 배열이 set보다 살짝 더 빠르고 메모리도 적게 쓴다. 근데 노드가 좌표 튜플이거나 문자열이면 set을 쓰는 게 사실상 유일한 선택지다.