알고리즘/BJ

[BJ] 백준 15591 MooTube (Silver) (JAVA)

문제 https://www.acmicpc.net/problem/15591 풀이 방법 이 문제는 시간초과가 관건인 문제였다. 처음에는 인접 행렬로 풀이를 하려고 했는데 계속해서 시간초과가 발생했다. 그래서 도저히 시간을 단축시킬 방법이 생각이 안나서 찾아봤더니 인접 리스트를 사용하면 풀리는 문제였다. 풀이 과정은 다음과 같다. 1. 인접 리스트를 생성해서 인접한 정점들과 USADO 값을 저장해준다. 2. v번째 정점으로부터 BFS를 시작한다. 3. queue에서 poll를 한 정점(n)과 인접하고(USADO값이 존재) 방문하지 않은 정점들만 탐색 후보가 된다. 4. n번 정점과 탐색 후보 사이의 USADO 값이 k이상인 경우에만 que에 넣어준다. 5. 그리고 cnt도 하나 증가해준다. 왜냐면 visit배..

[BJ] 백준 16954 움직이는 미로 탈출 (JAVA)

문제 https://www.acmicpc.net/problem/16954 풀이 방법 가장 왼쪽 하단에서 가장 오른쪽 상단으로이동하면 되는 문제이다. 대신에 맵에는 벽이 존재하고 벽이 아래로 이동하는 조건이 걸려있다. 풀이 방법은 BFS로 풀이했다. 우선 이동 가능한 좌표들을 선언해주고(제자리 포함), 이동 가능한 구역으로 이동후 queue에 넣어준다. 그리고 방문배열을 체크해줘야하는데 제자리에 있는 경우도 있기 때문에 3차원 배열로 만들어서 마지막은 방향으로 방문 배열을 생성해줬다. 그리고 캐릭터 이동 -> 벽 이동이기 때문에 같은 횟수? 번째? 이동인 경우에는 한 번에 처리해주고 그 다음에 벽을 이동해줬다. 제출 코드 import java.io.*; import java.util.*; public cl..

[BJ] 백준 11047 동전 0 (JAVA)

문제 https://www.acmicpc.net/problem/11047 풀이 방법 대표적인 그리디 알고리즘 문제이다. 동전의 단위가 있고, 금액이 있을 때 금액을 만들 수 있는 동전의 최소 개수를 구하면 된다. 순서는 정렬을 하고 단위가 큰 순서대로 금액에서 차감하면 되는데 입력값이 오름차순으로 주어진다고 했으니까 따로 정렬하지 않고 뒤에서부터 금액을 차감해주는 식으로 구현했다. 그리고 몫이 없으면 점점 단위가 내려가고 동전이 0이 되는 경우 for문을 벗어날 수 있게 해줬다. 제출 코드 import java.io.*; public class BOJ_11047_동전0 { public static void main(String[] args) throws IOException { BufferedReader..

[BJ] 백준 21610 마법사 상어와 비바라기 (JAVA)

문제 https://www.acmicpc.net/problem/21610 풀이 방법 문제에 따라서 순서대로 차근차근 구현해갔다. 문제에서 주목해야할 점은 1. 구름이 이동할 때 범위에 신경써야 하는 것 2. 대각선 방향을 확인할때의 범위는 또 다르게 적용된다는 것 3. 한꺼번에 처리하려다가 오히려 잘못된 값이 나올 수 있다는 점 이 세가지인 듯 하다. 나는 구현하는 건 어렵지 않았지만 3번 때문에 디버깅하는데 조금 시간이 걸렸다. 그리고 격자도 그렇고, 방향도 그렇고 인덱스 1부터 시작하는걸 나는 0부터 시작하는 걸로 수정해서 구현했다. 전제적인 과정을 정리하면 다음과 같다. 1. 처음에 구름 생성해주기 2. M번 이동 실행하기 1) 모든 구름을 올바른 방향으로 이동 시키기 2) 물의 양 증가시키기 3)..

[BJ] 백준 20058 마법사 상어와 파이어스톰 (JAVA)

