본문 바로가기

알고리즘60

[백준 Gold 1] 2098 외판원 순회 - Java 문제링크 : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 백준 10971 외판원순회2 문제의 코드를 리팩토링 시키는 방향으로 시도해보았다. 완전탐색으로 모든 경우를 탐색하면 시간초과!! 즉, 메모리제이션을 통해 이전에 체크한 부분을 재활용해야 한다. DP[][]을 만들어서 이를 관리 i 도시에 있고 j 비트에 포함된 도시를 탐색한 상황에서, 남은 도시를 모두 방문하는 최소비용 또한, 결국 .. 2021. 12. 22.
[백준 Silver 2] 10971 외판원 순회2 - Java 문제링크 : https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 한 도시에서 출발하여 모든 도시를 방문한 뒤, 출발 도시로 돌아왔을 때의 비용이 가장 적은 것을 출력하는 문제. 방문체크를 하면서 완전탐색을 하는 방법을 생각 도시의 수가 최대 10개이기에, 비용을 저장한 배열을 그냥 탐색하면서 다음 경로를 추적. 방문체크는 비트를 이용하여 판단 비용을 누적해가면서 경로를 추적하다가, 만약 이.. 2021. 12. 22.
[백준 Gold 2] 14657 준오는 최종인재야!! - Java 문제링크 : https://www.acmicpc.net/problem/14657 14657번: 준오는 최종인재야!! 첫째 줄에 문제의 수 N, 하루 풀이 시간 T가 주어진다. (2 ≤ N ≤ 50,000, 1 ≤ T ≤ 100,000) 이후 둘째 줄 부터 N-1개의 줄에 걸쳐 각 줄마다 A, B, C가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000) A와 B는 www.acmicpc.net 접근 과정 : 먼저 가장 많은 문제를 푸는 경우(트리의 지름)을 찾아야 한다.!! + 가장 많은 문제를 푸는 경우가 여러개 존재한다면, 가장 시간이 짧은 것을 찾아야 한다.!! 즉, 가장 긴 트리의 지름 중에서 가장 가중치가 적은 경우를 찾고 이를 기준으로 다시 한번 조회해서, 정확한 가중치를 찾아서 반.. 2021. 12. 21.
[백준 Gold 3] 13701 중복 제거 - Java 문제링크 : https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net 접근 과정 : 얼마전에 알게된 BitSet을 이용해서 이전에 입력된 숫자를 저장했다. 숫자값에 따른 존재여부를 확인하는 것은 HashSet보다 BitSet이 빠를것이라고 생각했다. + 배열과 비트마스킹을 이용한 풀이도 있기에 시도해보았다. (다른사람의 풀이를 참고.) 소스 코드 및 결과 : package BO.. 2021. 12. 21.

티스토리툴바