본문 바로가기

알고리즘 풀이/백준

 (48)
[백준] 7576번: 토마토 - JAVA 🔗 문제 링크 BOJ 7576번: 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📝 풀이 과정 익은 토마토가 주변의 앞, 뒤, 왼쪽, 오른쪽 4방향의 안익은 토마토를 익게 만드는 총 일수를 구하는 문제이다. 전형적인 BFS 문제의 구조를 띄고 있다. 처음 입력을 받으며 익은 토마토는 Queue에 넣는다.나의 경우 Queue에 int[] 배열로 토마토의 위치를 저장하였다. 마지막에 안익은 토마토가 존재할 경우 -1을 출력하는 조건 존재하기 때문에 이를 처리하기 위해 안익은 토마토가 등장..
[백준] 5525번: IOIOI - JAVA 🔗 문제 링크 BOJ 5525번: IOIOI 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 📝 풀이 과정 문제에서 핵심은 $P_N$에서 O는 N개만큼 들어있다는 점이다. 따라서, 현재 칸까지 'OI'가 몇 개 반복되었는지 누적하도록 하였다. 예를 들어, N = 1, S = OOIOIIOII인 경우를 살펴보자. 위와 같이 arr = M.toCharArray()이고, memo는 'OI'의 누적 갯수를 저장할 배열들이고, ans는 $P_N$이 몇 개 들어가는지 저장할 변수이다. i = 1일 경우, arr[i + 1]의 값이 'I'이므로 m..
[백준] 6064번: 카잉 달력 - JAVA 문제 링크 BOJ 6064번: 카잉 달력 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 풀이 과정 아 문제의 핵심은 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 예를 들어, # 일 때 1번째 해 : 2번째 해 : ... 10번째 해 : 11번째 해 : 12번째 해 : 13번째 해 : 이 처럼 x가 M, y가 N에 도달할 경우 1로 변경된다는 것이다. 단순히 하나씩 계산하며 만족하는 결과를..
[백준] 5430번: AC - JAVA 문제 링크 BOJ 5430번: AC 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 과정 명령어가 R이면 배열 전체를 뒤집고, D라면 첫번째 인자를 삭제하기 때문에 전체 배열을 뒤집는 경우는 $O(N)$의 시간복잡도가 소요되기 때문에, 배열을 직접 뒤집는게 아닌 조건에 따라 앞과 뒤에서 삭제하는 방식을 사용하기로 했다. 때문에, 앞과 뒤에서 pop을 자유롭게 할 수 있는 Deque를 활용하기로 했다. 입력의 앞과 뒤에 붙은 괄호를 제거하기 위해 substring(1, str.length())를 활용해 앞뒤로 한 개씩 삭제해 주었고, split을 사용해 ','을..
[백준] 2667번: 단지번호 붙이기 - JAVA 문제 링크 BOJ 2667번: 단지번호 붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 풀이 과정 모든 지도를 돌며 연결되어 있는 1을 카운트하며 갯수를 세면 되기 때문에 BFS사용하기로 했다. 개인적으로 map을 처리할 때, int형보다 boolean이 처리하기 쉬워서 입력값을 1일 때 true, 0일 때 false로 바꾸어 저장하였다. 이중 반복문을 통해 map배열에 true가 있는지 탐색하고 만약 존재한다면 해당 칸부터 시작해 상하좌우를 탐색하며 queue에 넣으며 방문한 칸을 false로 변경하여 ..
[백준] 2630번: 색종이 만들기 - JAVA 문제 링크 BOJ 2630번: 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 과정 문제의 조건이 주어지고 만약 조건이 성립하지 않으면 분할하여 반복하는 구조 ⇒ 분할정복 시작점을 두고 시작점과 주어진 칸들의 값이 일치한다면 카운트, 아니라면 4분할 하는 방법으로 접근하였다 이 문제에서 핵심적인 부분은 divide함수 부분이다. 색종이의 길이를 n, 좌상단 시작점을 (y, x)로 변수명을 정하고 시작하였다. 만약 시작점과 종이의 칸의 숫자가 다르다면 분할을 해야하..
[백준] 2606번: 바이러스 - JAVA 문제 링크 BOJ 2606번: 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 과정 바이러스는 연결된 네트워크를 통해 모두 전파되므로 연결되어 있는 모든 경로를 탐색하면 되는 문제이다. DFS와 BFS 모두 가능하지만, 다른 문제를 풀면서 BFS를 더 많이 사용해서 이번에는 DFS를 사용해 문제를 풀어보기로 했다 dfs(int) 를 통해 방문한 노드를 넘겨주고, 만약 해당 노드를 방문했다면 return, 아니라면 연결된 노드를 다시 dfs로 탐색하였다. 방문한 노드의 visit값을 true로 변경하고..
[백준] 2579번: 계단 오르기 - JAVA 문제 링크 BOJ 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 과정 먼저 문제의 핵심은 1번과 2번 규칙이다 계단은 한 번에 한 계단, 두 계단씩만 오를 수 있다 연속된 3개의 계단을 밟으면 안된다 그렇다면, n번째의 계단을 밟는 경우는 몇 가지가 존재할까? n-3을 밟고 n-1번 계단을 밟고 오는 경우와 n-2번을 밟고 오는 경우 2가지가 존재한다. 연속해서 3개의 계단을 밟는 것은 불가능하기 때문에 이외의 경우는 존재하지 않는다. 또한, 조건을 고려하며 한칸을 무조건 뛰는 경우가 발생..

티스토리툴바