구사과

1. ČVENK점 (x, y)가 빈 공간이기 위해서는 x & y = 0이 성립해야 한다. 이 점에서는 항상 (0, 0)으로 가는 경로가 존재하는데, 다음과 같은 방법으로 이를 찾을 수 있다. * x == 0 || y == 0일 경우에는 자명하게 경로를 찾을 수 있다. * x와 y가 모두 0이 아니라고 가정하자. lowest significant bit (LSB) 가 작은 쪽을 찾자. 여기서는 일반성을 잃지 않고 x라고 한다. 그렇다면, (x - LSB(x), y) - (x, y) 를 잇는 경로는 비어 있다. (x - LSB(x), y) 에서 재귀적으로 계속 경로를 찾아나간다.이 경로는 항상 존재하며 유일하다. 이는 빈 공간들이 트리를 이룬다는 증명이 되기도 한다. (사실 그건 사진을 보면 쉽게 눈치챌 수..

1. 숫자카드간단한 동적 계획법이다. 문자열을 길이 1 / 길이 2의 문자열로 분해하는 경우의 수를 세는 것인데, dp[i] = 앞 i자리 문자를 모두 분해하는 경우의 수라고 하면, dp[i-1]과 dp[i-2]에 대한 점화식이 나오고, 이를 통해 해결할 수 있다. 2. 놀이공원배열을 통해서 각 1분 단위의 시간에 휴식이 가능한지를 관리한다. 놀이기구 하나에 대해서, (시작 시간 - 10분) ~ (종료 시간 + 10분) 동안은 휴식이 불가능하다. 고로 각 놀이기구 마다 이 구간에 체크해 두면, 해당 단위 시간에 휴식이 가능한 지 알 수 있다. 이 정보를 안다면, 이 정보를 안다면, 가장 긴 휴식 가능 구간을 구하는 문제는, 0과 1로 이루어진 배열에서, 가장 긴 0으로 이루어진 연속 구간을 구하는 문제가..

1. 워크스테이션 배정그리디 알고리즘으로 해결할 수 있다. 모든 배정을 시작점 순으로 정렬하자. i번 배정을 할 때, 만약에 이미 끝난 다른 배정 중, 끝난 시간과 현재 시간과의 M 이하인 것이 있다면 그 배정과 같은 워크스테이션을 쓴다고 생각하자. 만약에 그러한 배정이 여럿 있다면 차이를 최대화 하는 것이 이득이다. (차이를 괜히 작게 줘 봤자 시작점이 큰 다른 배정에게 도움이 안 되니까) 이러한 그리디 알고리즘을 priority queue 등으로 구현하면 O(nlgn)에 문제를 해결할 수 있다. 2. Identifying Map Tiles주어진 문자열을 비트마스크로 읽어서 출력하면 되는 단순 구현 문제이다. (사실 1번 2번은 일단 placeholder로 넣은 거였습니다. 즉 나중에 다른 문제로 고칠..