본문 바로가기

개발공부/알고리즘 이론7

2178 미로찾기 bfs c++ 선언을 전역변수로 하고 main에서 resize를 하니 코드가 깔끔해진 것 같다#include #include #include #include using namespace std;int n, m;vector> maze; // 미로 정보를 저장vector> distan; // 최단 거리vector> visited; // 방문 여부int dx[4] = { 0, 1, 0, -1 }; // 상, 하, 좌, 우int dy[4] = { 1, 0, -1, 0 };void bfs() { queue> q; // 시작점 초기화 q.push({ 0, 0 }); distan[0][0] = 1; visited[0][0] = true; while (!q.empty()) { .. 2025. 1. 7.
MST 알고리즘(크루스칼, 프림) 최소비용 신장트리 (Minimum Spanning Tree, MST)MST의 특징신장트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리입니다.최소 비용: 간선 가중치의 합이 최소가 되는 트리입니다.유일성: 모든 간선의 가중치가 서로 다르면 MST는 유일합니다. 즉 여러 경로가 나올 수 없다는 것이다.MST 알고리즘MST를 구하는 알고리즘은 다음과 같은 두 가지 주요 방법이 있다.1. 크루스칼 알고리즘 (Kruskal’s Algorithm)방법: 간단하게 생각하면 sort하고 sort순서대로 간선연결하고 cycle이 발생하는지 검증만 하면 끝이다.그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.최소 가중치의 간선부터 하나씩 추가합니다.사이클이 발생하지 않는 경우에만 간선을 추가합니다.모든 .. 2024. 12. 7.
Graph-다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘이란?먼저 백번 글로 읽는 것 보다  움짤을 보자 1. 다익스트라 알고리즘의 특징그래프 유형: 방향 그래프 또는 무방향 그래프에 적용 가능.가중치 조건: 간선 가중치(Weight)가 음수일 수 없음.출발점 기준: 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산.2. 알고리즘 동작 방식초기화:출발점 s에서 모든 정점까지의 거리 값을 무한대(∞)로 설정.출발점 s의 거리는 0으로 설정.우선순위 큐(최소 힙)를 사용하여 가장 가까운 정점을 효율적으로 추출.최단 거리 업데이트:현재까지 가장 짧은 경로로 방문하지 않은 정점을 선택.선택된 정점을 기준으로, 인접 정점의 거리 값을 업데이트.만약 새로운 경로가 기존 경로보다 짧다면, 해당 정점의 거리를 갱신.반복:모든 정점이 처리될 때까.. 2024. 12. 7.
그래프란?(Computer Science) bfs, dfs, scc, dag 1. 먼저 그래프란 뭘까?개체들과 개체들의 일대일 관계를 수학적으로 나타내는 표현 방법이다. 2. 그래프의 종류에는 이렇게 크게 세가지 정도가 있다.희소 그래프 (Sparse Graph): 간선의 수가 정점 수에 비해 상대적으로 적은 그래프.완전 그래프 (Complete Graph): 모든 정점이 서로 간선으로 연결된 그래프.밀집 그래프 (Dense Graph): 간선의 수가 정점 수에 비해 상대적으로 많은 그래프.3. 그리고 그래프의 기본 알고리즘은  bfs, dfs가 있는데 이를 응용한 알고리즘이 존재한다.BFS (Breadth-First Search)BFS는 그래프의 모든 정점을 층층이 탐색하는 알고리즘입니다. 큐(Queue)를 사용하여 시작 정점에서 가까운 정점부터 탐색한다.알고리즘 과정시작 정점.. 2024. 12. 6.
시간복잡도 g(n)은 f(n)의 상한이다. 2024. 10. 20.
알고리즘 시간 복잡도, 마스터 정리 일반적으로 반복문 같은 경우에는 보는게 쉽다. 그냥 가장 큰 루프를 보면 되는데, 까다로운 것은 자기호출 함수가 있을 때 까다롭다. 그래서 수학 잘하는 형님들이 공식을 만들었는데 바로 마스터 정리이다. 증명하는 과정도 있는데 난 수학이 잼병이라 잘 모르겠다. 이렇게 좋은게 있다~~ 하고 쓰면 될 것 같다. a: 재귀가 호출 된 수b: 기존의 n보다 얼마나 쪼개는가.c: 재귀가 아닌 것의 반복, 시간복잡도이다.  대표적인 합병 정렬을 예시로 보자.a= 2 -> 재귀가 2번 호출 되므로b=2 -> 재귀가 2로 나누어 지므로 mid =(low+high)/2k= 1 -> merge과정은 시간 복잡도가 n이므로  구체적으로 따지면 n-1번 수행하게 되는데 그냥 편의상 n으로 봐도 무방하다. 그렇다면  T(n) =.. 2024. 10. 7.

티스토리툴바