본문 바로가기

Algorithm65

[백준] 14503번 로봇 청소기 자바 문제 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 풀이 문제 자체를 이해하기 어려워서 구글링을 했다. 왼쪽 방향으로 돌면서 빈칸일 경우 해당 칸으로 이동하고 그 칸에서 다시 인접칸을 확인한다. 모두 청소했거나 벽이여서 갈 수 없을 경우는 현재 방향 기준 뒤를 확인해서 후진할 수 있는 경우에 후진하고, 벽이 있다면 그대로 작동을 멈춘다. dfs로 해당 문제에 나온 알고리즘 그대로 코드를 짰다. 일단 나는 현재 방향에서 왼쪽으로 이동하고 바라보는 방향도 바꾸는 코드는 다음과 같은 2차원 배열을 이용해서 .. 2022. 5. 24.
[백준] 2263번 트리의 순회 자바 문제 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 풀이 감을 못잡겠어서 구글링했고, 분할 정복문제였다. inorder(중위순회)를 통해 루트노드에서 갈라지는 왼쪽/오른쪽 서브트리를 알아낼 수 있고 postorder(후위순회)를 통해 루트노드를 알아낼 수 있다. 간단한 예시를 통해 해보면 금방 알 수 있다. 따라서 알고리즘은 간단한데, 구현하는 게 꽤 어려웠다. 소스 코드 public class b_2263 { static int[] inorder, postorder, preorder; static int idx = 0; pub.. 2022. 5. 23.
[백준] 15900번 나무 탈출 자바 문제 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 문제 풀이 ArrayList를 이용하여 트리를 만들고 dfs로 순회했다. 성원이가 이기려면 리프노드에서 루트노드까지 게임말을 옮길 때 홀수가 되어야 이길 수 있다. 하지만 짝수여도 다른 루트에서 또 짝수가 존재하면 그 루트의 말을 옮기면 되므로 이길 수 있다. 따라서 루트노드에서 리프노드까지의 각각의 루트 거리의 총합이 홀수이면 성원이는 이길 수 있다. 처음에 visited[]배열을 int형으로 받아서 방문표시와 해당 노드까지의 거리 합을 누적하면서 답을 구.. 2022. 5. 19.
[백준] 2437번 저울 자바 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 풀이 구글링해서 풀었다. 논리 생각하기가 어려웠던 것 같다. 문제 예시로 알고리즘을 설명해보자면 우선 주어진 배열 [3, 1, 6 2, 7, 30, 1]을 정렬한다. → 작은 수부터 만들 수 있는 숫자를 찾기 위해서 정렬된 배열 A = [1, 1, 2, 3, 6, 7, 30], 배열 B를 A로 만들 수 있는 숫자 배열이라고 들겠다. A를 처음부터 반복하면서 B배열을 확인해보면 A[0]: 1로 만들 수 있는 숫자 B= {1} A[1]: 1 추가로 만들 수 있는 숫.. 2022. 5. 6.
[백준] 1213번 팰린드롬 만들기 자바 문제 2022. 4. 29.
[백준] 1292번 쉽게 푸는 문제 자바 문제 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 문제 풀이 처음에는 반복문으로 B까지의 배열을 생성해서 그냥 더해야 하나 싶었는데 뭔가 비효율적인 것 같아서 인덱스를 이용해서 풀었다. 아래와 같이 1+2+3.. 이런식으로 더해나갈 때 그 수의 마지막 인덱스 번호가 되는 것을 이용했다. 인덱스 구간 안에 A와 B가 포함될 때, 해당 숫자 값을 곱해서 answer변수에 넣어줬다. 해당 숫자 구간 안에 들어왔으면 그때의 더해진 인덱스(해당 숫자의 마지막 인덱스 번호)에서 A값을 빼면 해당 숫자를 몇 개 더해야 하는지 알 수 있다. .. 2022. 4. 25.

티스토리툴바