목록알고리즘 (153)

땀두 블로그

[백준] 6064번 - 카잉 달력

x와 y값 중 한 가지를 잡고 그 나머지에다가 M 또는 N값을 더한게 다른 변수의 나머지와 같으면 되게 하는 문제이다. 처음에는 M*N을 탐색하여 시간초과가 나서 최적의 값을 구하기 위해서 M과 N의 최소공배수를 구해 그 값까지만 탐색하여 문제를 해결하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p6064 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedRe..
알고리즘/백준 2022. 3. 23. 08:00
[백준] 1992번 - 쿼드트리

분할정복(Divide & Conquer)기법을 사용한 문제이다. https://ddamdoo.tistory.com/157 [백준] 2630번 - 색종이 만들기 대표사진 삭제 사진 편집 작게작게문서 너비문서 너비옆트임옆트임 삭제삭제 사진 설명을 입력하세요. 대표사진 삭제 사진 설명을 입력하세요. 대표사진 삭제 사진 설명을 입력하세요. 처음으 ddamdoo.tistory.com 위 링크의 문제와 비슷하게 풀이하면 된다. 배열에 입력된 값이 모두 통일된 값이 없으면 1/4단위로 쪼개어 모두 통일 된 값이 나오도록 하는 문제이다. 수식에서 쪼개는 함수를 실행하기 전에 결과를 출력할 문자열에 괄호를 열고, 함수를 모두 실행한 이후에 괄호를 닫는 것을 추가해주어 결과를 만들었다. import java.io.Buff..
알고리즘/백준 2022. 3. 23. 07:59
[백준] 7569번 - 토마토

https://ddamdoo.tistory.com/167 [백준] 7576번 - 토마토 BFS를 이용한 탐색문제이다. 이 문제의 경우, 기존에는 각 좌표에 해당하는 visited 배열을 통해서 방문 여부를 판단하였는데, 그렇게 하지 않고 다음 좌표를 방문할 때, count값을 1 증가시키는 방식 ddamdoo.tistory.com 위 링크에 있는 토마토가 X * Y의 배열이었다면 이번엔 X*Y*Z로 3차원으로 증가를 한 문제이다. 문제자체는 같은 방식으로 해결하지만, 3차원이라 인덱스를 잡는 부분에서 헷갈려 오래걸린것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j..
알고리즘/백준 2022. 3. 23. 07:58
[백준] 11656번 - 접미사 배열

단순하게 substring을 이용하여 각각의 string을 list에 저장하고, Collections의 sort 기능을 이용하여서 정렬한 값을 출력해주었다. Arrays.sort의 경우 퀵소트기반으로 worst case의 경우 시간복잡도가 O(N^2)이 되지만 Collections.sort는 머지소트 기반이므로 worst case 여도 O(NlogN)이 걸린다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class p11656 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc =..
알고리즘/백준 2022. 3. 23. 07:55
FloydWashall 알고리즘

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다. 이 알고리즘의 핵심은 '거쳐가는 정점'을 기준으로 판단하는 것이다. 쉽게 말해 i->j로 이동 시 i->k->j의 방식이 가능한지에 대한 판단을 하는 것이다. 이 알고리즘은 3중 for문을 이용하여 시간복잡도는 O(N^3)으로 비교적 속도가 오래걸리지만 input의 범위가 작은 경우 쉽게 문제를 해결할 수 있는 알고리즘이다. import java.util.Scanner; public class floydWarshall { static int INF = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in..
알고리즘 2022. 3. 23. 07:52
Prev 1 2 3 4 5 6 7 ··· 31 Next