[처음 생각했던 풀이] 1. 현재 커서 위치에서 그 글자까지 최소 몇번을 움직여야 하는가 계산하고, 2. 그 글자 (A)에서 알파벳을 몇 번 바꿔야 최소인가 계산하는 것으로 생각했다... [문제 풀이] 2. 알파벳이 A가 아닐 때, 변경하는 횟수를 구하는 과정은 쉽다. 아스키 코드를 생각하면 된다. ※ 'A'의 아스키 코드 = 65, 'Z'의 아스키 코드 = 90 1. 이 단계가 중요하다. 알파벳을 변경하려고, 매번 커서를 어느쪽으로 움직여야 할 지 판단하기는 힘들다! 이렇게 생각해보자. 1-1) 커서를 좌우로 움직이는 횟수는, 아무리 최악이어도 문자열을 한 번 순회하면 충분하다. -> N - 1 (최악의 경우) 또는 1-2) 한 쪽 방향(왼쪽/오른쪽)으로 먼저 이동한 다음, 그 반대 방향으로 이동하는 ..

간단하게 nCk -> n!/k!(n-k)! 같은 방식으로 문제를 풀 수 없다. 문제의 N과 K가 매우 크기 때문에 기존의 팩토리얼 알고리즘은 시간/공간 복잡도를 초과한다. 하지만 문제에서는 nCk 값을 1,000,000,007로 나누라고 했으므로 나머지를 구하는 소수(P)가 주어졌다. 그러면 페르마의 소정리를 적용할 수 있다. 자세한 것은 생략하지만, 조합 공식을 곱셈 형태로 변형할 수 있다. ∴ nCk​ % P = n! x ((n−k)!k!)^P−2 % P 여기서도 n, k, n-k의 팩토리얼을 그대로 구할 수 없기 때문에, 나머지 연산을 적용한 팩토리얼을 구하기 위해서 나머지 연산의 분배법칙 중 곱셈에 대한 분배법칙을 사용하면 된다! (A x B) % P = ((A % P) x (B % P)) % P..

이 문제의 분류는 "분할 정복을 이용한 거듭제곱" 이다. 즉, 어떤 수를 매우 큰 횟수로 거듭제곱 한다면, 시간복잡도를 줄이는 방법을 묻는 문제인 것이다. 예를 들어, 2를 32번 제곱한다는 것은 -> (2^16)^2, 즉 2의 16승을 한 번 제곱한 값과 같다. 그러면 32번의 연산에서 -> 17번의 연산으로 감소한다! 더 나아가서 ((2^8)^2)^2) 는 10번의 연산만 요구한다. (((2^4)^2)^2)^2)는 단 7번의 연산만 요구한다! def reduce_pow(a, b, c): if (b == 1): return a % c X = reduce_pow(a, b//2, c) if (b % 2 == 0): # 짝수라면 return X * X % c else: # 홀수라면 return a * X *..

어차피 체스판에 놓일 퀸들은 다 다른 행, 다른 열에 있어야 한다. 그리고 서로의 대각선에 위치해 있어도 안 된다. 맨 위에 행의 1번째 열부터 확인한다. 2번째 행에 되는 열(3번째 열)이 있으면, 3번째 행으로 내려간다. 이 상황은 3번째 행에 되는 열이 없다. 그럼 다시 2번째 행으로 올라간다. 2번째 행으로 올라가서 다음 열(4번째 열)을 확인한다. 3번째 행으로 가서 되는 열이 있는지(2번째 열) 확인한다. 이 상황은 4번째 행에 되는 열이 없다. 그럼 다시 1번째 행의 2번째 열부터 시작하는 것이다. 1번째 행의 2번째 열을 확인한다. 2번째 행에서 되는 열(4번째 열)이 있는지 확인한다. 3번째 행에 되는 열(1번째 열)이 있는지 확인한다. 4번째 행에 되는 열(3번째 열)이 있는지 확인한다..

재귀함수는 너무 어렵다.. 이전 15649번 문제도 한참 해맸는데, 조금만 응용하니까 더 헷갈린다. 처음 직접 풀었던 풀이 -> 그냥 이전 풀이처럼 모든 가능한 경우의 수를 다 때려박고 바로 출력하는 대신, 수열을 강제로 정렬하고 set으로 중복을 제거하고, 다시 출력했다. 딱 봐도 N, M이 커지면 커질 수록 시간 복잡도에서 손해를 볼 것이 분명하다.. N, M = map(int, input().split()) seq = [] seq_list = [] # 문제의 조건을 만족하는 수열들이 담길 리스트 def dfs(): if (len(seq) == M): seq_list.append(sorted(seq)) # 수열을 강제로 정렬한다음 리스트에 넣는다. return for i in range(1, N + ..

먼저 문제의 입력이 20억까지이므로 그냥 조합을 직접 계산하면 시간초과, 메모리 초과 가 난다. 끝자리가 0이라는 것은 2와 5의 곱으로 이루어져 있다는 것이다. 예를 들어 10 = 2 x 5이다. 나아가 끝자리 0이 2개라면, 2와 5의 곱이 2쌍이라는 것이다. 즉, 100 = 2 x 2 x 5 x 5이다. 따라서 "어떤 수의 끝자리 0의 개수는 그 수의 인수 2와 5의 개수 중에서 최소값이다." 라는 사실을 가지고 문제를 풀면 된다. 문제는 조합의 0의 개수니까 == N! 의 인수 2와 5의 개수 - ( (N - M)!의 인수 2와 5의 개수 + M!의 인수 2와 5의 개수)의 최소값을 찾으면 된다. def count_two(n): count = 0 i = 2 divisor = 2 while (div..

0. 먼저 아나콘다 프롬프트를 실행시킨다. 1. 아나콘다 환경 업데이트1-1. 기본 뼈대 업데이트conda update -n base conda 1-2. 패키지 업데이트conda update --all 1-3. 패키지 관리 시스템인 PIP 업데이트python -m pip install --upgrade pip 2. 파이썬 버전 변경 파이썬 버전을 변경하면 기본적으로 기존 패키지와 호환되지 않을 수 있으므로 기존 환경은 유지하고, 새로운 가상환경을 만들어서 그 버전을 사용하자! 2-1. 현재 변경 가능한 파이썬 버전 검색conda search python 2-2-1. 기존 환경은 유지하고, 새로운 가상환경을 만들어서 원하는 파이썬 버전을 적용하는 법 (예를 들어 3.11.0 버전을 적용하고 싶다면)cond..

같은 종류의 의상은 하나씩만 착용할 수 있으며, 알몸이 아니어야 하므로 꼭 1종류 이상의 의상은 착용해야 한다. 예를 들어, 3종류의 의상이 있으면 1종류만 착용해도 되고, 2종류를 착용해도 되고, 3종류를 착용해도 되지만 0종류를 착용하는건 안된다. 그렇다면 다음과 같은 식을 세울 수 있다. (a종류의 의상 수 + 1) x (b종류의 의상 수 + 1) x (c종류의 의상 수 + 1) ...... - 1 여기서 각 종류수에 +1을 해준 이유는 그 종류의 의상을 착용하지 않아도 되는 경우를 추가했기 때문이고 마지막에 -1을 해준 이유는 모든 의상을 착용하지 않은 경우는 제외해야 하기 때문이다. 의상의 종류는 같은데 이름이 다른 의상이 여러개일 수 있으므로 [의상의 종류]를 키, [의상의 이름들을 담은 리스..