본문 바로가기

Algorithm/BOJ45

[백준] 5397번 키로거 자바 문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제 풀이 처음에 ArrayList와 idx변수 하나를 이용해서 list의 인덱스 번호를 옮겨가면서 값을 삽입하는 방법으로 진행을 했는데 시간초과가 떴다. 그래서 구글링해본 결과, Stack을 이용하는 방법과 ListIterator를 이용하는 방법 두 가지가 있었다. 두 가지 모두 풀이에 적용해 보았다. 먼저 ListIterator를 이용하는 방법은 기존 ArrayList에서 index를 바꿔나가는 방법과 로직을 동일하게 사용하고 사용 자료구조와 함.. 2022. 5. 31.
[백준] 14501번 퇴사 자바 문제 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 dp문제인건 바로 알았는데 dp를 너무 못해서 구글링하고서도 이해하는데 꽤 많은 시간이 걸렸다.. 우선 dp의 크기를 N+2 로 두었다. 왜냐하면 마지막 날(N일)까지 일한건 퇴사일(N+1일)에 돈을 받을 수 있으니까 N+1일까지 누적 수익값을 구하기 위해서다. dp[i]는 i일까지의 최대 이익을 저장해둔 것이다. 1일부터 N일까지 반복하면서 해당 날짜로부터 상담을 시작해 상담이 끝난 다음 날의 dp에 해당 수익을 저장한다. 이때 해당 dp에 이미 들어있는 값과 현재 dp[i]의 값 + 현재 날짜에 상담을 함으로써 얻을 수 있는 이익과 비교한다. dp[ i + T[i] ] = Math.. 2022. 5. 28.
[백준] 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.

티스토리툴바