엔지니어 동행하기

DFS문제에서 어려울 수 있는 부분은 재귀함수의 동작 원리를 알아야만 문제를 풀 수 있다는 점 입니다. DFS 알고리즘에서 어떻게 재귀함수를 활용하는지를 중점으로 설명드리겠습니다. 기본구조 & 탐색과정 def dfs(v): //O(E) 백트래킹 관계없이 v 방문 시 수행할 코드 if visited[v] ==1: //백트래킹 조건 return visited[v] =1 //(깊이 탐색하기 전 v 에서 수행할 코드) if/for 추가적인 탐색 조건 //탐색 우선순위가 높은 경우 dfs(i) for i in graph[v]: //인접노드 탐색 dfs(i) //깊이 탐색한후 v에서 수행할 코드 기본이 되는 DFS 코드를 분석하면 3부분으로 나눌 수 있습니다. if문(백트래킹 조건) 방문한 노드에서 수행할 코드 f..

제한된 시간 내에 빠르고, 오류 없는 풀이를 하기 위해서는 반드시 의사 코드(pseudo-code)를 작성하는 연습을 해야 합니다. 실제 문제는 다음과 같은 단계로 풀게 됩니다. Step 1. 문제 정독, 상황 구체화 Step 2. Code Logic에 집중하여 의사코드 작성 Step 3. 예외 Case를 고려하여 코드 구현 Step 4. Test Case로 Debugging 의사코드 작성 규칙 1) 한 줄에 '하나의 동작을 나타내는 명령' 작성 실제 코드를 작성하는 방식과 같이 작성하는 것을 의미합니다. 개발하는 스타일에 따라 달라질 수 있는 부분이며, 한 줄에는 하나의 동작을 실행하는 코드만을 작성하길 권장합니다. 2) 어떤 동작을 하는 코드인지 의미를 명확하게 작성 얼마나 detail 하게 작성할지..

그래프 탐색 BFS 문제를 처음 접했을 때 어려울 수 있는 점은, BFS 문제에 좌표에 대한 내용이 많이 나오는데 이를 그래프 개념과 연결시키는 부분입니다. 카카오 코딩 테스트 문제(KAKAO BLIND RECRUITMENT 2019~2021)를 직접 풀어보며 이에 대해 정리했던 내용을 공유합니다. 기본 구조 from collections import deque def bfs(start): global n dist = [math.inf] * n q = deque([]) q.append(start) dist[start] = 0 while q: node = q.popleft() for i in graph[node]: # nextCost 계산 if nextCost < dist[i]: q.append(i) di..