학습목표 1. BFS(Breadth-First Search)가 무엇인지 학습 2. BFS의 수행과정에 대해서 학습 3. BFS와 최단 경로에 대해서 학습 4. BFS의 Java언어 기반 구현 5. BFS의 시간복잡도에 대해서 학습 1. BFS(Breadth-First Search, 너비우선순회)란 무엇인가? BFS란 그래프를 구성하는 노드들을 순회하는 방법 중에 하나입니다. 여기서 순회란 그래프의 모든 노드들을 방문하는 일을 의미합니다. BFS 알고리즘은 다음 순서로 노드들을 방문합니다. L₀ = {s}, 여기서 s는 출발 노드를 의미함 L₁ = L₀의 모든 이웃 노드들 L₂ = L₁의 이웃들 중 L₀에 속하지 않는 노드들 ... L_i = L_(i-1)의 이웃들 중 L_(i-2)에 속하지 않는 노드들 ..

학습목표 1. (무방향) 그래프에 대해서 학습 2. 방향 그래프와 가중치 그래프에 대해서 학습 3. 그래프를 표현하기 위한 방법인 인접행렬과 인접리스트에 대해서 학습 4. 무방향 그래프에서 경로와 연결성에 대해서 학습 1. (무방향) 그래프란 무엇인가? 각각의 노드들을 링크로 연결한 집합입니다. 이때 무방향이라는 것은 정점과 정점 사이가 연결된 링크가 존재하면 방향성이 없다는 의미입니다. 그래프에서 데이터를 담고 있는 것을 노드(Node) 또는 정점(Vertex)이라고 부릅니다. 그리고 2개 이상의 정점들을 연결하는 링크를 에지(Edge) 혹은 링크(Link)라고 부릅니다. V={1,2,3,4,5,6,7,8} E={(1,2),(1,3),(2,3), ... , (7,8)} n=|V|=8 (정점의 개수) m..

1. 멱집합(Power Set)이란 무엇인가? 멱집합이란 주어진 집합의 모든 부분집합들로 구성된 집합을 의미합니다. 예를 들어 아래 집합 S에 대한 모든 부분집합은 다음과 같습니다. 요소의 개수 3개인 집합 S 모든 부분집합의 개수는 총 8개입니다. 이는 멱집합의 부분집합의 개수는 2ⁿ개임을 알 수 있습니다. S = {a,b,c} Power set = {ø, {c}, {b}, {b,c}, {a}, {a,c}, {a,b}, {a,b,c}} 위 집합 S={a,b,c}의 모든 부분집합을 나열하려면 다음과 같습니다. a를 제외한 {b,c}의 모든 부분집합들을 나열하고 {b,c}의 모든 부분집합에 {a}를 추가한 집합들을 나열합니다. 다시 {b,c}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면 다음과 같..

1. Counting Cells in a Blob 이미지는 2개의 픽셀로 구성, 이미지 픽셀(image pixel) 또는 배경 픽셀(background pixcel) 서로 연결된 image pixcel들의 집합을 blob이라고 부름 상하좌우 및 대각 방향으로도 연결된 것으로 간주함 위 그림에서는 총 4개의 blob이 존재하고 각각의 크기는 5,5,13,1개입니다. 위 알고리즘의 문제는 입력으로 특정 좌표 (y,x)가 주어졌을 때 특정 좌표를 포함한 blob의 크기를 구하는 문제입니다. 예를 들어 (3,5)이 입력으로 주어졌을 때 blob의 크기는 13입니다. 입력 N*N 크기의 2차원 그리드(grid) 하나의 좌표 (y,x) 출력 픽셀 (y,x)가 포함된 blob의 크기 (y,x)가 어떤 blob에도 속..

1. 미로찾기(Maze) 입구는 (0,0)에서 시작하여 (7,7)에 도착하면 탈출을 성공합니다. pathway는 통로로써 지나갈 수 있습니다. wall은 벽으로써 지나갈 수 없습니다. Recursive Thinking 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중에서 하나에서 출구까지 가는 경로가 있어야함 boolean findPath(x,y) if (x,y) is the exit return true; else for each neighbouring cell (x', y') of (x,y) do if (x', y') is a pathway cell if findPath(x',y') return true; return false; 위 재귀적 사고는 무..

이전글 https://yonghwankim-dev.tistory.com/194 [알고리즘] 재귀(Recursion) 기본 개념과 예제 2 이전글 https://yonghwankim-dev.tistory.com/193 [알고리즘] 재귀(Recursion) 기본 개념과 예제 1 Recursion 재귀(Recursion)란 자기 자신을 호출하는 함수를 의미한다. void func(...) { ... func(...); ... }.. yonghwankim-dev.tistory.com 순환적 알고리즘 설계 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 존재해야 함 모든 case는 결국 base case로 수렴해야 함 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 ..