코딩 테스트 연습/이론5 BFS/DFS(2) 간단한 DFS 구현해 보기 깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 또한 DFS는 스택을 이용하는 알고리즘 이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 예제 코드는 다음과 같다. # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end= '') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph , i , visi.. 2024. 2. 28. BFS/DFS(1) 그럼 이제 본격적으로 DFS에 대해 알아보자. DFS가 '깊이우선탐색'이라는 것은 귀에 딱지가 앉을 정도 많이 들어서 이미 알고있었다. 하지만 구체적으로 어떻게 작동하는 것일까? 이번 포스팅에서는 DFS의 작동 원리에 대해서 알아보자. DFS는 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. DFS는 '스택' 자료구조를 사용하며, 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2. '스택의 최상단 노드'에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고, 방문처리를 한다. 방문하지 않은 인접노드가 없다면 스택에서 최상단 노드를 꺼낸다. 3. 2번 과정을 끝날때까지.. 2024. 1. 2. 그래프 vs 트리 그래프를 탐색하는 두 알고리즘으로 DFS/BFS에 대해서 공부하고 있다. 그래프를 탐색하는 알고리즘에 대해서 공부하고 있으면서 나는 그래프가 무엇인지도 모르고 있었다. 그래프가 '여러개의 노드와 이들을 연결하는 간선으로 이루어진 자료구조'인 것은 지난 포스팅을 통해 알게되었는데, 그래프의 그림을 보니 트리와의 차이점을 모르겠다는 생각이 들었다. 이번 포스팅에서는 '그래프'와 '트리'의 차이점에 대해서 알아보도록 하자. 그래프(Graph)? 여러개의 노드(node)와 이들을 연결하는 간선(edge)으로 이루어진 자료구조 즉, 연결된 객체 간의 관계를 표현할 수 있는 자료구조 그래프의 특징 그래프는 네트워크 모델이다. 그래프는 순환 혹은 비순환 구조를 이룬다. 그래프는 루트노드라는 개념이 없다. 부모 - 자.. 2024. 1. 1. DFS/BFS(0) BFS/DFS는 그래프를 탐색하기 위한 대표적인 두 알고리즘이다. 나는 정말 아무것도 모르는 감자이기 때문에, BFS/DFS를 다루기 이전에 우선 탐색과 그래프의 개념을 정확하게 이해할 필요가 있었다. 탐색이란? 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 주로 그래프, 트리 등의 자료구조 안에서 탐색을 진행하게 된다. 그래프(GRAPH)란? 그래프는 여러개의 노드(node)와 이들을 연결하는 간선(edge)으로 이루어진 자료구조이다. 이때 노드를 정점(vertex)이라고도 말한다. 그래프를 탐색한다는 것은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데 '인접 행렬' 방식과 '인접 리스트' 방식이다... 2023. 12. 31. Greedy 대망의 첫번째 포스팅이다. 꾸준하게 포스팅 할 것을 생각해서 무리하게 많은 내용을 담기보다는 조금씩 확실하게 포스팅 하자. Greedy(탐욕스러운) 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 알고리즘을 의미한다. 지금 당장 최적인 답만 고르기 때문에, 현재의 선택이 나중에 미칠 영향 따위는 고려하지 않는다. 마시멜로 실험을 떠올리면 이해가 빠를 것 같다. 아이들은 15분동안 마시멜로를 먹지 않으면, 15분 후에 2개의 마시멜로를 먹을 수 있다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는다는 것이다. 하지만 이는 "15분 후에 2개를 먹는다"라는 최적의 해에 도달하지 못한다. 이렇듯, 그리디 알고리즘은 전체 문제의 최적해를 찾지 못하는 경우도 발생한다. .. 2023. 12. 17. 이전 1 다음
