Bruteforce 썸네일형 리스트형 [Bit Mask]BJ_14939, 불 끄기 [문제의 접근] 전구 100개가 10x10 모양으로 주어지는 input, 무엇을 떠올려야 할까? 10이하로 주어지는 모양을 보아서는 뭔가 bit mask나 DFS적인 접근이 될거라는 생각이 먼저 떠올라야 한다. 또한 기초적으로 생각해야 할 것들을 적어보자. 1) XOR 연산을 떠올려야 한다. 스위치를 누르면 불이 켜져있을 때는 꺼지게 되고, 불이 꺼져 있을 때는 켜지게 된다. 이는 곧 XOR연산을 의미한다. 0을 꺼짐, 1을 켜짐으로 명명한다고 하면 0 ^ 1 = 1, 1 ^ 1 = 0 이 되니 말이다. 2) (특징) 행렬의 제일 위에서 부터 불을 끄게 된다고 한다면 현재보다 위의 행에 불이 켜져 있다면 반드시 현재 행의 스위치를 눌러야 한다. 예를 들면 위의 예제 입력에서 좌측 상단을 (0, 0)이라고.. 더보기 [BruteForce] BJ_1018 체스판 다시 칠하기 알고리즘의 존재 이유이자 최종 목적은 제한시간 안에 얼마나 효율적으로 문제를 계산해 낼 수 있으냐이다. 따라서, 모든 알고리즘 문제에서 수의 입력 범위를 확인하는 것은 중요한 일이다. 입력 범위가 충분히 작다면 굳이 어려운 방법으로 문제를 풀 필요가 없다는 뜻이된다. 컴퓨터는 1초에 1억번 정도의 연산을 해낼 정도로 계산에 최적화된 기계이다. 그렇다면 이 문제에서는 얼마만큼의 연산량이 필요할까? 문제를 읽어보면 확인할 수 있겠지만, 입력으로 주어지는 전체 판의 크기는 50 x 50이다. 여기에서 기준이 되는 매트릭스 좌측 상단의 색깔이 'W', 'B' 두가지 케이스에, 검사해야 하는 maxtrix의 크기인 8x8이다. 총 계산량은 ? 아무리 크게 잡아도 32만을 넘기 어렵다. 그렇다면 우리가 이 문제를 .. 더보기 이전 1 다음
