알고리즘(C++)11 그래프 탐색 - 너비 우선 탐색(BFS) DFS는 스택을 사용해서 구현했었다BFS는 큐를 사용한다!! 큐는 들어간 순서대로 나오는 거 FIFO 1) 큐가 비었나 확인(비었으면 모든 노드 다 방문한 거임. 탐색종료)2) 큐에서 노드를 팝3) 방금 막 팝한 노드 인접 노드 확인-> 그 중 방문 안한거 있으면 그 노드 큐에 푸쉬 후 방문 처리 1. 그림으로 보는 큐를 이용한 DFS 2. 코드로 보는 큐로 구현한 DFS#include #include #include #include using namespace std;// 인접 리스트vector> AdjList;// 방문 여부vector bVisited;// BFS 함수void BFS(int StartNode){ queue Q; Q.push(StartNode); bVisite.. 2025. 2. 5. 그래프 탐색 - 깊이 우선 탐색 DFS DFS는 스택 or 재귀 이용해서 푼다1. 스택을 활용한 DFS탐색 전 시작 노드 정하기스택에 시작 노드를 Push스택에 있는 노드는 방문 안 한 노드 && 방문 예정 노드임스택이 비었는지 확인-> 비었으면 모두 방문한거니까 탐색 종료스택에서 노드 팝-> 팝한 원소는 최근 스택에 푸시한 노드팝한 노드의 방문 여부 확인-> 안했으면 방문방문한 노드와 인접 모든 노드 확인-> 안 했으면 노드를 스택에 푸시 1.1. 그림으로 보는 스택으로 만드는 DFS 1.2. 코드로 구현한 DFSsort함수 쓰려고 algorithm 추가했당. #include #include #include #include using namespace std;// 인접 리스트vector> AdjList;// 방문 여부vector bVisit.. 2025. 2. 4. 그래프 탐색 - DFS vs BFS 1. 경로 찾는 문제가 나온다면..?방법은 2개가 있다1) 더 이상 탐색할 노드 없을 때 까지 탐색해본다. 더 이상 탐색할 노드 없으면 최근 방문 노드로 되돌아가서 가지 않은 노드 방문한다2) 현재 위치에서 가장 가까운 노드 모두 싹 돌고, 다음 노드로 넘어감. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문이게 뭐냐? 각각 깊이 우선 탐색, 너비 우선 탐색임이해가 쉽도록 아래 그림을 확인해보자.1.1. 깊이 우선 탐색 1.2. 너비우선탐색2. 코테 풀 때!!!탐색은 해야하는데 최단 경로 구하는 거 아니면 DFS 쓰면 됨최단 경로 찾는다? BFS 갈겨~~~~ 2025. 2. 4. 그래프 1. 그래프란?노드(정점,vertex)랑 간선(edge)을 이용한 비선형(일렬이 아닌 것) 데이터 구조데이터 관계 표현 시 사용함방향성 : 간선은 방향이 있을 수도 없을 수도 있음없으면 무방향 그래프 undirected graph있으면 방향 그래프 directed graph둘다 서로 가리키는 간선도 있음가중치 : 흐름의 정도가중치가 있는 그래프 : weight graph순환 : 다시 돌아오는 경로있으면 순환 그래프 cycle graph없으면 비순환 그래프 acyclic graph 2. 그래프 구현은 어떻게?구현할 때 인접행렬(adjacency matrix), 인접리스트(adjacency list) 두가지 방법이 있음"송파역에서 석촌역으로 유동인구가 5000명 발생" 을 구현해보자데이터 담고 있는 노드 .. 2025. 2. 4. 유니온 파인드 알고리즘 저번 포스팅에서 집합 개념을 정리했다집합 알고리즘의 메인 연산 : 합치기, 탐색합치기는 union, 탐색은 find라고 불러서 유니온파인드 알고리즘이라고 함find와, union 연산을 각각 알아보자 1. 파인드 연산특정 노드의 루트 노드가 뭔지 탐색하는 방법임보통, find 연산은 특정 노드가 같은 집합에 있는지 확일할 때 씀예) a,b 노드가 있는데 얘네의 루트 노드가 같다면 얘네는 같은 집합임1) 현재 노드의 부모 노드를 확인2) 부모 노드 계속 확인하다가 부모 노드가 루트노드이면 찾기 종료3) 아니라면 계속 반복1.1. find 예시 7을 찾아보자! find(7)1) 7의 루트노드를 찾는다. -> (루트노드는 인덱스랑 밸류가 같음)2) 루트 노드 찾기 전까지 계속 반복하고 찾으면 find 종료하면.. 2025. 2. 3. 배열 - 두개 뽑아서 더해서 정렬하기 1. 문제/* 문제 : - 오름차순으로 반환하는 솔루션함수만들기 - 근데 이 넘버스 정수 배열에서 서로 다른 인덱스에 있는 2개 요소 뽑아 더해 만들 수 있는 모든 수로 만들어야함 */ 2. 내 접근역시나 못 풀었다...하지만 접근은 조금 해봤다. 아래와 같음#include #include using namespace std;//=========================================================================vector solution(vector numbers) { // 일단 매개변수로 받은 넘버스 예시 5,4,3,2면 그 뒤에꺼랑 한개씩 짝지운다 // 어케 짝 지우지? 5,4/5,3/5,2/4,3/4,2/3,2.. 2025. 1. 30. 이전 1 2 다음
