Algorithm 썸네일형 리스트형 [C] 너비 우선 탐색(BFS; Breadth First Search) 개념 및 정리 개념 너비 우선 탐색(BFS; Breadth First Search)은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘으로, 동작 과정이 직관적이여서 이해하기 쉽다 (a)의 그래프에서, a를 탐색의 시작점이라고 하자 H0의 a를 방문하고, H1의 b d e h, 그리고 H2, H3에 속한 정점들을 순서대로 방문해 나간다 이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 먼저 꺼내는 것이다 시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문이다 이 조건을 큐를 사용하여 만족시킬 수 있게 된다 snupi.tistory.com/20 [C code] 원형 큐 (Circular Queue) #include #include #define size 10 typedef struct Queue .. 더보기 [C] 깊이 우선 탐색(DFS; Depth First Search) 개념 및 정리 개념 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한다 깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 따라가고, 더이상 갈 곳이 없다면 포기하고 마지막에 온 간선을 따라 뒤로 돌아간다 3번의 과정에서 우리는 재귀 호출을 이용하여 간단하게 구현할 수 있다 코드 인접 행렬 사용 #include #define MAX 1001 int adj[MAX][MAX]; //인접행렬 만들때 사용 int visited[MAX]; //방문했는지 check void ini.. 더보기 [Java] 너비 우선 탐색(BFS; Breadth First Search) 개념 및 정리 개념 너비 우선 탐색(BFS; Breadth First Search)은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘으로, 동작 과정이 직관적이여서 이해하기 쉽다 (a)의 그래프에서, a를 탐색의 시작점이라고 하자 H0의 a를 방문하고, H1의 b d e h, 그리고 H2, H3에 속한 정점들을 순서대로 방문해 나간다 이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 먼저 꺼내는 것이다 시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문이다 이 조건을 큐를 사용하여 만족시킬 수 있게 된다 코드 import java.io.*; import java.util.*; class BfsGraph { private int nV; // 노드의 개수 private LinkedList adj[.. 더보기 [Java] 깊이 우선 탐색(DFS; Depth First Search) 개념 및 정리 개념 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한다 깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 따라가고, 더이상 갈 곳이 없다면 포기하고 마지막에 온 간선을 따라 뒤로 돌아간다 3번의 과정에서 우리는 재귀 호출을 이용하여 간단하게 구현할 수 있다 코드 인접 리스트 import java.util.ArrayList; import java.util.Scanner; class DfsGraph { private int nV; // 정점의 개수 priv.. 더보기 [Python] KMP 알고리즘 (문자열 검색 알고리즘) 글에 앞서, "알고리즘 문제 해결 전략"에서 공부한 내용을 정리한 글임을 알려드립니다 문자열 검색 우리는 수많은 문자열 자료를 다룬다 이는 문서 파일, 웹페이지, 이메일 등에서 쓰이고, 정보 검색(information retrieval)이나 생물 정보학(bioinformatices) 분야에서 유용하게 사용된다 긴 문자열 H에서 짧은 문자열 N을 부분 문자열로 포함하는지, 그 시작 위치는 어디인지 문제를 해결해보자 가장 단순한 방법으로는 한 칸씩 옮겨 확인하는 방법이 있다 더 효율적인 방법은 없을까 ? KMP 알고리즘 우리는 검색 과정에서 얻는 정보를 잘 활용하면 많은 시간을 절약할 수 있다 그림 1에서 확인할 수 있듯이, 우리는 시도조차 피할 수 있는 "시작 위치 후보"가 있음을 알 수 있다 이 때 우리.. 더보기 이전 1 2 3 4 5 ··· 7 다음
