본문 바로가기

Algorithm50

마법사 상어와 비바라기(BJ_G5_21610) 1. 문제 링크 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 나의 코드 메모리: 22864kb 시간: 264ms 코드 길이: 3527B 시간 복잡도 : O(M * N^2) 설명 - 모든 구름을 이동 - 이동한 좌표를 방문처리 - 이동한 곳을 기준으로 대간선으로 탐 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; .. 2024. 2. 24.
마법사 상어와 파이어볼(BJ_G4_20056) 1. 문제 링크 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 2. 나의 코드 메모리: 40540kb 시간: 732ms 코드 길이: 4868B 시간 복잡도 : O(KM) 설명 - 먼저 모든 파이어볼을 이동시킨 후 합치기 - 합치는 과정에서 다음 객체와 같은지 다른지 비교 - 시작과 끝 인덱스를 사용하여 같은 위치에 있는 것들은 인덱스 리스트에 추가(끝나면 삭제) - 추가해야 할 객체도 리스트에 추가 후 .. 2024. 2. 24.
다리 만들기 2(BJ_G1_17472) 1. 문제 링크 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 나의 코드 메모리: 14352kb 시간: 128ms 코드 길이: 5993B 시간 복잡도 : O(섬의갯수^2). 설명:먼저 DFS를 통해서 섬의 갯수를 알고, 섬의 번호를 부여한다. 그리고 조합 알고리즘을 사용하여 섬들간의 경우의 수를 구하고 BFS를 사용해서 섬들간의 최소거리를 구한다. 마지막으로 크루스칼 알고리즘을 사용하여 최소 간선의 합을 구한다. i.. 2024. 2. 22.
아기 상어(BJ_G3_16236) 1. 문제 링크 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 나의 코드 메모리: 26748kb 시간: 352ms 코드 길이: 2714B 시간 복잡도 : O(N^4) // BFS의 최악의 경우는 노드 수의 제곱 설명: BFS를 사용해서 모든 곳을 방문한다. 만약 상어가 먹을 수 있는 곳이라면 리스트에 추가한다. 모든 곳의 방문이 끝났으면 리스트를 정렬해서 첫 번째 자리의 값을 0으로 바꾸고 먹어 치운다. import java.ut.. 2024. 2. 21.

티스토리툴바