bitmask 3

BOJ#11723 집합

BOJ#11723 집합 * 문제https://www.acmicpc.net/problem/11723 * 풀이매우 쉬운 문제이지만 시간 제한과 메모리 제한을 모두 생각해야 합니다. 저는 비트마스크를 사용하여 풀어보았습니다.아니면 배열을 사용해서도 쉽게 풀 수 있습니다. * 나의 코드 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWri..

Algorithm/구현 2017.09.28

BOJ#1525 퍼즐

BOJ#1525 퍼즐 * 문제https://www.acmicpc.net/problem/1525 * 풀이종만북을 참고하여 풀었습니다.To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기 저는 이번에 bfs와 비트마스크를 이용해보았습니다. 맵은 하나의 정점으로 볼 수 있습니다. (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다) 그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다. 문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.저는 비트마스크를 이용해보았습니다. 각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면..

BOJ#2098 외판원 순회

BOJ#2098 외판원 순회 * 문제https://www.acmicpc.net/problem/2098 * 풀이dp 문제입니다. (주의점, 힌트)1. 사이클이므로 어느 점을 시작점으로 잡아도 상관없다.2. 마을 방문 여부를 매개변수로 넘겨주기 위해서는 ? 비트마스크를 사용하자.3. 시간 복잡도 : O(N^2 * 2^N) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232098_TSP/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.St..

Algorithm/DP 2017.04.07