알고리즘 고득점 Kit - DFS/BFS

타겟넘버

제출 코드

def solution(numbers, target):
    answer = 0
    stack = [(0,0)]
    while stack:
        index, current_num = stack.pop()
        if index == len(numbers):
            if current_num == target:
                answer += 1

        else:
            stack.append((index+1, current_num+numbers[index]))
            stack.append((index+1, current_num-numbers[index]))
    return answer

알고리즘: 예를 들어 numbers = [1,1,1,1,1], target = 3 이라면 각 number 마다 (+1, -1), 즉 +와 -를 모두 붙여서 모든 경우의 수를 계산하는 알고리즘이다. 즉, 이 예시의 경우 stack에서 2^5의 계산이 이루어지는 것.

시간복잡도: O(2^n)

개선 사항: DP(동적 프로그래밍)의 원리(memorization)를 사용하면 시간복잡도를 개선할 가능성이 있다.

• 현재 문제 자체가 모든 경우를 다 봐야 하는 완전탐색 성격이야.
• 그래서 "모든 경로를 다 살펴봐야 정답을 구할 수 있는 문제" 에 해당해.
• numbers의 합이 크지 않거나 n이 작으면 그냥 지금처럼 O(2^n)이라도 괜찮아.
• 다만, 조금 개선을 하자면:

(1) 메모이제이션 (DP)을 활용할 수 있어.

• 같은 (index, current_sum) 조합이 중복으로 나올 수 있어.
• 이를 기억해두면 중복 계산을 피할 수 있지.

예를 들어 다음처럼 dict를 써서 중복 계산을 줄일 수 있어:

def solution(numbers, target):
    from collections import defaultdict
    
    dp = defaultdict(int)
    dp[0] = 1  # 초기값: 합이 0이 되는 경우는 1가지
    
    for num in numbers:
        next_dp = defaultdict(int)
        for current_sum in dp:
            next_dp[current_sum + num] += dp[current_sum]
            next_dp[current_sum - num] += dp[current_sum]
        dp = next_dp
        
    return dp[target]

• 이 방식은 O(n * k) 정도로 동작해.
• 여기서 k는 만들 수 있는 합의 범위야. (최대 sum(numbers)의 2배)
• 즉, n=20이고 합이 작은 경우, 훨씬 빠르게 끝나.

---

요약

항목 네 코드 (stack) 개선 코드 (DP)

시간 복잡도	O(2^n)	O(n * k) (k는 합의 범위)
특징	모든 경우 탐색	중복 합산을 줄여 빠름

---

정리

• 개선 방법: 메모이제이션(DP) 사용하면 O(n * k)로 최적화 가능.
• 단, n이 크지 않거나 sum(numbers)가 매우 크면 여전히 시간이 걸릴 수 있어.

---

"재귀 + 메모이제이션" 버전
(훨씬 깔끔하면서 빠르게 작동해.)

def solution(numbers, target):
    memo = {}
    
    def dfs(index, current_sum):
        if (index, current_sum) in memo:
            return memo[(index, current_sum)]
        
        if index == len(numbers):
            return 1 if current_sum == target else 0
        
        plus = dfs(index + 1, current_sum + numbers[index])
        minus = dfs(index + 1, current_sum - numbers[index])
        
        memo[(index, current_sum)] = plus + minus
        return memo[(index, current_sum)]
    
    return dfs(0, 0)

---

설명

• dfs(index, current_sum) 함수는 index번째까지 탐색했을 때 current_sum을 만드는 경우의 수를 리턴해.
• (index, current_sum) 조합이 한 번 계산되면 memo에 저장해서,
• 다음에 같은 조합이 오면 다시 계산 안 하고 바로 가져와.
• 이렇게 해서 중복 탐색을 확 줄이는 거야.

시간 복잡도는?

• 최악의 경우 (index, current_sum) 조합 수만큼 → O(n * k) 수준.
  (k는 만들 수 있는 sum 범위.)

---

포인트 요약

방법 특징

Stack 방식	코드 짧지만 중복 계산 많음 (O(2^n))
DP (반복문)	반복적으로 상태 업데이트 (O(n*k))
DP (재귀+메모이제이션)	직관적, 중복 피해서 빠름 (O(n*k))

---

추가로, 네 문제 풀이 스타일에 맞춰 반복문 방식이 나은지, 재귀 방식이 나은지 골라서 쓰면 돼!
(대회에서는 보통 반복문 DP를 더 선호하지만, 인터뷰에서는 재귀 + 메모이제이션이 더 직관적이야.)

---

네트워크

제출코드

def solution(n, computers):
	def dfs(computer, visited):
    	visited[computer] = True
        for i in range(n):
        	if computers[computer][i]==1 and visited[i]==False:
            	dfs(i,visited)
    visited = n*[False]
    answer = 0
    for _ in range(n):
    	if visited[_]==False:
        	dfs(_,visited)
            answer += 1
            
    return answer

 

알고리즘: dfs 함수는 연결된 끝까지 찾아가는 함수. visited값이 false인 요소들에 대하여 dfs 함수를 실행하면 해당 요소와 연결된 모든 요소들에 대해 visited 하게 되고(값이 True로 바뀌고) 하나의 연결된 덩어리들에 대해 answer + 1이 수행됨. 따라서 덩어리들의 개수를 세어 return 하게 됨.