one Book a Day

버튼을 누르면 5가지 방향에 대해 불이켜지고 꺼지는 버튼이 있다. 2열부터는 위쪽 열에만 켜져있는걸 꺼주는 식으로 진행해주면 되는데 1열처리가 문제이다.(각각 누르고 켜는 경우의수 2의 10승) 때문에 1열 경우의 수에 대해 비트마스크 처리를 해준다. 사실 그 외의 탐색은 10*10이어서 그리 오래걸리지 않기 때문에 1열 경우의수 탐색만 잘 처리해주면 통과한다. table = [] for i in range(10): temp = list(input()) for j in range(10): if temp[j] == 'O': temp[j] = True #True: 불 켜져있음 continue temp[j] = False #False: 불 꺼져있음 table.append(temp) # 5방탐색. dx = [-..

마찬가지로 N=26이지만 5개 확정시켜줘서 N=21인 비트마스킹 문제. 입력된 글자에대해 0001010101001 켜진 이진수를 tmp에 더해주고 배열에 저장해뒀다가 1,2,,8,16등 2의 배수가 저장된 배열에서 k개 뽑아낸 조합(2의 배수들은 알파뱃의 1,0켜지고 안켜지고를 나타낸다.) 조합의 합과 아까 저장해둔 필요알파뱃 비트합의 tmp값과 비교해 같으면 문자를 만들수 있는 알파뱃조합이라고 판명해 ct를 쌓는 방식으로 어떤 알파뱃 조합이 cnt가 가장 높은지(많은 문자열을 소화할 수 있는지) 판단하는 문제. from itertools import combinations n, k = map(int, input().split()) # 글자가 5개 미만이면 antic도 못배우니까 어떤 글자도 배울 수 없..

비트마스크 문제. 0~9까지의 숫자를 총 자릿수를 늘려가고 뒷자릿수에 따른 경우의수를 더해주며 dp진행합니다. 초깃값은 100000000, 010000000,00100000 ....000000001 시작값에 대해 불을 켜주고 경우의수 1을 더해주고 시작합니다. dp[x][y][z]에서 x는 비트숫자(불켜진 모든 경우의수), y는 자릿수(0:1자리), z는 마지막자리의 숫자. import sys input = sys.stdin.readline n = int(input()) # dp: 비트 정보, 자릿 수, 끝나는 수 dp = [[[0] * 10 for _ in range(101)] for _ in range(1

비트마스크(bit mask) 비크마스크란 무엇인가? 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술. 집합에서 하나의 원소는 하나의 bit로 표현(꺼져있다, 켜져있다.) ex switch_states = [True, False, False, True, True, False, False, False, True, True] switch_states = 0b1001100011 # 611, python에서는 앞에 '0b'를 붙여 이진수 표현 가능 정수형으로 표현하면 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐 더 간결한 코드 작성이 가능 더 빠른 연산이 가능 더 작은 메모리의 사용. 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함. (중요) 위와같은 장점이 ..