본문 바로가기

전체 글96

[백준] 4195번 친구 네트워크 자바 문제 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 풀이 HashMap을 이용하여 친구의 이름을 숫자로 표현해야 배열 인덱스를 이용할 수 있다. 그리고 union-find함수를 이용하여 두 친구 관계의 집합 크기를 늘려간다. 이때 연결 노드를 저장할 부모 배열외에 몇개가 연결되어있는지 누적하기 위해 count 정수형 배열을 하나 더 사용해준다. count배열에는 처음에 모두 1로 초기화해주고 해당 원소가 다른 원소로 합쳐질 때(부모값이 변경될 때) count값을 해당 원소의 최상위 부모 co.. 2022. 6. 8.
[백준] 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.