문제 상황 코딩 테스트 문제를 풀다 보면, 다음과 같은 조건이 있을 때가 있다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 위와 같은 조건은 숫자가 너무 커져 발생하는 오버 플로우를 방지하기 위함이다. 하지만 최종 값에만 나머지 연산을 적용할 경우 여전히 오버 플로우가 발생할 때가 있다. # (n x 2) 바닥 채우기 # n 번째 바닥 def solution(n): # 경우의 수 저장 DP = [1, 2] for i in range(2, n): DP.append(DP[i - 2] + DP[i - 1]) return DP[n - 1] % 1000000007 # 최종 값에만 나머지 연산을 적용할 경우 이럴 땐 연산 과정 중간 중간 나머지 ..

모든 사진과 내용은 강의를 참고 했습니다. 투포인터 2 가지 점(시작, 끝점)의 위치를 기록해서, 순차 접근을 빠르게 할 수 있도록 도와주는 알고리즘이다. 투포인터를 사용하면 기존 $O(N^2)$에서 $O(N)$로 시간 복잡도를 줄일 수 있다는 장점이 있다. 매 시행 마다 투 포인터의 시작, 끝 점은 1개 씩 움직이고, 각 점이 마지막 성분에 도달하면 끝나게 되기 때문에 $O(N)$ 임 활용 1 : 부분 합 구하기 투포인터는 수열의 부분 합을 구하는데 활용될 수 있고, 수열의 모든 수가 양수인 경우에만 가능하다. 모든 수가 양수여야 시작점을 오른쪽으로 옮길 때, 합을 구성하는 성분 수가 줄어 합이 줄어 들고, 끝점을 오른쪽으로 옮겨 부분 합을 구성하는 성분 수가 늘어 합이 늘기 때문이다. 투포인터를 활용..

조합 def get_comb(arr, n): comb_list = [] # 종료 조건 if n == 0: return [[]] # 현재 arr의 담긴 수를 확인 for i in range(len(arr)): # 선택된 수 num = arr[i] # 나머지 수로 구성된 배열 arr_left = arr[i+1:] for comb in get_comb(arr_left, n - 1): comb_list.append([num] + comb) return comb_list 순열 def get_perm(arr, n): perm_list = [] # 종료 조건 if n == 0: return [[]] # 현재 arr의 담긴 수를 확인 for i in range(len(arr)): # 선택된 수 num = arr[i] ..

기본 연산 [ic]SUM[/ic], [ic]COUNT[/ic], [ic]AVG[/ic] : 합, 개수, 평균 [ic]ROUND[/ic](숫자, 반올림할 자릿수) : 자릿수를 기준으로 반올림 [ic]TRUNCATE[/ic](숫자, 버림할 자릿수) : 자릿수를 기준으로 버림 [ic]CEIL[/ic], [ic]FLOOR[/ic] : 정수화(올림, 버림) [ic]POW[/ic], [ic]SQRT[/ic] : 거듭 제곱, 제곱근 The Blunder | HackerRank Query the amount of error in Sam's result, rounded up to the next integer. www.hackerrank.com SELECT CEIL(AVG(SALARY) - AVG(REPLACE(CAST..

기본 패턴 re.search() : 주어진 패턴과 일치해야 함 re.match() : 주어진 패턴과 처음부터 일치해야 함 고급 패턴 () : 문자열을 그룹으로 묶어서 관리(캡쳐)할 수 있도록 도와준다. \1 ~ 9 : 캡쳐된 그룹의 인덱스를 명시해서 참고할 수 있다. # () : 그룹 지정, \1 : 캡쳐된 그룹 참조 re_pt1 = r"(aya|ye|woo|ma)\1+" 찾고자 하는 패턴이 반복되는 경우, Group 또는 findall을 활용할 수 있다. Group 활용한 경우 예시 # 우선 Group으로 match 시작 >>> m = re.match('([0-9]+) ([0-9]+)', '10 295') >>> m.group(1) # 첫 번째 그룹(그룹 1)에 매칭된 문자열을 반환 '10' >>> m..

오류 겪을 때마다 추가합니다. 런타임 에러 0으로 나누었을 때(분모가 0인 경우) 존재하지 않는 인덱스에 접근할 때 선언하지 않은 변수를 사용할 때 재귀 호출이 너무 깊어질 경우 : 참고 타입 에러 문자열을 인덱싱하여 값을 수정할 때 deque를 slicing 할 때

구간 합 N개의 수에 대해서 M개의 구간 정보로 구간 합을 구해야 하는 경우 구간 합을 완전 탐색을 통해서 구할 경우 O(NM)의 시간 복잡도 결국 N, M이 클 경우 별도의 방법 필요 누적합(Prefix sum) N개의 수는 변하지 않고 그대로이며 M개의 구간 정보만 바뀌는 상황일 때, N개의 수에 대한 누적합을 계산하여 별도의 리스트에 미리 저장해줌 필요한 시간 복잡도 O(N) 이 경우 M개의 구간 정보 L, R에서 구간 합을 구할 경우 P[R] - P[L-1]을 통해서 빠르게 구할 수 있음 인덱싱만 하면 되기 때문에 각 구간 정보당 O(1)의 시간 복잡도를 가지게 됨 따라서 구간 합을 구할 때 누적합을 이용하게 되면 O(N + M)의 시간 복잡도만으로 가능하다. 참고 이것이 취업을 위한 코딩 테스트..

완전 탐색 활용 최대 공약수(GCD) : O(N)의 시간 복잡도 최소 공배수(LCM) : O(N*M)의 시간 복잡도 n, m = map(int, input().split()) # 최대 공약수 for i in range(max(n, m), 0, -1): if n % i == 0 and m % i == 0: print(i) break # 최소 공배수 for i in range(min(n, m), n * m + 1): if i % n == 0 and i % m == 0: print(i) break 유클리드 호제법 : 최대 공약수를 빠르게! 유클리드 호제법을 사용하면 최대 공약수를 재귀적으로 구할 수 있다. 이 경우 최대 공약수를 구하기 위해 필요한 시간 복잡도는 O(logN)이다. 유클리드 호제법은 다음과 같..

시간복잡도 알고리즘을 위해 필요한 연산의 횟수를 나타냄 코딩 테스트에서 작성한 프로그램이 모든 입력을 받아 처리하고 실행한 결과를 출력하는데까지 걸리는 시간 측정 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는 지를 나타냄 문제에서 가장 먼저 확인 ‘복잡도’라고 하면 보통 ‘시간 복잡도’를 의미 보통 코딩 테스트의 시간 제한 : 1 ~ 5초 / 파이썬 기준 대략 2000만번의 연산 ~ 1억번의 연산 처리 가능 시간 제한 문제를 해결할 때는 N의 범위에 따라 다른 시간 복잡도 알고리즘을 설계 시간 제한이 1초에 대한 문제에 대한 예시 N의 범위 복잡도 500 O($N^{3}$) 2,000 O($N^{2}$) 100,000 O($Nlog N$) 10,000,000 O($N$) 공간 복잡도 알고리즘을..