꼼개의 개발자취

문제 : https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제설명 BFS 와 객체 비교, PQ와 queue를 사용한다. 복잡한 문제여서 잘 읽어보며 꼼꼼히 코딩해야한다. 알고리즘 1. 우선순위를 compareTo를 이용하여 설정한다. 현재 위치를 queue에 넣고 BFS 실행 2. 먹이를 먹으면 PQ에 넣는다. 이떄 먹이를 먹을 때 까지의 최소시간 min을 이용해서 최소시간에 먹이를 먹은 애들만 PQ에 넣는다. -> queue 비워짐..

문제 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제설명 1. BFS, DFS, Prim, Kruskal 등 다양한 알고리즘이 사용된다. 2. 문제를 잘 분석하고 하나하나 디버깅하며 해결한다. 알고리즘 1. BFS와 DFS를 사용하여 labeling 후 labeling 한 구역을 하나의 정점이라 생각한다. 2. 정점 사이의 거리를 PQ에 넣어준다. 3. PQ와 Union-Find를 이용하여 Kruskal 알고리즘을..

문제 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어 www.acmicpc.net 문제설명 이분 그래프 문제이다. 이분그래프 문제는 BFS로 구현하는 것이 정석이다. 알고리즘 1. 삽입 삭제가 빈번하면 Li..

문제 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 알고리즘 1. 한방향 그래프를 인접 리스트로 연결하고 도착점에 count를 증가시킨다. 2. count가 0이면 가장 앞자리거나 정보가 없는 정점이기에 큐에 넣는다. ->정보에 나오지 않은 학생은 어디에 있어도 순서가 만족한다. 3. 큐가 빌 때 까지 poll 하면서 나온 정점이랑 이어진 간선을 제거한다. 주의사항 1..

서론 우선순위 큐는 알고리즘 풀 때 자주 쓰이는 자료구조 중 하나이다. 우선순위 큐의 장점은 offer를 하면 큐 내에서 Sort를 해준다. Sort의 기준은 defalut가 값 하나에 대한 오름차순이다. 그러나 대부분 문제들이 우선순위 큐에 객체로 들어가기 때문에 CompareTo를 Overriding 하여 Sort의 기준을 잡아준다. 구현 코드 ///////////////////////객체 생성 후 CompareTo 재정의/////////////////////// class road implements Comparable{ int y; int x; int value; public road(int y, int x, int value) { super(); this.y = y; this.x = x; thi..