문제풀이
-
[백준]2056: 작업 - JAVA문제풀이/백준 2021. 4. 30. 15:34
[백준]2056: 작업 풀이 선행 관계에 맞추어 모든 작업을 완료하는 시간을 구하는 위상정렬 문제였다. 오랜만에 푸는 위상정렬 문제여서 중간에 조금 헤메며 풀었다. 문제 난이도는 어렵지 않은 수준의 위상정렬 문제였다. 위상정렬 알고리즘을 사용하여 모든 노드를 선행 관계에 맞추어 작업을 마무리 할 수 있는 최소 시간을 구해주었다. 각각 구한 최소시간에서 가장 큰 값을 선택하면 그 값이 모든 작업을 완료 했을 때의 시간이 되므로 반복문을 사용하여 가장 큰 값을 찾아주었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 4..
-
[백준]10282: 해킹 - JAVA문제풀이/백준 2021. 4. 29. 17:41
[백준]10282: 해킹 www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 서로 의존성을 가지고 연결된 컴퓨터들 끼리 전염이 되는데 최대 전염 컴퓨터의 수와 전염될 수 있는 컴퓨터가 모두 전염되었을 때의 시간을 반환하는 문제이다. 첫 시작 컴퓨터를 기준으로 다른 모든 컴퓨터가 전염되는 시간을 구하는 문제임으로 다익스트라 알고리즘을 사용하여 문제를 풀었당. 다익스트라 알고리즘을 실행한 후 dist함수에서 Integer.MAX_VALUE값이 아닌 값 중 최대 값..
-
[백준]4358: 생태학 - JAVA문제풀이/백준 2021. 4. 29. 15:39
[백준]4358: 생태학 www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 풀이 자료구조 관련된 문제로 HashMap을 사용해서 풀었다. HashMap으로 문자열을 입력받고, 해당 문자열이 총 몇번 입력되었는지를 key와 value쌍으로 저장해 주었다. 그 다음에 key값만을 배열로 만들어 오름차순 정렬한 후 조건에 맞게 계산해 주었다. 이번 문제를 풀면서 key값만을 가져올 수 있는 방법을 알게 되었다. 아래와 같이 KeySet().toArray(..
-
[백준]6416: 트리인가? - JAVA문제풀이/백준 2021. 4. 28. 19:04
[백준]6416: 트리인가? www.acmicpc.net/problem/6416 6416번: 트리인가? 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. www.acmicpc.net 풀이 간선에 대한 정보를 입력 받아 해당 간선과 정점으로 만들 수 있는 그래프가 트리인지 판별하는 문제였다. 트리인지 판별하는 과정은 다음과 같다. 루트가 하나여야 한다. 루트를 제외한 모든 노드들의 진입 간선은 한개여야 한다. 정점의 개수 - 1 == 간선의 개수여야 한다. 정점의 개수를 중복 없이 세 주기 위해 HashMap을 사용하였다. key값을 정점 값으로, value값을 진입..
-
[백준]1202: 보석 도둑 - JAVA문제풀이/백준 2021. 4. 27. 18:53
[백준]1202: 보석 도둑 www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선순위 큐를 사용한 문제로 굉장히 재미있게 느껴졌던 문제였다. 이 문제는 쉽게 생각하면 쉽게 풀 수는 있지만 시간복잡도에서 통과하기가 쉽지 않은 문제였다. 처음에는 우선순위큐를 사용하여 정렬을 통해 쉽게 풀 수 있을 것이라 생각했지만 역시나 시간 초과가 발생했다. 우선순위 큐를 두개를 만들어서 꺼내고 집어넣고를 반복..
-
[백준]1655: 가운데를 말해요 - JAVA문제풀이/백준 2021. 4. 27. 15:24
[백준]1655: 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 처음에는 우선순위큐를 사용해서 풀려다가 우선순위큐의 메소드 중에서는 인덱스로 접근할 수 있는 메소드가 없어 ArrayList로 접근하였다. list에 숫자를 입력받아 넣어주고 정렬 후에 2로나눈 인덱스 값을 출력하도록 하였더니 시간초과가 발생하였다. 다시 우선순위큐로 접근을 시도하였으나 마땅한 해결방법이 떠오르지 않았다. 다른 분들의 풀이를 확인하면서 정말..
-
[백준]4386: 별자리 만들기 - JAVA문제풀이/백준 2021. 4. 26. 19:04
[백준]4386: 별자리 만들기 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 별들의 좌표를 간선으로 이었을때 최소인 비용을 찾는 문제로 MST알고리즘을 사용하여 풀면 된다. 별을 입력받을때 해당 별의 번호와 좌표를 저장해 주었다. 이 문제에서는 별들이 연결된 간선의 정보가 없으므로 모든 별들 사이의 거리를 직접 구하여 간선list에 저장해 주었다. 그다음 MST알고리즘인 prim, kruskal알고리즘을 사용하여 각각의 MST를 구해주면 된다. 코드 ..
-
[백준]2096: 내려가기 - JAVA문제풀이/백준 2021. 4. 26. 15:09
[백준]2096: 내려가기 www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 DP문제로 프로그래머스의 '정수 삼각형'문제와 매우 유사하다. 정수 삼각형은 최대값만 찾았다면 이번 문제는 최대, 최소값을 모두 찾는 문제이다. 합을 누적시킬때 최대값을 누적시키는 maxDp, 최솟값을 누적시키는 minDp배열을 만들어 주었다. 이때 한 줄당 총 3개의 숫자가 올 수 있으므로 3개의 경우로 나누어서 누적시켜주었다. 각각의 위치에서 누적시킬 인덱스는 다음과 같다. 현재 인덱스가 ..