Study/Algorithm

[알고리즘] BFS (너비우선탐색)

1. BFS (너비 우선 탐색)? BFS(Breadth-First-Search)는 너비 우선 탐색으로 큐(FIFO:선입선출)를 통해서 주로 구현이 됩니다. 출발 노드에서 가까운 것부터 접근하는 방식으로, 넓게, 층층히 탐색한다고 생각할 수 있습니다. 최단경로, 임의경로를 탐색해야하는 문제에서 주로 사용됩니다. DFS와 마찬가지로 방문체크를 해줄 필요가 있으며, 방문 체크를 하지 않을 경우 무한루프에 빠질 수 있습니다. 2. 기본적인 원리 기본적인 동작 원리는 다음과 같습니다. 현재 노드와 연결된 노드 중 방문되지 않은 모든 노드에 대해 방문체크 후 큐에 삽입 큐에서 가장 앞의 노드(가장 먼저 삽입된 노드) pop -> 새 노드 새 노드에 대해 1번 반복 큐에 원소가 없을 때까지 1~3 반복 처음에 시작노..

[알고리즘] DFS (깊이우선탐색)

1. DFS(깊이 우선 탐색)? DFS(Depth-First-Search)는 깊이 우선 탐색으로 스택 또는 재귀를 통해서 주로 구현이 됩니다. 하나의 인접노드에 대해 모든 인접노드를 다 탐색한 뒤 다음 인접노드로 넘어가는 방식으로, 해당 노드에 대해 방문여부를 체크하는 것이 핵심입니다. 방문여부를 체크하지 않으면 무한루프에 빠질 위험이 있습니다. 2. 기본적인 원리 기본적인 동작 원리는 다음과 같습니다. 현재 노드와 연결된 노드 중 하나의 노드 방문 여부 체크 만약 이미 방문된 노드라면, 패스 / 만약 아직 방문되지 않은 노드라면, 방문 현재 노드를 새로 방문한 노드로 변경 인접노드가 없을 때까지 1~3번 반복 더 이상 갈 수 있는 인접 노드가 없을 경우, 가장 최근의 분기점으로 되돌아가 다른 노드 방문..

[알고리즘] 스택(Stack), 큐(Queue)

알고리즘이란? 알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm 알고리듬[*], IPA: [ǽlɡərìðm])은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다.(출처: 위키피디아) 위의 정의에서도 볼 수 있듯이, 알고리즘이란 어떤 계산을 실행하기 위한 단계적 절차를 의미하고, 모든 계산에는 계산이 되어야 할 원소(element)가 존재합니다. 매우 간단하고도 당연한 말입니다. 정의적으로 얘기하기는 어렵지만, 그림 한장을 통해 아주 쉽게 이해할 수 있습니다. 매우 당연한 얘기입니다. 어떤 맛집의 비법 양념 만드는 법을 알고리즘이라고 한다면, 설탕, 간..