알고리즘/백준 Baekjoon19 백준 4963번 섬의 개수(JAVA) - DFS 백준 4963번 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제설명 섬과 바다 지도가 주어지는데, 섬의 개수를 세는 문제 - 가로, 세로, 대각선으로 연결되어 있으면 걸어갈 수 있다. - 지도의 너비 w와 h를 입력받는다. (행/렬 구분 주심) - w,h가 0 0 이 들어오기 전까지 계속 반복하며 0 0 이 들어오면 종료. 접근 DFS로 접근 (상하좌우, 대각선까지 정의) 코드 import java.io.BufferedReader; .. 2023. 5. 1. 백준 11659 구간 합 구하기 4(JAVA) - DP(Dynamic Programming) 백준 11659번 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제설명 첫째 줄에 N(숫자의 개수)과 M(반복할 횟수) 를 입력받아 진행 접근 처음엔 for문으로 풀어볼까 생각했지만 범위가 각 10만까지라 1초가 넘어 갈것같아 DP로 접근 각 구간까지의 합을 DP 배열에 저장해두고 i,j(구간의 시작과 끝) 을 입력받은 다음 dp[j]에서 dp[i-1]을 빼주면 된다. (dp[0]은 0을 넣어줌.) ex) 5 4 3 .. 2023. 4. 1. 백준 7562 나이트의 이동(JAVA) - BFS 백준 7562번 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제설명 체스판에서 나이트 (위의 그림처럼 대각선으로 이동가능함)가 몇번만에 이동가능한지 알아내는 문제 체스판의 변의 길이가 주어지고, 초기위치와 도착위치를 입력받는다. 접근 BFS로 접근 ( 기본이 상하좌우 라면 이 문제는 좌표를 각각 대각선에 맞춰 설정) 코드 import java.io.BufferedReader; import java.io.IOException; import j.. 2023. 3. 25. 백준 10026 적록색약(JAVA) - BFS 백준 10026번 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제설명 적록색약이 아닌사람(A) 적록색약인 사람(B)과 이 봤을때의 그림의 그룹의 개수를 나누는 문제 A는 R,G,B 각각의 그룹을 나눌수 있지만 B는 R,G가 같게 보인다는 가정. 접근 BFS로 접근 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;.. 2023. 3. 25. 이전 1 2 3 4 5 다음
