알고리즘

BFS(Breadth First Search)

하나의 정점으로부터 시작하여 차례대로 모든 정점들은 한번씩 방문하는 것 ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지 전자회로에서 특정 단자와 단자가 서로 연결되엉 ㅣㅆ는지 너비우선 탐색(BFS)이 깊이우선탐색(DFS)보다 좀 더 복잡하다 특징 직관적이지 않은 면이 있다 → BFS는 시작노드에서 시작해서 거리에 따라 단계별로 탐색 BFS는 재귀적으로 동작하지 않는다 그래프 탐색의 경우 어떤 노드르 방문했었는지 여부를 반드시 검사 → 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다 BFS는 방문한 노드들은 차례대로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용 즉, 선입선출(FIFO)원칙으로 탐색 일반적으로 큐를 이용해서 반복 형태로 구현하는 것이 가자 잘 동작한다 ‘Prim..

2023. 8. 2. 14:47

알고리즘

DFS (깊이 우선 탐색) Depth First Searc

DFS는 가능한 모든 경로(후보)를 탐색한다 따라서 불필요한 것 같은 경로를 사전에 차단하거나 하는 등의 해동이 없으므로 경우의 수를 줄이지 못합니다 N가지의 경우의수를 가진 문제는 DFS로 처리가 불가능 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 넓게 탐색하기 전에 깊게 탐색하는 것이다 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에는 이 방법을 선택한다 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 단단하다 단순 검색 속도 자체는 너비 우선 탐색(BFS)보다 느리다 DFS의 특징 자기 자신을 호출하는 순환 알고리즘 형태를 가짐 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 ..

2023. 8. 2. 14:46

알고리즘

백트래킹

해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법이다 최적화 문제와 결정 문제를 푸는 방법이 됨 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다 이를 ‘가지치기’라고 불리는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다 즉, 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 이라고 한다 주로 문제 풀이에서 DFS등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다

2023. 8. 2. 14:46

알고리즘

플로이드 워셜

다익스트라 알고리즘과 비슷하지만 다른 개념이다 음의 가중치가 있어도 경로를 찾아갈 수 있다는 게 장점이다 모든 노드들과 모든 노드들 사이의 최단거리를 알려준다 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고 더 짧은 길이를 선택하여 줄이는 과정이다

2023. 8. 2. 14:45

알고리즘

Dijkstra (다익스트라)

다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려 줌 but, 음의 간선은 포함할 수 없다 (현실세계에서 음의 간선은 존재하지 않기 때문) 그렇기 때문에 현실세계에서 사용하기 적합한 알고리즘 중 하나이다 문제: 최단 거리는 여러개의 최단 거리로 이루어져 있다. → 작은 문제가 큰 문제의 부분 집합에 속할 수 있다 기본적으로 “하나의 최단 거리를 구할 때 이전까지 구했던 치단거리 정보를 그대로 사용”하는 것이 특징이다 BFS컨셉이고, 시작점을 기준으로 모든 노드들의 최단거리를 알려 준다 비슷하지만 다른 → 폴로이드 워셜

2023. 8. 2. 14:45

네트워크

네트워킹 2

이더넷(Ethernet) 네트워킹의 한 방식 즉, 네트워크를 만드는 방법 중 하나이다 특징 : CSMA/CD라는 프로토콜을 사용해서 통신한다 CSMA/CD : ‘Carrier Sense Multiple Access / Collision Detection’을 줄여서 부르는 방식 한마디로 “대충 알아서 통신하자”이다 이더넷 환경에서 통신을 하고 싶은 PC나 서버는 지금 네트워크 상에 통신이 일어나고 있는지를 확인합니다

2023. 8. 2. 14:43