본문 바로가기

비트마스킹4

[백준 Gold 3] 2146 다리 만들기 - Java 문제링크 : https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 접근 과정 : DFS를 통해 같은 대륙은 같은 번호를 붙여서 구분. 대륙을 탐색할 때, 대륙은 Queue에 좌표와 대륙 번호를 저장 (BFS 때 이용하기 위해) 어떤 대륙에서 출발하여, 다른 번호의 대륙을 만날 때, 그 거리를 반환하는 BFS 구성 한칸에서 시작하는 DFS를 하는 것이 아니라, 모든 대륙을 담은 Queue로 한번에 BFS를 시행 방문체크는 int[][]에 비트마스킹을 통해 .. 2021. 12. 28.
[백준 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.
[백준 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.
[백준 Silver 1] 2961 도영이가 만든 맛있는 음식 - Java 문제링크 : https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 접근 과정 : 재료의 조합을 만들어가면서, 각 조합의 신맛과 쓴맛을 계산해 그 차이를 갱신한다. 완전탐색을 통해 모든 조합을 확인. 사용되는 재료는 비스마스킹으로 체크. 아무것도 사용하지 않은 경우를 제외한, 나머지 조합으로 맛의 차이 계산 소스 코드 및 결과 : package BOJ; /* 도영이가 만든 맛있는 음식 */ import java.io.*; impo.. 2021. 12. 21.

티스토리툴바