프로그래민👨‍💻

비트마스킹을 이용한 완전탐색으로 해결한 문제이다. 이 문제를 맨처음 봤을땐 아이디어가 잘 생각안지 않았다. 곰곰히 생각해보니 어차피 빈칸 하나에 대해선 가로 방향 또는 새로 방향을 가질 수 있으므로 전체가지수를 2^(가로X세로) 로 생각하고 모든 경우에 대해 값을 계산해보는 방법을 생각해냈다. 2가지의 경우를 가지기 때문에 비트마스킹을 이용하여 모든 subSet을 가로는 -1, 세로는 1로 표현하여 dir이란 배열에 대입해주어 계산하였다. 그 후 해당 경우에서 가로, 세로를 따로 계산하여 더한값을 최종답으로 갱신해주며 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3..

2개로 팀을 나눠서 답을 구하는 문제이다. 스타트와 링크 문제와는 다르게 정확히 두개의 팀이 같은 팀원수를 가지는 것이 아니라 다른 두개의 팀으로 나눠지기만 하면 되는 문제이다. 그래서 이문제를 비트마스킹으로 접근하였다. 비트 마스킹을 이용하여 예를 들면 N=4일때 0001 부터 1110 까지 수를 구하고 1과 0으로 팀을 나누어서 값을 구하여 비교해주는 방식으로 답을 구하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 6..

기본적인 부분수열의 합문제이다. 두가지 방법으로 풀어보았다. 첫번째로는 비트마스킹을 이용하여 모든 부분수열을 구하는 방식으로 구현하였다. 두번째로는 재귀적인 DFS 방식으로 현재항을 더해주는 경우, 현재항을 더해주지 않는 경우로 나누어 2번씩 호출해주는 방식으로 풀었다. 이때 기저조건으로는 마지막인덱스에 도달하였을 경우 종료시키게 해주었다. 시간은 비트마스킹을 사용하는 첫번째 코드보다 두번째 재귀적인 DFS를 사용한 코드가 빨랐다. 1. 비트마스킹 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 package ch..