본문 바로가기

분류 전체보기60

백준 1003 피보나치 함수 DP 점화식 만드는게 중요하다.f[n] = f[n-1] + f[n-2]#include #include #include #include using namespace std;vector>v;//first = 0 sencond = 1int main() { v.resize(41); int n; int temp = 0; cin >> n; v[0].first = 1; v[0].second = 0; v[1].first = 0; v[1].second = 1; for (int i = 2; i > temp; cout 2025. 2. 17.
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.
백준 1620 포켓몬 마스터 c++ https://www.acmicpc.net/problem/1620 처음에는 그냥 넣고 선형탐색으로 해서 시간초가 나왔는데 해시맵으로 index번호와 함께 저장하면 바로 찾을 수 있어서 탐색이 필요 없다.#include#include#include#include#includeusing namespace std;vector > v;int main() { int n, m; cin >> n >> m; vector v1(n); vector v2(m); for (int i = 0; i > v1[i]; } for (int i = 0; i > temp; if (temp[0] 2025. 1. 3.
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.

티스토리툴바