백준/비트마스킹6

• 

  [백준 2098번 / C++] 외판원 순회 비트마스킹과 dp를 활용한 문제이다. tsp 알고리즘은 완전 탐색으로 도시가 n개이면 시간 복잡도 n! 이 걸리는 np-hard문제로 널리 알려져있다. 그렇기 때문에 이미 탐색했던 경로에 대해서는 다시 방문해서 처음부터 재귀함수를 호출할 필요없이 비트마스킹과 메모이제이션을 활용해 기록했던 데이터값을 다시 들고와야 시간초과를 피할 수 있다. #접근방법 * dp [도시의 수][ 방문 비트] ex) [방문비트] -> 1100 : 4번째 도시와 3번째 도시를 방문했다는 뜻. ex.1) " 0 -> 1 -> 2 -> 3 (도시 방문 경로) " 위의 방문 경로는 dp[3][1111(2진수)]의 배열의 주소를 참조하고 있으며 해당 배열에 다음 도시로 가야할 경로값 중 최소값을 더해주며 갱신해준다. 즉, 완전탐색을 하.. 백준/비트마스킹 2022. 2. 23.

• 

  [백준 2234번 / C++] 성곽 이 문제는 "비트연산, 완전탐색, BFS"를 활용한 문제이다. 이 세가지에 대한 이해도가 확실하면 정말 재밌게 풀 수 있을것이다. 먼저 구해야 할 값은 총 3가지이다. 1. 처음 BFS 함수를 호출 하는 개수(방의 개수) 2. BFS함수에서 Queue값을 pop() 하는 개수(방의 영역) 3. 하나의 벽을 허물었을 때 나오는 최대 방의 영역. 먼저 , 첫 번째 답과 두 번째 답을 풀기 어렵다면 쉬운 bfs 문제를 풀고 오기를 권한다. 이 문제에서 조금 다른점은 벽의 위치를 2진수 방법으로 표현했다는 것이다. 예를들어, 10진수 "11"은 2진수로 "1011" 이라는 값이 나오는데 오른쪽부터 위치한 1은 서쪽에 벽이있고 그 다음 1은 북쪽에 벽이 있고 그 다음 0은 동쪽에 벽이 없고 그 다음 1은 남쪽에 .. 백준/비트마스킹 2022. 2. 11.

• [백준 14889번 / C++] 스타트와 링크 1. 비트연산을 통해서 두개의 팀으로 나올 수 있는 모든 경우의 수를 구함. ex) abcdefgh 11001010 {a,b,e,g}, {c,d,f,h} 두팀으로 나뉘어짐. abcdefgh 11001011 {a,b,e,g,h}, {c,d,f} 다른 한팀이 인원이 더 많으므로 continue; 2. 이차원 배열에서 해당하는 팀원의 인덱스값을 통해 팀의 sum 값을 갱신해나간다. 3. 두 팀의 차이값이 이전에 구했던 차이값보다 작으면 계속해서 갱신 #include #include #include #include #include using namespace std; int min_number = INT_MAX; int main() { int n; cin >> n; vector v(n, vector(n, 0)).. 백준/비트마스킹 2022. 1. 28.

• 

  [백준 5430번 / C++] AC dequeue 자료구조를 활용하자. dequeue를 활용하지 않고 벡터를 활용하여 R이라는 명령어가 들어왔을 때 reverse라는 정렬을 할 수도 있다. 하지만 수행할 함수가 100,000이면서 R이라는 명령어만 주어졌고, n의 개수가 100,000이라면 100억번을 수행해야한다. 그렇다면 시간초과가 발생하게 된다. 또한, D라는 명령어가 들어왔을 때는 맨 앞에 원소를 지우는 erase 함수를 수행할 수 있지만 뒤에 있는 모든 원소를 하나씩 당겨와야하기 때문에 그만큼의 시간이 든다. 그렇기 때문에 dequeue라는 자료구조를 활용해서 제일 앞의 원소를 뺄지 또는 제일 끝의 원소를 뺄지를 back이라는 비트변수가 체크해준다. 즉, R이라는 명령어가 들어오면 back라는 변수를 1로 세팅하면서 현재 거꾸로 .. 백준/비트마스킹 2022. 1. 25.

• 

  [백준 1062번 / C++] 가르침 이번 문제는 비트마스킹을 활용해서 완전 탐색을 하여 풀었다. 문제에서 n개의 문자열이 주어지는데 공통된 언어로는 "anta"로 시작되고, "tica"로 끝난다는 것이다. 즉, 'a', 'n', 't', 'c', 'i' 이 단어를 배우지 못하면 어떤 단어도 읽지를 못한다. 그렇기 때문에 배우는 알파벳의 개수가 저 알파벳을 포함해서 최소 5개는 돼야 한다는 것이다. 그렇기 때문에 alpa 라는 값에 최초 초기화해야할 숫자는 'a', 'n', 't', 'c', 'i' 이 단어를 가리키는 이진수의 값으로 나타내야한다. 그리고 dfs 를 돌게 되는데 여기서 중요한 점은 첫번째 인덱스를 돌다가 dfs를 돌 때는 그 인덱스 값을 파라미터 값으로 전달 해줘야한다. 즉, dfs 함수 안에서 또 for문이 동작하게 되는데.. 백준/비트마스킹 2022. 1. 20.

• 

  [백준 19942번/ C++] 다이어트 해당 문제는 map과 비트마스킹을 이용해서 풀면된다. 조건에서 N은 3이상 15이하라고 하였으니 N이 5일때를 가정하고 한번 풀어보자. N이 5라는 것은 데이터가 들어있는 표의 개수가 총 5개라는 뜻이다. 해당 문제는 각 표의 데이터값을 하나하나 다 더해서 조건식을 만족하는지 체크를 하는것이다. 그렇기 때문에 비트마스킹을 활용하는것이다. N이 5라면 비트는 5개지만 나타낼수 있는 수는 총 2^5개가 만들어진다. 예를 들어 00001, 00010, 00011, ... , 11110, 11111 이런것이 만들어질텐데 비트가 1인것은 각 표의 튜플(행)을 보라는 뜻이다. 즉, 00101 이라면 첫번째 데이터값과 세번째 데이터값들을 더해서 각 영양분이 최소 영양성분이 되냐를 따지면 된다. 만약 11111 이라면.. 백준/비트마스킹 2022. 1. 13.