Algorithm5 BFS - 그래프 탐색을 위한 너비 우선 탐색 알고리즘 BFS BFS는 Breadth First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대다. 그렇다면 BFS는 실제로 어떤 방식으로 구현할 수 있을까? BFS 구현 에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. - Part 02 Chapter 05 DFS/BFS 143p 알고리즘의 정확한 동작 방식은 다음과 같다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에.. 2023. 5. 16. DFS - 그래프를 탐색하기 위한 깊이 우선 탐색 알고리즘 DFS DFS는 Depth-Frist Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현한다. 일반적으로 그래프를 표현할 때 사용하는 단어들이다. 노드를 도시, 간선을 도로라고 생각해보자. A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해서, A와 B를 연결하는 도로(간선)를 거친다고 이해하면 쉬울 것이다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는.. 2023. 5. 16. DFS & BFS를 위한 (선형)자료구조의 기초 Data Structure 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. 자료구조란 데이터를 표현, 관리, 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음 두 핵심적인 함수로 구성된다. 삽입 (Push): 데이터를 삽입한다. 삭제(pop): 데이터를 삭제한다. 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다. 오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 .. 2023. 5. 11. Implementation - 아이디어를 코드로 바꾸는 구현 Implementation 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있을까? 그렇지 않다. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다. 어떤 문제가 구현하기 어려운 문제일까? 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제ㅡ 문자열이 입력으로 주어졌을 때 한 문자.. 2023. 5. 4. 이전 1 2 다음
