1.슬라이딩 윈도우 (Sliding Window) 특징 '연속된 배열 안에서 범위의 크기가 일정할 때' 2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결 서브 배열 합계 체크 import sys def max_sub_array(arr, k): maxsum = -sys.maxsize - 1 arraysize = len(arr) for i in range(arraysize - k + 1): current_sum = 0 for j in range(i, i + k): current_sum += arr[j] maxsum = max(maxsum, current_sum) return maxsum if __name__ == '__main__': print(max_sub_array([2, 4..
1. Two Pointer Algorithm 전제 투 포인터 알고리즘 : 리스트(배열)가 '정렬'이 되어있어야 함! 특징 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 구간 합의 경우 오직 누적 합(합 배열)에서 기존의 배열을 순차적으로 접근(X), 기존의 배열의 합에 접근(O) 이기 때문에 다름 흔히 2,3,4,5,6,7번 학생을 지목해야 할 대 간단히 '2번부터 7번까지의 학생'이라고 부름 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음 Caution 포인터 2개가 모두 한 쪽 끝에서 시작할 수도 있으나, 양쪽 끝에서 시작할 수도 있음 연속한 구간 합을 구하는 경우 : 한 쪽 끝에서 시작 두..
1. 구간합 (Prefix Sum) 1) 기존 배열 -> 누적합(합배열) : (주어진 배열의 합 배열을 전부 구해놓을 것) 2) 누적합(합배열) 더하거나 빼서 -> 구간 합 특징 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 2. 과정 Process 1. 합 배열 구하기 : 리스트 A가 있을 때 합 배열 S는 다음과 같이 정의 • S[i] = A[0] + A[1] + A[2] + .... + A[i] • 기존의 리스트 데이터들을 전처리한 배열 • 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)->O(1) • S[i] = S[i-1] + A[i] : 1차원 배열 or temp += i으로 놓고 S.append(temp)하기 • ..
1. 배열 (Array) 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 값은 인덱스를 통해 참조할 수 있음, 선언한 자료형의 값만 저장할 수 있음 특징 - 인덱스를 사용하여 값에 바로 접근할 수 있음 - 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움 - 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요함 - 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음 - 구조가 간단하므로 코딩 테스트에서 많이 이용함 2. 리스트 (List) 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 특징 - 인덱스가 없으므로 값에 접근하려면 head 포인터부터 순서대로 접근해야 함 -> 값에 접근하는 속도가 느..
코딩테스트를 진행하며 실수하기 쉬운 4가지 오류 찾아보기 1. 변수 초기화 오류 찾아보기 • 변수 초기화 로직에서 초기화를 제대로 하지 않은 경우 • 두 번째 테스트 케이스부터 통과되지 않을 때는 모든 변수가 정상적으로 초기화되고 있는지 디버깅을 이용해 확인해볼 것! 2. 반복문에서 인덱스 범위 지정 오류 찾아보기 • 반복문을 사용할 대마다 범위와 시작 인덱스를 꼼꼼하게 확인할 것 • 입력 실수를 대비하여 디버깅하는 습관을 들일 것! 3. 잘못된 변수 사용 오류 찾아보기 • 출력 부분이나 로직 안에서 사용해야 하는 변수를 다른 변수와 혼동하여 잘못 사용하는 경우 • 반복문에서 반복변수를 사용해야 하는데 기준 변수를 사용하거나 변수 이름 자체가 비슷할경우 4. 파이썬 자동 형 변환 조심하기 • / 연산 :..
• 복잡도 : 알고리즘의 성능을 나타내는 척도 • 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석 파이썬은 1초에 약 2000만 번 연산하는 것을 기준으로 생각함!! 1. 상수는 시간 복잡도 계산에서 제외한다. 2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. • 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 • 복잡도가 낮을수록 좋은 알고리즘임 • 빅오 표기법 (big-O notation) : 최악일 때의 연산횟수를 나타낸 표기법 • 가장 빠르게 증가하는 항만을 나타내는 표기법 (함수의 상한만을 표기) • 연산 횟수 = 3N^3+5N^2+1000000 -> O(N^3) : 최고차항만 남기고, 계수 날리기 • 주어진 데이터의 '개수..
Last update : 2023.06.27 # 기본 입출력 빠르게 하기 • import sys • input = sys.stdin.readline : 끝에 () 넣지 말 것!! • print = sys.stout.write : 끝에 항상 print(f'{}...{}...\n') 처리 - print가 무조건 string으로 받고, 끝에는 \n 붙여야함! 정리하자면 1. input()보다는 sys.readline()을 쓰자. 2. 빈 리스트에 append()로 추가하는 것보단 입력 받을 개수 만큼 초기화된 리스트에 인덱스를 이용해서 접근해서 그 위치에 직접 입력받자. 3. 줄바꿈 할때엔 print()가 아니라 '\n', for문 마다 출력하지 말고 문자열 변수에 저장해놓고 한 번에 출력하자. # lambd..
