Code Diary Code Diary

그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 1번 코드 (시간 초과) 뺄셈으로 반복문을 돌렸더니 시간 초과 판정이 나왔다. 2번 코드 (정답) 나눗셈으로 반복을 돌렸더니 정답이었다.

맨 처음이 W로 시작하는 "조건 만족 전체 사이즈 체스판"과 B로 시작하는 "조건 만족 전체 사이즈 체스판"을 미리 구해두고,필요 색칠 횟수를 값으로 삼는 누적합을 미리 구해둔 뒤, 그걸 활용하여 체스판을 자르는 모든 경우의 수를 돌면서 최소 색칠 횟수를 구한다. 임의의 K*K 크기에서 색칠 횟수를 구할 때 왼쪽 윗 부분에서 한 칸씩 전의 idx를 사용하기 때문에, 편의를 위해 idx의 시작을 1부터로 통일한다. check는 모든 칸이 조건을 충족하는 체스판을 나타낸 것이다.sum_sub는 (1, 1)부터 (x, y)까지의 체스판의 색칠 횟수 값을 담는 2차원 리스트이다. 체스판을 자르는 모든 경우의 수를 돌면서 누적합을 이용하여 가장 적은 색칠 횟수를 찾는다.

첫 번째 코드 : 시간초과 열은 누적합으로 구했지만 행으로는 반복문으로 더했다. 시간초과가 났다. 두 번째 코드 : 정답 이차원으로 전부 누적합을 구한 후 색칠 된 부분을 구하기 위해 제일 큰 네모에서 작은 네모 두 개를 뺀 후 두번 빼진 작은 네모를 한번 더해준다. 9번 줄 같이 작성하면 간단하게 반복해서 입력받을 수 있으니 꼭 기억해두자.

첫 번째 코드 : 시간초과 누적합을 이용했고 이중반복문을 사용했다. 시간초과 판정을 받았다. 두 번째 코드 : 정답 수학적 원리를 이용했다. 예를 들어 1 2 3 1 2 가 들어왔다고 해보자. 누적 합 리스트DP를 구해보면 0 1 3 6 7 9 가 된다. 원래는 여기서 (DP[i]-DP[j])%M == 0인 모든 i j 쌍을 구하는 것이지만 두 개를 빼서 나눴을 때 나머지가 0 이라는 소리는 그 두 개를 각각 M으로 나눴을 때 나머지가 같다는 의미다! 즉 각각을 나누면 0 1 0 0 1 0이 되고 나머지가 같은 것 들을 각각 쌍을 지어주면 되는 간단한 문제가 된다. 0들을 쌍지어주면 6개, 1들을 쌍지어주면 1개가 나와 정답이 7이 된다. 쌍지어주는 것은 nC2 (조합)을 이용했다.

첫 번째 풀이 : 50점 (맞긴하지만 프로그램이 느림) 같은 문자가 들어왔을 때 똑같은 과정을 반복하는 것은 너무 비효율이므로 누적합을 이용했다. a를 받을때마다 먼저 a라는 알파벳에 관해서 내가 문자열에서 세봤는지 검사하고, 안세봤으면 세본 후 답을 구하고, 세봤으면 이미 구한 리스트에서 답을 쉽게 도출해낸다. sys.stdout.write()는 print()와 비슷한데, 차이점은 1. 자동 줄바꿈 x, 2. str만 출력함 3. 빠름 이다. 새로운 a를 받을 때마다 다시 세는 과정때문에 50점을 받았다. 세는 과정을 줄여야 한다. 두 번째 풀이 : 100점 첫 번째 풀이와 두 번째 풀이의 가장 큰 차이점은 첫 번째 풀이는 두 번째와 같은 문자가 계속 들어올 땐 차이가 없지만 서로 다른 문자가 들어오면..

처음에는 제일 생각해내기 쉬운 반복문으로 짰다. 그럴 것 같았지만 시간초과 판정을 받았다. 아무래도 N과 M이 커지면 반복문을 너무 많이 돌리게 돼서 그런 것 같다. 새로운 방법으로 미리 0부터의 합을 더해놓는 리스트L2를 만들어놓고, i와j에 따라서 L2[j]-L2[i]를 구하면 미리 0부터의 합을 더해놓는 과정하나만 늘리면 그 이후의 반복문이 다 매우 간단해진다. L = 5 4 3 2 1 L2 = 0 5 9 12 13 14 i = 1 j = 3 구간합 = L[0]+L[1]+L[2] = L2[j]-L2[i-1] = 12

정말 암담했다. 아무리 생각해도 풀이법이 생각나질 않아서 구글링을 해보았다. 그거마저 이해하는데 시간이 들었다. 풀이법은 다음과 같았다. 먼저 이차원 리스트를 생각한다. 행과 열을 각문자열을 넣고 하나씩 늘려가며 횡단한다. 예를들어 2행 3열에서 서로 A로 일치하게 된다. 이러면 이 행렬이 추가되기 이전의 값 (1행2열) = 1 에서 1을 더해준다. 이 말은 곧 원래 만들 수 있던 최장공통부분수열 뒤에 A를 하나 더 붙여 길이가 1늘어나게 되었다는 뜻이다. C -> CA 2행 4열은 서로 일치하지 않으므로 좌측값 또는 위에값 중 큰 값인 2를 그대로 가져온다. 이 말은 곧 이 행렬 상관 없이 그 전에 만들 수 있던 것 중 가장 긴 것을 가져오겠다는 뜻이다. 여기서는 CA를 그대로 가져온다는 뜻이다. 이해..

없애야 하는 전깃줄을 구하려고 하게 하는게 이 문제의 함정이었다. 없애야 하는 전깃줄을 구한다고 생각하지 말고 안엉키는 전깃줄의 모임을 구한다고생각하면 증가부분수열을 구하는 문제가 된다. S1에는 A와B의 전깃줄 인덱스 묶음이 이차원 리스트로 저장된다. S2에는 A인덱스 기준으로 오름차순 정렬된다. S3에는 최장길이 증가부분수열을 구하기 위한 번호가 저장된다. S1.sort(key = lambda x:x[0]이란 x[0]에 대해서 S1을 오름차순 정렬하겠다는 뜻이다.