Algorithm

Coding Test(Kruskal Algorithm)

최소 신장 트리(MST : Minunum Spanning Tree) 신장 트리(Spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 신장 트리(Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않은 부분 그래프 정점이 N개인 무방향 그래프에서 나올 수 있는 최대 간선의 수 : N(N-1)/2 정점이 N개인 방향 그래프에서 나올 수 있는 최대 간선의 수 : N(N-1) 크루스칼 알고리즘(Kruskal Algorithm) O(ElogE) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 = 최소 신장 트리를 만들기 위한 알고리즘 그리디 알고리즘(결정의 순간..

백준 17135 캐슬 디펜스(구현, 조합, BFS) ★★

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 단순 구현 문제인 줄 알고 쉽게 접근했지만 다양한 알고리즘을 사용해야 했던 문제였다. 1. 궁수의 위치를 정해야 하기 때문에 Combination 사용 2. 궁수가 공격을 해야하는데 동일한 거리의 적이 여러명 있으면 가장 왼쪽인 적을 죽인다 => BFS를 통해 가장 가까운거리를 탐색하고 방향벡터를 [좌 상 우] 방향으로 탐색함으로써 가장 가까운 애들 중 가장 왼쪽에 있는 적을 탐색하게 만든다 why?) 만약..

백준 1826 연료 채우기(우선순위 큐, 그리디)★★

https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 주유소에 최대한 적게 가야한다는 것을 보고 그리디적으로 접근해야됨을 알았다. 어떻게 하면 최대한 적게 갈 수 있을까? 내가 보유한 P만큼 앞으로 나갈 수 있는데 P만큼 전진 했을 때 만약 도착지점에 가지 못했다면 지나친 주유소들 중 연료를 가장 많이 주는 곳에서 채우는게 가장 이득이지 않겠는가?! ==> Max-Heap 거리는 1,000,000이기 때문에 크기..

백준 최소 회의실 개수(우선순위 큐, 그리디)★★

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 매우 어려운 문제였지만 원리를 이해한다면 쉽다. > 접근방법 우리는 회의실을 가장 적게 쓰고 싶어한다. 주어지는 입력은 무작위로 들어올텐데 문제를 읽어보면 진행되는 회의의 종료시간과 다음 회의 시작시간의 상관관계가 가장 중요하다는 것은 알 수 있다. 즉, 회의 데이터들의 입력을 받고 시작시간 기준으로 정렬해줄 필요가 있다. why?) 그래야 순차적으로 회의실을 늘릴지말지 판별할 수 있지 않..

백준 17406 배열 돌리기4(구현)

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 1. 배열에 대해서 permutation을 돌리는 기법이 자바에서 구현하기 많이 힘들었다. ==> row에 대한 인덱스들만 따로 모은 1차원 배열을 permutation 돌리는 기법으로 하는게 정석인 것 같음 2. rotation 시키는 방법 2-1. (in java) list에 넣고 Collections.rotate() 2-1-1 (in python) queue.r..

백준 16206 롤케이크(그리디)

https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 문제를 읽고 그리디적으로 푸는 것이라고 생각했다. 무조껀 10의 케이크만 먹을 수 있기 때문에 10으로 나눈 몫과 나머지에 집중을 하기 시작했다. 규칙을 찾아보니까 1. x에 대해 10으로 나눈 나머지가 있을 경우 x//10번 자르면 x//10개의 10길이 조각이 나온다. 2. x에 대해 10으로 나눈 나머지가 없을 경우 x//10 -1번 자르면 x//10개의 10길이 조각이 나온다...