Python 썸네일형 리스트형 [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)이라고.. 더보기 [DP] BJ_2775, 부녀회장이 될테야 [문제의 접근] 이 문제에서의 핵심은 바로 다음 글귀이다. "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다." 이 것을 읽고 어떤 생각을 해야할까? 특이한 조건이네 이렇게? 특이한 조건인건 맞다. ㅎㅎ. 많은 알고리즘 문제에서는 스토리를 만들어내기 위해 사실 별로 필요없는 문구들도 많이 넣기는 하는데, 위의 문구를 보면 아래와 같은 수식을 떠올려야 한다. 우리는 알고리즘 문제를 풀고 있고 알고리즘은 수식으로 이루어지니 말이다. arr[a][b] = arr[a-1][1] + arr[a-1][2] + ... arr[a-1][b] 그럼 이 문제를 위의 수식 그대로 풀어내면 될까? test case의 T의 숫자가 주어지지 않아서 명확하진 않지만.. 더보기 [Two-Pointer] BJ_2230, 수 고르기 [문제의 접근] 두 수를 선택하고, 두수의 차이가 M이상이면서 가장 작은 차이를 구해야 한다. 어떻게 접근해야 할까? Bruteforce로 접근하면 가장 쉽게 접근법을 생각할 수 있다. 즉 모든 경우의 수를 비교해 보는 것이다. N개의 수 중에서 2개의 수를 임의로 선택해야 하기 때문에, $O(N^2)$ 시간 복잡도가 나온다. For 문을 계층적으로 2번 돌린다고 생각하면 쉽다. 첫번째 수를 정하고 N-1개 비교, 2번째 수를 정하고 N-2개 비교,.... 현재 N이 1,000이하라면 충분하겠지만, 주어진 값은 N이 100,000 으로 주어져 있다. 연산량은 $10^{10}$으로 대략적인 1초의 연산량 $10^8$을 초과하므로 시간초과다. 그럼 어떻게? $O(n\log_{2}{n})$의 접근이나, $O(.. 더보기 [BruteForce] BJ_1018 체스판 다시 칠하기 알고리즘의 존재 이유이자 최종 목적은 제한시간 안에 얼마나 효율적으로 문제를 계산해 낼 수 있으냐이다. 따라서, 모든 알고리즘 문제에서 수의 입력 범위를 확인하는 것은 중요한 일이다. 입력 범위가 충분히 작다면 굳이 어려운 방법으로 문제를 풀 필요가 없다는 뜻이된다. 컴퓨터는 1초에 1억번 정도의 연산을 해낼 정도로 계산에 최적화된 기계이다. 그렇다면 이 문제에서는 얼마만큼의 연산량이 필요할까? 문제를 읽어보면 확인할 수 있겠지만, 입력으로 주어지는 전체 판의 크기는 50 x 50이다. 여기에서 기준이 되는 매트릭스 좌측 상단의 색깔이 'W', 'B' 두가지 케이스에, 검사해야 하는 maxtrix의 크기인 8x8이다. 총 계산량은 ? 아무리 크게 잡아도 32만을 넘기 어렵다. 그렇다면 우리가 이 문제를 .. 더보기 이전 1 다음
