본문 바로가기

Algorithm/BOJ42

[백준] 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.
[백준] 2461번 대표 선수 자바 문제 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 문제 풀이 학급 대표선수 간 최대 최소 차가 최소가 되기위해서는 최대한 비슷한 값끼리 묶여있어야 하므로 모든 학생들을 학급 표시만 해둔 채로 정렬시켰다. 그리고 두 개의 인덱스 변수로 첫번째 선수를 마킹해두고, 뒤로 가면서 모든 학급이 다 찰때까지 두번 째 인덱스를 증가시켜 나갔다. 그 때의 최솟값을 갱신하면서 첫번째 인덱스를 증가하면서 나갔는데 시간초과가 떴다. 이를 개선하기 위해서 한 학급에서 나온 대표선수를 표시해두기 위해 boolea.. 2022. 4. 25.

티스토리툴바