[백준] 1753번 최단경로 구하기 C++ 문제풀이

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 출발점이 명시된 최소 간선 찾기 문제이므로 다익스트라를 이용해 문제를 해결했다. 다익스트라 설명은 이전 문제에 설명했으므로 생략한다. https://itcodeheaven.tistory.com/87 [백준] 1916번 최소비용 구하기 C++ 문제풀이 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 ..

• format_list_bulleted 알고리즘
• · 2024. 2. 4.

[백준] 1916번 최소비용 구하기 C++ 문제풀이

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 최소 경로 찾기 문제에 자주 사용되는 알고리즘 2개가 있다. 1. 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 정점들간의 최단거리를 계산하는 알고리즘으로 시간복잡도가 O(N^3) 으로 크다. 2. 다익스트라 알고리즘 다익스트라 알고리즘은 한 정점으로부터 다른 모든 정점까지의 최단거리를 계산하는 알고리즘으로 O(ElogV)로 훨씬 빠르다 이 문제..

• format_list_bulleted 알고리즘
• · 2024. 2. 4.

[백준] 16236번 아기 상어 C++ 문제풀이

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 시뮬레이션 관련해서 구현을 해본 적이 없어 많이 고민했다. BFS를 이용해서 푸는 건 알겠는데, 디테일한 작은 부분부분에서 계속 틀리더라... 풀이는 1) 현재 상어의 위치에서 가장 먼저 1마리를 먹을때까지 BFS를 수행 -> 만약 여러 마리를 먹을 수 있는 경우는 맨 위, 맨 위에서도 맨 왼쪽에 있는 물고기를 먹는다. 2) 1마리를 먹으면 BFS를 종료 후 다시 상어의 위치에서..

• format_list_bulleted 알고리즘
• · 2024. 2. 2.

[백준] 1766번 문제집 C++ 문제풀이

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 전형적인 위상정렬 문제다. 위상정렬이란 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘이다. 여기서는 고려해야하는 순서는 2가지였다. 첫 번째는 '먼저 푸는 것이 좋은 문제'의 경우에는 먼저 풀어야한다. 두 번째는 문제집 번호가 낮은 번호부터 큰 번호 순서로 진행되어야 한다. 이 두가지를 고려해 queue에 진입차수가 0인 문제가 하나..

• format_list_bulleted 알고리즘
• · 2024. 1. 28.

[데이터엔지니어링] Airflow 실습(2) - Airflow 간단 설명

Airflow를 통해서 스케줄링을 하는 예시 이전에 Airflow란 무엇인지, 기본 구조는 무엇인지에 대해서 설명하겠다. Airflow란? Workflow Management Tool로, Workflow란 ETL과 같은 작업의 흐름을 말한다. Workflow는 DAG와 task라는 단위로 다양하게 구성할 수 있다. Airflow는 Python코드로 쉽게 workflow를 구성한다는 장점이 있다. 워크플로우 관리 도구의 주요 역할은 ‘ 정기적으로 태스크를 실행’하고 ‘비정상적인 상태를 감지하여 그것에 대한 해결을 돕는’것이다. Airflow Architecture Scheduler 스케줄된 workflow 를 trigger 하고, task 를 executor 에 실행하도록 제출 모든 task와 DAG를 모..

• format_list_bulleted 데이터엔지니어링
• · 2024. 1. 28.

[백준] 1202번 보석 도둑 C++ 문제풀이

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 가방에 최대 1개의 보석밖에 못 넣기 때문에 그리디로 풀면 된다. 가방에 넣을 수 있는 보석들을 다 Priority_queue에 넣어놓고, 그리고 가방에 담을 수 있는 무게를 넘어가면 Priority queue에서의 Top에 있는 걸 sum에 합치고 다음 가방으로 넘어가는 형식으로 해결한다. 소스 코드 #include #inc..

• format_list_bulleted 알고리즘
• · 2024. 1. 25.