Ch05. 정수론
이 부분은 백준 단계별 풀어보기_정수론 에서 유클리드 호제법 등을 사용했던 게 큰 도움이 되었다.
기초 내용은 초,중,고등학교 때 배웠던 내용을 복습하는 느낌이었다.
-
약수와 배수
-
소인수 분해
-
약수
-
이진법
-
유클리드 알고리즘 : 두 수의 최대공약수를 구하는 알고리즘
-
유클리드 호제법 증명
-
유클리드 알고리즘 백준 풀이 (백준-1934)
#유클리드 호제법 -> 최대공약수 -> 최소공배수 import sys input=sys.stdin.readline class UC: def read(self): self.n=int(input()) self.info=[list(map(int,input().split())) for _ in range(self.n)] def solve(self): for pb in self.info: r=float("inf") pb=sorted(pb) a=pb[0] b=pb[1] while r>0: r=pb[1]%pb[0] pb[1]=pb[0] pb[0]=r print((pb[1])*(a//pb[1])*(b//pb[1]),end='\n') uc=UC() uc.read() uc.solve()
-
Ch06. 경우의 수 세기와 비둘기집의 원리
-
경우의 수 : 일어날 수 있는 모든 사건의 수
-
합의 법칙
-
곱의 법칙
-
포함 - 배제의 원리
-
순열과 조합
순서를 고려 순서 고려 X 반복 허용 중복 순열 중복 조합 반복 불허 순열 조합 -
중복 순열 : n**r (n개 -> n개 -> n개 …)
-
중복 조합 : (n+r-1)C(r)
r개의 빈칸에 n-1개의 칸막이를 쳐서 총 n개의 공간을 만들어 각 공간에 있는 개수만큼 해당 원소를 추출하는 경우 ex. 1~9 까지의 자연수 중 중복을 허용하여 3개를 뽑아 숫자 10을 만드는 경우의 수
case 1 )
-
-
이항 정리
-
파스칼 항등식
특징 1.
특징 2.
-
비둘기 집의 원리 응용 : ex. 8명의 학생이 있다면 반드시 생일의 요일이 같은 2명의 학생이 있다.
Ch07. 점화관계
-
점화 관계 : 수열 {a(n)} 이 있을 때, a(n) 을 a(n-1),a(n-2), … , a(0) 에 관한 식으로 표현한 것.
-
점화 관계 푸는 법
점화관계는 시간 복잡도를 구하는 데 유용함 !
Ch08. 그래프론 (이산수학적 그래프 개념, cf. 자료구조)
- ‘인접하다’ : 정점끼리 연결되었을 때
- ‘근접하다’ : 정점과 변이 연결되었을 때
- 루프
- 다중그래프
- 방향 그래프
- 가중치 그래프
- 차수 : 점 v 에 근접하는 변의 개수
- 외차수 : 점 v 를 출발점으로 하는 변의 수
- 내차수 : 점 v 를 도착점으로 하는 변의 수
-
경로 : 같은 변을 두 번 이상 포함하지 않는 길
-
연결그래프 : 임의의 점 u,v 사이에 경로가 있는 그래프
-
완전그래프 : 모든 점 사이에 변이 있는 그래프
-
이분그래프 : 한 점은 v1 부분집합에, 한 점은 v2 부분집합에 있는 그래프 -> 분리 가능한 그래프
-
부분그래프
-
회로 : 한 점에서 출발하여 자기 자신으로 돌아오는 경로
-
오일러 경로 : 모든 모서리를 꼭 한번씩만 지나는 경로
-
오일러 회로 : 모든 모서리를 꼭 한번씩만 지나는 회로
- 오일러 회로 필요충분 조건 : 모든 차수가 짝수여야 한다
-
해밀턴 회로 : 모든 점을 꼭 한 번씩만 지나는 회로
-
인접 리스트
-
인접 행렬
- 정리 ) 만약 A 가 그래프의 인접 행렬이라면 A**n 의 i행 j열의 값은 V(i) 에서 V(j) 로 가는 길이 n짜리 길의 개수이다
