비트마스킹, 다이나믹 프로그래밍 문제입니다. dp[x][y][z] x - 자리수 y - 마지막 숫자 z - 사용된 숫자 ex) dp[4][2][11] - 4자리수에서 마지막 숫자가 2이며, 11(0000001011)로 1, 2, 4번째 자리 숫자를 사용함 dp[i][j][bit] = (dp[i][j][bit] + (j == 0 ? 0 : dp[i - 1][j - 1][k]) + (j == 9 ? 0 : dp[i - 1][j + 1][k])) % MOD; #include #define MOD 1000000000 #define MAX_BIT 1024 typedef long long ll; using namespace std; ll dp[101][10][MAX_BIT]; void solution() { int..
비트마스킹 문제입니다. 기억하고 있는 알파벳과 단어에 대해서 각각 비트마스크로 처리합니다. 그리고 해당 비트연산을 통해서 해당 알파벳을 포함하는지 확인하는 과정을 합니다. 비트마스킹으로 문제를 풀면 한 단어를 계산할 때 한번의 작업이 들지만 일반적으로 비교연산으로 처리하면 알파벳 한 단어를 계산할 때 단어의 길이만큼 작업이 듭니다. #include #include #include #include #define MAX_BIT 67108863 using namespace std; int n, m; int alphabet = MAX_BIT; vector word(10000); void solution() { int num; int count = 0; char alp; string s; cin >> n; cin..
다이나믹 프로그래밍 문제입니다. 1. 2*1의 경우 2가지 경우가 가능합니다. 1-1. 2*1 타일 1개 1-2. 1*1 타일 2개 2*2의 경우 3가지 경우가 가능합니다. 2-1. 1*2 타일 2개 2-2. 1*2 타일 1개(위), 1*1 타일 2개 (아래) 2-3. 1*2 타일 2개(아래), 1*1 타일 2개 (위) 이를 통해 점화식을 세울수 있습니다. DP[i] = DP[i-1] * 2 + DP[i-2] * 3 여기서 예외인 부분이 존재합니다. 3. 2*3의 경우 3-1. ㅁㅁ- -ㅁㅁ 3-2. -ㅁㅁ ㅁㅁ- (ㅁㅁ 1*2 타일) ( - 1*1 타일) 위와 같은 모양이 가능합니다. 해당 모양은 2*4, 2*5 ... 2*n 모두 가능한 모양입니다. 그래서 DP를 2차원 배열로 만들어서 2번째 부분에..
비트마스크, 다이나믹프로그래밍 문제입니다. 최소의 비용으로 모든 도시를 들려서 처음 출발한 도시로 도착하는 문제입니다. 다음의 비용은 동일합니다. A -> B -> C -> D -> A B -> C -> D -> A -> B C -> D -> A -> B -> C D -> A -> B -> C -> D 각각의 도시를 들렀을 때 최소값을 저장해가면서(DP) 최소비용을 찾습니다. 이 때 해당 도시를 들렸는지 확인하는 과정에서 비트마스크를 사용합니다. cost[x][y]에서 x는 현재위치, y는 방문한 도시들을 담고있습니다. cost[3][15]는 현재 위치는 3이고 1, 2, 3, 4의 도시를 방문한 상태입니다. (15 = 1 + 2 + 4 + 8) 1. 모든 도시를 방문했는지 확인 1-true. 시작점으로..
비트마스킹 문제입니다. 왼쪽에 벽 - 1 위쪽에 벽 - 2 오른쪽 벽 - 4 아래에 벽 - 8 11의 경우 1 + 2 + 8로 왼쪽, 위쪽, 아래에 벽이 있는 경우입니다. BFS를 이용해서 각 지점에서 출발을 합니다. 비트마스킹을 통해 벽이 있는지 확인을 하고 해당하는 부분들을 영역처리합니다. 영역의 개수와 영역의 크기를 출력합니다. (1, 2) 마주하는 영역의 경우 크기를 합쳐서 가장 크게 합칠 수 잇는 값을 출력합니다. (3) #include #include #include #include #include using namespace std; vector v; int visit[51][51]; int roomSize[2501]; int n, m; void bfs(int a, int b, int c) ..
비트마스크 문제입니다. 알파벳에 대하여 비트마스크로 처리합니다. 0x3FFFFFF (11 1111 1111 1111 1111 1111 1111) 각 텍스트에 대해서 비트마스크 처리해줍니다. 배울 수 있는 알파벳 개수에 따라 가능한 조합들을 DFS로 확인하였습니다. 각 조합에서 텍스트와 비트마스크 연산을 통해 문자조합이 텍스트를 포함하는 경우 카운트를 증가해줍니다. ex) 텍스트가 acd 이면 1101입니다 배울 수 있는 알파벳은 0으로 처리를 합니다. 배울 수 있는 알파벳이 abcdf이면 11 1111 1111 1111 1111 1101 0000입니다. 텍스트 (acd) 00 0000 0000 0000 0000 0000 1101 배울 수 있는 알파벳 (abcdf) 11 1111 1111 1111 1111..
비트마스크를 사용하는 문제입니다. 16진수로 0x00000을 기본값으로 받습니다. 16진수 5개이므로 0000 0000 0000 0000 0000 20개의 비트를 표현 가능합니다. add - or연산자로 해당 비트를 참으로 만듭니다. remove - 0xFFFFF - 해당 비트를 and연산을 통해 처리합니다. check - and 연산자를 통해 확인합니다. toggle - xor 연산자를 이용해 확인합니다. all - (bit = 0xFFFFF) empty - (bit = 0x00000) * 시프트 연산으로 해당 방향으로 비트를 밀어줍니다. #include #include #include using namespace std; int bit = 0x00000; void add(int x) { bit = b..
2019 KAKAO BLIND RECRUITMENT (2019 카카오 블라인드 채용 문제) 각 스테이지의 실패율을 구해서 내림차순으로 정렬하는 문제입니다. 1. 스테이지 배열을 내림차순으로 정렬 한 후 2. 스테이지를 높은 위치에서부터 낮은 위치로 반복문을 실행합니다. 3. 탐색중인 스테이지보다 높은 스테이지들은 분모가 되고 해당 스테이지는 분자가 됩니다. 4. 현재 스테이지와 해당 분수값을 저장합니다. 5. 1~4의 과정을 거친 후에 값이 높은 순대로, 같을 경우 스테이지가 낮은 순서로 정렬합니다. *분자가 없는 경우 0으로 처리해줍니다. (0으로 나눌 수 없음) #include #include #include #include using namespace std; bool compare(pair a, ..