GPT와 함께하는 알고리즘 공부 방법

Intro.

구름톤 챌린지로 오늘의 문제인, Goorm_연합을 풀이하였습니다
요즘은 코딩 테스트는 기본이라 꾸준히 풀고 있습니다.

확실하게 실력을 늘리려면, 다른 사람의 코드를 보거나, 제 코드에 대한 피드백을 받는거라 생각합니다
딱 GPT가 코드 인터프리터와 함께 사용하면 괜찮겠는데? 싶어 시작했습니다

내 코드 최적화

def find_union_iterative(N, M, graph):
	# Step 1: Initialize the graph
	g = defaultdict(set)
	for a, b in graph:
			g[a].add(b)

	# Step 2: Check for bidirectional links and create a union set
	visited = set()
	unions = []
	def dfs_iterative(start_node):
			stack = [start_node]
			current_union = set()
			while stack:
					node = stack.pop()
					if node not in visited:
							visited.add(node)
							current_union.add(node)
							for neighbor in g[node]:
									if neighbor not in visited and node in g[neighbor]:
											stack.append(neighbor)
			return current_union

	for node in range(1, N + 1):
			if node not in visited:
					current_union = dfs_iterative(node)
					unions.append(current_union)

	# Step 3: Return the number of unions
	return len(unions)
print(find_union_iterative(N, M, graph))

기본적으로 깊이 우선 탐색을해서, 각 지점을 방문하는 아이디어로 문제를 풀이하였습니다

코드 인터프리터를 사용하였고, 프롬프트는 아래와 같습니다

최적화한 코드를 반환하고, 관련 개념과 코드를 검증하도록합니다
GPT의 문제 풀이를 돕기 위해, 문제와 제가 짠 코드 그리고, 테스트 케이스 2개를 제시하였습니다

음흠 잘 알려줍니다, 코드를 실행 시켜보니 정답인 코드입니다

왜 이 코드가 더 효율적인 코드를 만드는지 다시 물어봅니다. 일종의 검증 과정을 거치는거죠

답변은 아래와 같습니다. 자료형의 특징을 이용해서 최적화 했음을 알 수 있습니다.

1. Use a set for visited nodes for faster look-up:

   • A set in Python is implemented as a hash table, which allows for constant time (O(1)) look-up operations.
   • When you’re checking whether a node has been visited or not, using a set is faster than using a list, where the time complexity for look-up would be (O(n)).

2. Use adjacency lists instead of a defaultdict for more efficient storage:

   • A defaultdict with sets (defaultdict(set)) is a more flexible but heavier data structure compared to a simple list of lists (adjacency list).
   • For this problem, you don’t need the extra functionality that defaultdict provides, such as automatic key creation.
   • Lists are generally more memory-efficient and faster for iteration in Python compared to sets.
   • By knowing the number of nodes (N) in advance, you can initialize a list of (N + 1) elements to represent the adjacency list, which eliminates the need to dynamically create keys.

나랑 다른 방식으로 풀이

이제 제 풀이와 완전 다른 풀이를 보고 싶으니 질문합니다

저는 DFS로 풀었는데 이 친구는 Union-Find 알고리즘를 사용해서 풉니다
실행 시간 초과가 발생해서 수정 요청 제출했더니, 모든 테스트 케이스를 통과하였습니다

from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1] * n

    def find(self, u):
        if self.parent[u] == u:
            return u
        self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def merge(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.rank[u] > self.rank[v]:
            u, v = v, u
        self.parent[u] = v
        if self.rank[u] == self.rank[v]:
            self.rank[v] += 1

def find_number_of_unions_efficient(N, M, graph):
    uf = UnionFind(N + 1)
    
    # Create an adjacency list
    adjacency_list = defaultdict(set)
    for a, b in graph:
        adjacency_list[a].add(b)
        
    for a, b in graph:
        if b in adjacency_list[a] and a in adjacency_list[b]:
            uf.merge(a, b)
            
    unique_parents = {uf.find(i) for i in range(1, N + 1)}
    return len(unique_parents)

N, M = map(int, input().split())
graph = [tuple(map(int, input().split())) for i in range(M)]

result1 = find_number_of_unions_efficient(N, M, graph)
print(result1)

제가 작성한 코드와 GPT가 만든 코드를 비교 분석합니다

Union-Find 방식의 GPT 코드가 메모리 효율은 더 뛰어나다고 합니다

결과적으로 그렇다면, 코딩 테스트에서는 어떤 방식을 사용할 것인지, 그리고 어떤 코드가 더 효율적인지 물어봅니다

답변도 잘 달아 주었습니다. DFS를 추천한다고 합니다. 가독성과 디버깅에 이점이 있고, 특히나 시간 복잡도가 N+M이기 때문입니다. (엄청나죠…)

핵심 : 무엇을 말하고 싶었는가?

GPT 코드 인터프리터는 코드를 실행 할 수 있다는 장점이 있습니다
그냥 GPT에게 물어볼 경우에, 검증이 되지 않아 환각 현상이 발생 할 때가 있는데, 알고리즘 풀이와 같은 상황에 코드 인터프리터를 사용할 경우 오차를 줄일 수 있습니다

정확한 요구사항, 제약 조건, 테스트 케이스만 주어진다면 충분히 제가 작성한 코드를 검증하고 새로운 방향성(다른 풀이)에 대한 인사이트를 얻을 수 있습니다

또한, 다른 언어로 문제를 푸는 사람이라도, Python으로 작동하는 코드를 작성하고, 컨버팅 할 경우에 잘 작동하기 때문에 괜찮은 공부 방식이라 생각합니다