끄적끄적 코딩
article thumbnail
[Java] 백준 18188번 다오의 데이트
알고리즘 2023. 7. 12. 12:28

브루트포스 문제입니다. 다오가 디지니가 있는 위치까지 가는데 이동한 방향과 가능여부를 출력하면 됩니다. 이동 방향은 각 이동마다 2가지로 주어집니다. DFS로 2가지 경우 모두 탐색하여서 가능한지 여부를 찾았습니다. 가능한 경우 결과배열에 이동경로를 저장하면서 재귀함수를 탈출했습니다. 가능한지 여부를 출력하고 결과배열에 있는 값을 출력해주었습니다. import java.util.*; import java.io.*; public class Main { static int n; static int m; static int moveCnt; static int sy, sx; static int ey, ex; static int[][] map; static int[][] move; static String res..

article thumbnail
[Java] 백준 24884번 장작 넣기
알고리즘 2023. 7. 12. 01:50

브루트포스 문제입니다. 규칙에 맞게 장작을 넣어서 K개의 모닥불을 유지 시킬 수 있는 경우의 수를 구해야합니다. 현재 위치에서 [-1, 0, 1] 위치의 장작을 넣을 수 있습니다. 장작을 넣을 경우 해당 위치 1시간 동안 불이 줄어들지 않습니다. 화력 감소는 아래와 같습니다. 인접한 2곳에 불이 켜져있으면 -1 인접한 1곳에 불이 켜져있으면 -2 인접한 곳에 불이 없으면 -3 순서는 화력감소가 된 후에 장작 넣기가 진행됩니다. => 첫번째 시간에는 아직 장작을 넣은 것이 없기 때문에 모든곳에서 화력감소가 일어납니다. 진행 순서 1-1 현재 T시간 인 경우 경우의 수 +1, 4번으로 1-2 현재 T시간이 아닌 경우 2번으로 2. 화력감소 3. 꺼진 개수 세기 4. [-1, 0, 1]에 장작넣기 -> 1번으..

article thumbnail
[Java] 백준 2110번 공유기 설치
알고리즘 2023. 7. 11. 00:14

이분 탐색 문제입니다. N개의 집에 C개의 공유기를 설치하여 인접한 두 공유기 사이의 최대로 하여야 합니다. 먼저 정렬을 해주어서 공유기의 위치를 차례대로 나열해줍니다. 인접한 공유기와 거리를 배열에 저장합니다. 이분 탐색을 통해 0~1,000,000,000의 값들 중 가능한 값들을 찾아나갑니다. 1. 가능 한 경우 더 높은 경우가 있는지 확인하기 위해서 left = mid + 1 2. 불가능 한 경우 가능한 경우를 찾기 위해서 right = mid - 1 위의 과정을 left > right가 될 때까지 반복해줍니다. 위의 과정에서 가장 큰 값을 출력해줍니다. import java.util.*; import java.io.*; public class Main { static int result; stat..

article thumbnail
[Java] 백준 1916번 최소비용 구하기
알고리즘 2023. 7. 7. 15:43

다익스트라 문제입니다. 시작위치에서 도착위치까지 최소비용을 구해야합니다. 우선순위 큐를 활용해서 다익스트라 알고리즘을 구현해주었습니다. pq(우선순위큐)에서 값을 뽑아냅니다. pq는 인덱스와 가중치 정보를 가지고 있습니다. 가중치가 낮은 순으로 차례대로 정점들을 뽑아냅니다. 해당 정점들에서 이동가능한 곳들의 가중치를 구합니다. 해당 정점의 가중치 > 이전 위치의 가중치 + 해당 정점까지의 비용 위의 비용을 비교해서 true라면 값을 갱신해주고 pq에 넣어줍니다. 위의 과정을 반복해서 간선들을 갱신해주고 도착지의 cost를 출력해줍니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader;..

article thumbnail
[Java] 백준 11404번 플로이드
알고리즘 2023. 7. 7. 11:45

플로이드 문제입니다. 모든 도시에 가는 최소비용을 구해야합니다. 모든 경로의 비용을 최댓값으로 넣어주고 시작했습니다. A->B를 가는 경우 A->C->B를 가는 경우와 비교해서 더욱 빠른 경로로 갱신해주었습니다. 모든 경우에 대해서 갱신을 해주고 결과값을 출력해주었습니다. 주의할점은 초기값이거나 i와 j가 같은경우 0으로 처리해주었습니다. 플로이드 알고리즘은 O(n^3)의 시간복잡도를 가집니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public cla..

article thumbnail
[Java] 백준 12931번 두 배 더하기
알고리즘 2023. 7. 6. 17:54

그리디 문제입니다. 0으로 이루어진 A배열과 값이 있는 B배열이 주어집니다. 규칙에 따라 B배열을 만들 때 최소 횟수를 출력해야합니다. 1. A배열에서 하나의 값을 1 올린다. 2. A배열 전체에 2를 곱한다. 경우의 수가 많아 보이지만 그리디로 처리할 수 있습니다. 각 값을 기준으로 0을 만들때 1번과 2번을 몇번 사용해야하는지 구해줍니다. 2로 나눌 수 있는 경우 2로 나누어주고 2번 사용에 대해서 카운팅 해줍니다. 2로 나눌 수 없는 경우 1을 빼주고 1번 사용에 대해서 카운팅 해줍니다. 그러면 각 값을 최소한으로 만들 수 있느 수가 나옵니다. 곱셈의 경우 (2번 경우) 모두 같이 사용할 수 있으므로 각 값들에 대해서 최대로 많이 사용한 값만 있으면 됩니다. 덧셈의 경우 (1번 경우) 각자 사용하므..

article thumbnail
[Java] 백준 17140번 이차원 배열과 연산
알고리즘 2023. 7. 6. 16:51

시뮬레이션 문제입니다. R연산 - 행의 개수가 열의 개수보다 크거나 같은 경우 C연산 - 열의 개수가 행의 개수보다 큰 경우 R연산은 행에 대하여 정렬을 진행합니다. C연산은 열에 대하여 정렬을 진행합니다. 정렬을 예로들면 각 수의 개수를 구합니다. 1 2 1 => 숫자 1이 2개 / 숫자 2가 1개 오름차순으로 개수를 기준으로 정렬 해줍니다. 숫자 2가 1개, 숫자 1이 2개 => 2 1 1 2 R연산이었다면 모든 행에 위의 정렬을 해줍니다. 모든 연산이 끝나고 행의 길이를 갱신해줍니다. 행과 열의 길이를 비교해서 R연산 C연산을 진행합니다. 시간이 100초가 넘어가거나, 값을 찾으면 종료합니다. import java.io.BufferedReader; import java.io.BufferedWrite..

article thumbnail
[Java] 백준 12946번 육각 보드
알고리즘 2023. 7. 6. 00:56

브루트포스 문제입니다. 육각보드의 일부분을 색칠하려고 합니다. 이 때 인접한 곳과 색이 같지않게 했을 때 최소의 색의 수를 구해야합니다. 육각보드에 모두 색을 칠할 경우 3개의 색만 있으면 모두 칠할 수 있습니다. 이것을 활용해서 DFS로 문제를 풀었습니다. ex) 0 = X색, 1 = Y색 처음에 0을 넣고 다음번엔 1을 넣는 방식으로 반복합니다. 이 때 매번 인접한 칸을 확인하는데 현재 넣을 값과 같은곳이 있다면 3번째 색을 넣는 경우로 판단하였습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public cl..

검색 태그