GPT와 함께하는 코딩 테스트 준비

Intro.

구름톤 챌린지로 오늘의 문제인, [[Goorm_연합]]을 풀이하였습니다

요즘은 코딩 테스트는 기본이라 꾸준히 풀고 있습니다.

확실하게 실력을 늘리려면, 다른 사람의 코드를 보거나, 제 코드에 대한 피드백을 받는거라 생각합니다

딱 GPT가 코드 인터프리터와 함께 사용하면 괜찮겠는데? 싶어 시작했습니다

내 코드 최적화

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

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

최적화한 코드를 반환하고, 관련 개념과 코드를 검증하도록합니다

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.