반응형 Coding Test28 [Coding Test][Python][Shortest Path] Prim 알고리즘 Prim 알고리즘에 앞서 Kruskal 알고리즘을 보고 오시면 좋습니다. [Coding Test][Python][Shortest Path] Kruskal 알고리즘 개념 및 예제, Union - Find 자료구조1. Kruskal 알고리즘이란?그래프의 Minimum Spanning Tree(MST, 최소 신장 트리) 를 구하는 대표적인 알고리즘입니다.Minimum Spanning Tree란 그래프의 모든 Vertex가 연결하면서 Edge의 Weight의 합이 최소가 되는 Trself-objectification.tistory.com 1. Prim 알고리즘이란?Prim 알고리즘은 Kruskal 알고리즘과 같이 Graph에서 Minimum Spanning Tree(MST)를 찾는 알고리즘입니다.특징Kruska.. 2025. 3. 18. [Coding Test][Python][Shortest Path] Kruskal 알고리즘 개념 및 예제, Union - Find 자료구조 1. Kruskal 알고리즘이란?그래프의 Minimum Spanning Tree(MST, 최소 신장 트리) 를 구하는 대표적인 알고리즘입니다.Minimum Spanning Tree란 그래프의 모든 Vertex가 연결하면서 Edge의 Weight의 합이 최소가 되는 Tree를 의미합니다.알고리즘 특징Edge를 중심으로 접근하여 MST를 구성Greedy 알고리즘 사용Undirected Weighted Graph에 적용가능시간 복잡도 : $O(E log E)$2. Kruskal 알고리즘 동작 과정위의 그래프에서 Kruskal 알고리즘을 적용해보겠습니다.1) 모든 Edge를 가중치가 작은순으로 정렬Edge의 Weight가 작은 순으로 정렬한 후 가장 작은 Weight를 가진 Edge를 선택합니다.2) 정렬된 E.. 2025. 3. 18. [Coding Test][Python][Shortest Path] Floyd-Warshall 알고리즘 개념 및 예제 Floyd - Warshall에 앞서 Dijkstra 알고리즘을 먼저 보고 오시면 좋습니다. [Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제1. Dijkstra Algorithm 이란?Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적self-objectification.tistory.com 1. Floyd - Warshall(플로이드 워셜) 알고리즘 이란?Dijkstra 알고리즘은 한 지젬에서 다른 지점까지로 가는 최단거리만 제공하기 때문에, 모든 지점의 최단거리를 .. 2025. 3. 18. [Coding Test][Python][CodeTree] Binary Tree 개념 및 구현 1. Binary Tree(이진 트리) 란?Tree의 각 node가 최대 두 개의 자식(0개, 1개, 2개) Node를 가지는 Tree의 형태의 자료구조입니다.위의 그림은 Binary Tree를 나타낸 그림입니다.2. Binary Tree(이진 트리) 구현Binary Tree는 구현이 간단하는 특징이 있습니다.1) 배열을 이용한 Binary Tree 구현Binary Tree는 자식 Node가 두개이기 때문에 하나는 왼쪽, 하나는 오른쪽에 존재합니다.이 때, Root Node를 배열의 Index 1에 넣게 되면 왼쪽 자식 Node를 Index 2, 오른쪽 자식 Node를 Index 3에 넣어 주면 됩니다.이러한 방식으로 Parent Node의 Index를 i라고 하면 왼쪽 자식 Node는 Index $2i.. 2025. 3. 12. [Coding Test][Python][백준] 삼성 SW 코딩 테스트 기출문제 BOJ #12100 2048(Easy) 문제)2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.) 의 경우에서 위로 블록을 이동시키면 의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 의 상태가 된다.의 상태에서 블록을 오른쪽으로 이동시키면 가 되고, 여기서 다시 위로 블록을 이동시키면 이 된다. 여기서 오른쪽으로 블록을 이.. 2025. 2. 27. [Coding Test][Python][백준] BOJ #2304 창고 다각형 문제)N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.지붕의 가장자리는 땅에 닿아야 한다.비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각.. 2025. 2. 22. [Coding Test][Python][백준] BOJ #1446 지름길 문제)매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다.어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.세준이가 운전해야 하는 거리의 최솟값을 출력하시오.입력)첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.출력)세준이가 운전해야하는 거리의 .. 2025. 2. 21. [Coding Test][Python][백준] BOJ #20922 겹치는 건 싫어 문제)홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K$K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. $100\,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다. 이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.입력)첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.둘째 줄에는${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)출력)조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.. 2025. 2. 21. [Coding Test][Python][백준] BOJ #2075 N번째 큰 수 문제)N×N의 표에 수 $N^2$개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.127915513811196211026311648142835255220324149 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.입력)첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.출력)첫째 줄에 N번째 큰 수를 출력한다.풀이)※ 풀이 아이디어$N \le1500$ 이므로 $N^2$의 Matrix는 $1500 \times 1500 \times 4 .. 2025. 2. 21. 이전 1 2 3 4 다음 반응형
