다 내꺼로

Python은 동적 타입 언어지만, 타입 힌트(Type Hint)를 통해 정적 타입 언어처럼 명시적인 타입 선언을 할 수 있습니다.이를 가능하게 해주는 핵심 도구가 바로 typing 모듈입니다.📌 왜 typing이 필요한가?코드 가독성 향상IDE 자동완성, 정적 분석 도구(MyPy) 지원대규모 협업에서 의사소통 명확화def add(a: int, b: int) -> int: return a + b이렇게 타입 힌트를 추가하면 함수가 어떤 입력과 출력을 기대하는지 명확하게 표현할 수 있습니다.📚 주요 타입 예시from typing import List, Dict, Tuple, Union, OptionalList[int] : 정수를 담는 리스트Dict[str, int] : 문자열 키, 정수 값 딕셔너리..

중복 제거 원리는 단순히 누적합 알고리즘에만 쓰이는 기법이 아닙니다.수학, 컴퓨터 과학, 알고리즘 전반에 걸쳐 "겹치는 영역을 조정하여 정확한 값을 계산하는 방법"으로 널리 사용됩니다.📌 중복 제거 원리의 핵심"겹치는 것을 한 번만 포함시키기 위해, 불필요하게 더해진 값을 빼주고, 과하게 빠진 값을 다시 더하는 것"이 원리는 포함-배제 원리(Inclusion-Exclusion Principle)의 구조를 기반으로 합니다.🧠 대표적인 활용 사례1️⃣ 누적합(Prefix Sum, 특히 2D, 3D 확장)2차원 누적합에서 사각형 구간 합을 구할 때, 다음과 같이 겹치는 부분을 제거합니다:sum = S[y2][x2] - S[y1-1][x2] - S[y2][x1-1] + S[y1-1][x..

1차원 배열의 누적합을 확장하면, 2차원 배열의 특정 영역에 대한 합도 빠르게 구할 수 있습니다.이때 사용하는 알고리즘이 바로 2D Prefix Sum (이차원 누적합)입니다.📌 2D Prefix Sum이란?이차원 배열의 좌측 상단부터 (y, x) 위치까지의 모든 값을 누적한 배열을 만들어 두는 기법입니다.예: 2D 배열 A가 있을 때,S[y][x] = (0, 0) ~ (y, x)까지의 합→ 직사각형 범위 (y1, x1) ~ (y2, x2)의 합은 다음과 같이 계산S[y2][x2] - S[y1-1][x2] - S[y2][x1-1] + S[y1-1][x1-1]이는 중복 제거 원리를 활용한 누적합 공식입니다.중복제거 원리 관련해서는 아래 링크에서 공부 가능하십니다. 2025.06.09 - [알고리즘/개념]..

배열에서 특정 구간의 합을 여러 번 빠르게 구해야 하는 상황, 코딩 테스트에서 정말 자주 나옵니다.이때 유용하게 사용되는 기법이 바로 Prefix Sum (누적합)입니다.📌 Prefix Sum이란?Prefix Sum은 배열의 각 위치까지의 누적합을 미리 계산해두고,이후에 특정 구간의 합을 O(1) 시간에 계산하는 알고리즘입니다.예: 배열 A = [3, 1, 4, 1, 5, 9]Prefix Sum 배열 S = [0, 3, 4, 8, 9, 14, 23]→ S[i]는 A[0]부터 A[i-1]까지의 합을 의미합니다.이렇게 해두면 구간 [i, j]의 합은 다음과 같이 계산할 수 있습니다:S[j+1] - S[i]💡 시간 복잡도 비교방식사전 처리구간 합 계산Brute ForceXO(N)Prefix SumO(N)O..