목록비트마스킹 (6)
알고리즘 모음(C++)
백준 4991 - 로봇 청소기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 비트마스킹과 BFS를 이용해 풀 수 있는 문제입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second using namespace std; int N, M; char map[21][21]; int check[..
백준 14939 - 불 끄기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 비트마스킹을 이용한 문제입니다. 구현하는 방법을 떠올리는게 어려웠던 문제입니다. 한 곳의 불을 끄면 해당 위치부터 상하좌우의 값이 바뀌게 됩니다. 가로, 세로가 모두 10의 크기이기에 모든 경우를 확인하여면 2^100인 경우가 나오게 됩니다. -> 시간 초과가 생깁니다. 이 문제를 풀기 위해선 2가지를 생각해야하는데, 1. 한 번 누르면 다시 누를 필요가 없다. -> ..
백준 1562 - 계단 수(C++)
문제 링크입니다.https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 비트마스킹과 Dp를 사용하는 문제입니다. 생각하는게 어려웠던 문제입니다. 0~9를 모두 포함하는 계단 수를 세는 문제입니다. 0~9를 사용했는지 배열을 이용해서 구하는 방법은 너무 어려워집니다. 따라서 변수 하나를 통해 0~9를 사용했는지 저장할 것입니다. -> 비트마스킹 방법을 사용하면 됩니다. 문제에 사용된 비트마스킹은 다음과 같습니다. 9 8 7 6 5 4 3 2 1 0 1 1 1 1 0 0 0 0 0 0 예를 들어, 계단 수가 10206789 라고 하면, (6, 7, 8, 9)가 계단수가 됩니다...
백준 1194 - 달이 차오른다, 가자.(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 비트마스킹을 사용한 구현 문제였습니다. 비트마스킹이라는 방법을 사용하는 문제였습니다. int 형 변수를 비트연산자처럼 사용하는 방법인데, 0과 1을 이용해 원하는 데이터 값을 저장합니다. 예를 들어, 문제에서 열쇠를 a, c, f를 가지고 있다면, 10101로 나타내 해당 위치의 열쇠를 가지고 있는지 저장합니다. 그렇다면 새로운 열쇠를 얻었을 때, ..
백준 2098 - 외판원 순회(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 유명한 문제인 외판원 순회입니다. 외판원 문제에 대한 설명이 잘나와있습니다. 해당 블로그를 참고해주세요! 더보기 https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-%EB%AC%B8%EC%A0%9C ..
백준 11723 - 집합(C++)
문제 링크입니다. https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스킹을 이용한 문제입니다. 비트마스킹을 잘모르면 해당 링크를 통해 공부하면 풀 수 있습니다. https://rebro.kr/63 비트마스킹이 아닌 배열로서 문제를 풀면 시간초과가 걸립니다. 1~20까지의 수이니, 변수를 20자리로 생각하면 됩니다. 예를 들어 00000000000000000001 -> 1이 존재한다 01000000000000000000 -> 19가 존재한다. 따라서 X라는 수가 존재한다면 변수..