문제 https://www.acmicpc.net/problem/20058 풀이 방법 풀이 순서를 차분하게 정하고 코드로 구현만 한다면 생각보다 간단한 문제였다. 1. 우선 처음에 해야하는건 부분 격자로 나누고, 그 안에 있는 요소를 시계방향으로 회전 시켜준다. 2. 주변에 얼음이 없는 칸을 찾고, 만약 얼음이 없는 칸이 3개 미만이면 해당 위치의 얼음의 개수를 -1 해준다. 여기서 주의해야할 점이 얼음의 개수를 바로바로 업데이트해주면 안된다. 1 2 4 1 3 4 3 4 5 이런 형태에서 얼음을 제거할때 만약 얼음의 개수를 바로바로 적용을 시켜준다면 결과가 원하는대로 나오지 않는다. 만약 바로 적용시켜준다면 0 2 3 0 3 4 2 4 4 이런 형태가 될텐데 이렇게 하면 제대로 정답이 나오지 않고, 제대..

[BJ] 백준 2579 계단 오르기 (JAVA)

문제 https://www.acmicpc.net/problem/2579 풀이 방법 각 계단에는 점수가 있고, 계단을 밟으면 점수를 얻을 수 있다. 대신에 한번에 최대 두 칸까지만 오를 수 있고, 연속한 세개의 계단을 밟을 수 없다. 얻을 수 있는 최대 점수를 구하면 되는 문제다. dp를 사용해서 풀었다. dp[i]의 값은 i번째 계단은 밟는다는 것을 가정하고, i-1번째, i 번째 연속해서 밟는 경우와 i-2번째, i번째 한 칸 뛰어 넘고 밟는 경우 중에서 더 큰 점수를 가진 경우를 저장했다. 연속해서 밟는 경우는 연속 3개는 밟으면 안되기 때문에 dp[i-3]의 값을 더해줘야한다. 제출 코드 import java.io.*; public class BJ_2579_계단오르기 { public static v..

[BJ] 백준 2748 피보나치 수2 (JAVA)

문제 https://www.acmicpc.net/problem/2748 풀이 방법 피보나치 수의 기본 문제다. n을 입력하면 n번째 피보나치 수를 출력하는 간단한 문제다. 나는 dp를 사용했고 N까지 구해준 뒤 dp[N]을 출력해줬다. 제출 코드 import java.io.*; import java.util.*; public class BJ_2748_피보나치수2 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); long[] dp = new l..

[BJ] 백준 1003 피보나치 함수 (JAVA)

문제 https://www.acmicpc.net/problem/1003 풀이 방법 dp를 활용한 피보나치 관련된 문제다. 재귀호출을 사용해서 피보나치 수열을 구현할 때 0과 1을 호출하는 횟수를 출력해야한다. 그래서 dp배열은 [수][0과1호출수]을 담을 2차원 배열로 선언해줬다. 0일 때는 0호출 한번, 1일때는 1호출 한번이기 때문에 각각 1로 초기화해주고, 입력값의 최대값이 40이였기 때문에 나는 미리 40까지 다 구해주고, n에 따라서 출력해서 사용했다. 2부터 40까지 반복문을 돌리면서 i-1, i-2의 0과 1 호출 횟수를 더한 값을 각각 dp[n]에 저장해줬다. 그 이유는 재귀호출로 피보나치 수열을 구현했을때 처음부터 생각해보자. 그러면 f(2) = f(1) +f(0) 부터 시작할 것이다. ..

[BJ] 백준 1012 유기농 배추 (JAVA)

문제 https://www.acmicpc.net/problem/1012 풀이 방법​ 실버 레벨에 해당하는 문제로 배추의 위치가 주어지고, 인접해있는 배추를 탐색해서 몇개의 배추 구역이 있는지 개수를 구하면 되는 문제다. 4방탐색으로 모든 방향을 돌면서 배추가 존재하는지, 방문했는지의 여부를 판단해야하기 때문에 BFS알고리즘을 사용해서 구현했다. 우선 배추의 위치는 입력값을 토대로 1로 설정해줬다. 그리고 이제 땅을 모두 돌면서 배추가 존재하면서 아직 방문하지 않은 경우 새로운 구역을 발견한 것이기 때문에 구역의 수에 1를 추가해줬다. 인접해있는 배추들을 모두 찾아줘야하기 때문에 Queue를 사용해서 BFS를 구현해줬다. 4방탐색을 하면서 배추이면서 아직 방문하지 않는 칸이 있다면 큐에 추가해주고, 방문 ..