1. '국내 기술 면접 가이드라인' 깃허브 https://github.com/JaeYeopHan/Interview_Question_for_Beginner GitHub - JaeYeopHan/Interview_Question_for_Beginner: :boy: Technical-Interview guidelines written for those who started studying :boy: :girl: Technical-Interview guidelines written for those who started studying programming. I wish you all the best. :space_invader: - GitHub - JaeYeopHan/Interview_Question_for_B..

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

1. 시간 복잡도(Time complexity)란? 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 입력 크기 : 알고리즘이 처리해야 할 데이터의 양 코딩 테스트 기준으로 대략적으로 기억하자. "컴퓨터가 초당 연산할 수 있는 최대 횟수는 1,000~2,000만 번이다." 2. 점근적 표기법 O(N), O(1), O(NlogN) 처럼 입력 크기에 따른 연산 횟수의 "추이"를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다. 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는, 즉 최악의 경우의 시간 복잡도를 표현하는 빅오 표기법(big-O notation)이다. 3. 파이썬은 부동소수형 데이터를 다룰 때 오차가 발생한다. 파이썬은 부동소수형 데이터를 이..

간단하게 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..