분류 전체보기
-
[백준]9662: N-Queen - JAVA문제풀이/백준 2021. 5. 2. 15:32
[백준]9662: N-Queen www.acmicpc.net/problem/96639663번: N-QueenN-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.www.acmicpc.net풀이프로그래머스에 있는 N-QUEEN문제와 동일한 문제이다. DP문제의 대표가 하노이의 탑이 있다면 순열 문제의 대표라고 할 수 있는 문제이다. 이전에 풀었던 적이 있지만 오래되어 다시 한번 풀어보았다. 다시 풀자니 역시 조금 헤메이는 부분이 있었다. 게다가 백준의 문제 설명이 부족한 것도 있다. 프로그래머스에는 문제 설명이 자세히 잘 되어 있으니 N-QUEEN문제는 프로그래머스에 푸는 것을 추천한다...
-
[백준]1717: 집합의 표현 - JAVA문제풀이/백준 2021. 5. 2. 14:48
[백준]1717: 집합의 표현 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 문제도 간결하고 읽어보면 알 수 있듯이 union-find문제이다. union-find는 MST의 Kruskal알고리즘에서도 사용되는 이론이므로 꼭 알고있자. 풀이도 간단하다. 0을 입력받으면 union, 1을 입력받으면 각 요소의 부모가 같은지 확인후 yes, no를 출력해주면 된다. union함수는 각 요소들의 부모를 같게 만들어 ..
-
[백준]2660: 회장뽑기 - JAVA문제풀이/백준 2021. 5. 1. 15:39
[백준]2660: 회장뽑기 www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 모든 회원 간의 관계를 조사한 다음에 그 중에 최대값을 찾아 회원 점수를 찾아낸 뒤, 그 중 최소값은 갖는 후보가 회장 후보가 된다. 즉, 모든 회원간의 관계(거리)를 알아야 하므로 플로이드-와샬 알고리즘을 사용하였다. friend[i][j]보다 friend[i][k] + friend[k][j]가 더 작다면(k를 경유하여 가는 거리가 더 작다면) 갱신해준다. 이렇게 구한 모든 회..
-
[백준]2493: 탑 - JAVA문제풀이/백준 2021. 5. 1. 14:25
[백준]2493: 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 자료구조 관련 문제로 볼 수 있을 것 같다. 문제는 어렵지 않으나 메모리, 시간 초과가 발생하지 않도록 적절한 자료구조를 사용해 주어야 한다. 우선 문제의 조건을 분석해 보면, 탑의 높이를 입력 받고 나서 레이저를 자신 보다 앞의 인덱스의 탑에만 송신한다. 즉, 탑을 미리 입력을 받지 않고 입력 받으면서 이미 입력 받은 값들 하고와 비교하여도 충분히 문제를 풀 수 있다는 것이다. 이..
-
[백준]1092: 배 - JAVA문제풀이/백준 2021. 4. 30. 19:43
[백준]1092: 배 www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 크레인이 무게 제한과 박스의 무게를 arraylist로 받았다. 그 다음 내림차순 정렬을 한 후 박스를 차례대로 하나씩 처리해 주었다. 현재 크레인에 박스를 담을 수 있다면 담았다고 생각하고 박스를 제거해 주었다. 현재 박스를 담을 수 없다면 다음 박스를 확인하며 담을 수 있는 박스를 찾아 제거해 주었다. 만약 제일 무거운 박스가 크레인의 무게 제한으로 인해 어떤 크레..
-
[백준]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(..