알고리즘,PS

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 풀이 처음에 PriorityQueue를 쓰다가 33%쯤에서 틀렸다고 나왔다. 힙 구조특성상 맨 앞에있는 원소만 순서를 보장해줘서 그런 것 같다. 결론은 LinkedList 큐 에서 하나 뽑은 다음 , 더 높은 중요도의 문서가 있다면 그냥 큐의 뒤로 보내는 것이 가장 정석적인 방법일 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

https://www.acmicpc.net/problem/16197 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 동전 위치를 나타내는 Point 객체와 두 동전을 담고 움직이는 횟수를 나타내는 Move 객체를 생성 2. 우선순위큐를 이용하여 횟수가 적은 순서대로 처리 3. isRange(x,y) 로 범위를 벗어나는 조건을 이용해서 둘 중 하나만 떨어지는 경우를 체크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 문제 풀이 이 문제에서 내가 집은 포인트는 3 가지이다. 1. 우선 순위 큐를 이용하여 최대한 시간이 덜 걸리는 순으로 처리하는 것 (우선순위큐 bfs 다익스트라 이용) 2. dp배열을 이용해서 이미 왔던 곳이면 break를 거는 것 3. 이중 for 문을 이용해서 nextX,nextY를 정할 때 , 1부터~k까지 이동가능한 모든 경우를 큐에 넣는 것 1 2 3 4 5 6 7 8 9 1..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 풀이 전형적인 dp문제이다. 우선 단순 노가다로 풀어보다가 3번쨰마다 규칙이 있을거라는 추측을해본다. 두번째마다 1씩 올라가는 걸 확인 할 수 있다. 이걸 점화식으로 세우면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*; imp..

문제 풀이 1. 이 문제는 bfs와 같은 일반적인 그래프 탐색으로 접근하면 시간초과가 나버린다.. -> dp 문제 2. 경로의 개수는 263-1보다 작거나 같으므로 dp의 자료형을 long으로 선언 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main{ static int N; static int[][] map; static long[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = ..

문제 풀이 1. dfs 탐색으로 같은 문자인 경우에만 진행하도록 함2. dfs 호출될때 마다 cnt 카운트 수 1씩 증가3. 한 무더기(?) dfs 탐색 끝났을 때 , 그 진영무리의 위력값 cnt*cnt 을 합산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 import java.util.*; import java.io.*; public class Main{ static int w,h,cnt,white,blue; static char[][] map;..

문제 풀이 이 문제는 재귀적 완전탐색(DFS) + 백트래킹 문제이다.연산자를 차례대로 방문하면서 끼워넣어 완전한 식과 그에대한 total 값을 낸 다음 , 사용하였던 연산자 개수를 회복하면서 다른 순서 방식을 통해 다시 반복하는 식으로 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 import java.util.*; import java.io.*; public class Main{ static int N; static int[] arr; st..

문제 풀이 전형적인 크루스칼 알고리즘 풀이다. 1. Edge의 weight크기가 작은 순으로 정렬 2. Edge를 집합에 포함 시키기위해 find(x) 함수를 호출해서 parent가 같은지 확인 3. Parent가 같지 않은 Edge 한에서 Union을 호출하여 집합에 포함시킨 후 가중치 합을 반환 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.util.*; import java.io.*; class Solution{ static int[] parent; static ArrayLi..