백준 32162번: n, 3n, 5n
문제 요약서로 다른 양의 정수로 구성된 증가 수열 중, 다음 조건을 만족하는 사전순으로 최소인 수열을 찾는 문제입니다:임의의 양의 정수 n에 대해, n, 3n, 5n 중 정확히 하나만 수열에 등장한다.입력: 테스트 케이스 T개, 각각 인덱스 i (1 ≤ i ≤ 100,000)출력: 각 i번째 수열 원소 ai"사전순 최소"란?두 수열을 앞에서부터 비교할 때, 처음으로 다른 위치에서 더 작은 값을 가진 수열이 사전순으로 앞섭니다.수열 A: [1, 2, 4, ...]수열 B: [1, 2, 5, ...]→ 3번째 위치에서 4 즉, 가능한 한 작은 수부터 그리디하게 선택하되, 조건을 만족해야 합니다.수열 생성 예시1부터 차례로 확인하며 선택 가능 여부를 판단:1 선택 → n=1일 때 {1, 3, 5} 중 1 선택..
2025. 10. 11.
Python `pow()` 3항 형태와 모듈러 거듭제곱 최적화
모듈러 거듭제곱이란?기본 개념모듈러 거듭제곱은 큰 지수 계산 결과를 특정 수로 나눈 나머지를 구하는 연산입니다.(a^b) mod m예를 들어, 2^10 mod 1000을 계산하려면:일반적 방법: 2^10 = 1024 → 1024 % 1000 = 24Python: pow(2, 10, 1000) → 24왜 필요한가?큰 지수를 계산할 때 문제가 발생합니다:# ❌ 이렇게 하면 안 됩니다result = (2 ** 1000000) % 1000000007 # 메모리 폭발!# ✅ 올바른 방법result = pow(2, 1000000, 1000000007) # 빠르고 안전pow(a, b, m)의 동작 원리정의pow(a, b, m) # (a^b) mod m을 반환제약 조건:a, b, m은 모두 정수m ≠ 0b 일 때..
2025. 10. 3.
군론(Group Theory)
개요군론은 “대칭”을 수학적으로 다루는 도구다. 핵심은 한 집합과 그 위의 이항연산이 네 가지 조건(닫힘, 결합법칙, 항등원, 역원)을 만족하는지 확인하는 것.1. 필요한 배경지식기초 수학: 집합, 함수, 나눗셈, 소수, 최대공약수.논리: 증명 구조(가정 → 전개 → 결론).선택: 선형대수(행렬, 벡터공간). 표현론 입문 시 유리.2. 학습 순서와 핵심 개념2.1 군(Group)의 정의집합 $G$와 이항연산 $:G\times G\to G$가 다음을 만족하면 $(G,)$는 군.닫힘: $\forall a,b\in G,\ a*b\in G$결합법칙: $(ab)*c=a(b*c)$항등원: $\exists e\in G,\ \forall a,\ ea=ae=a$역원: $\forall a,\ \exists a^{-1},\..
2025. 9. 21.
