Algorithms (5) 썸네일형 리스트형 명제 논리 진리표 p q p ∧ q p ∨ q p → q p ↔ q T T T T T T T F F T F F F T F T T F F F F F T T p이면 q이다(implies, if p then q) 오직 p인 경우에만 q이다(p if and only if q) 위 2가지를 제외하고는 진리값이 직관적입니다. p이면 q이다의 경우 ~(p ∧ ~q)입니다. p ↔ q의 경우 ~(p ∧ ~q) ∧ ~(q ∧ ~p)입니다. 나중에 2-sat 구현할때 필요한 내용인데, 저는 이를 모르고 구현하여 애먹었습니다. 정렬 정당성 증명 loop invariant를 이용한 정렬 알고리즘 정당성 증명 삽입 정렬 초기: arr[:1]은 정렬 되어 있다 유지: loop가 끝나면 arr[:i] 정렬되어있다. 종료: arr 정렬되어있다 버블 정렬 초기: arr[n-1:n] 정렬되어있다 유지: loop 끝나면 arr[i:n] 정렬되어있다 종료: arr 정렬 3273 두 수의 합 투포인터 정당성 증명 배열 arr이 정렬된 상태 int s = 0, e = n-1; for (int i = 0; i x임으로 .. segment tree 세그먼트 트리는 어떤 범위에 대한 쿼리를 효율적으로 대답해 줄 수 있는, 또 그러면서 수정도 가능한 자료구조 중 하나입니다. 아래와 같은 쿼리 2개를 생각해 봅시다. 1. 길이가 N인 어떤 수열 A에서 A[i]부터 A[j]까지의 합을 구하라 2. 길이가 N인 어떤 수열 A에서 A[i]를 v로 바꿔라 일반적인 경우 이 두 쿼리는 $O\left ( N \right )$으로 해결 할 수 있습니다. 그런데 구간 트리를 이용하면 $O\left ( logN \right )$으로 쿼리를 해결 할 수 있습니다. 위 그림과 같이 각 노드가 구간을 커버하면서 구간에 해당하는 값을 가지고 있는 형태를 세그먼트 트리는 가지고 있습니다. 1번이 루트 노트이고 아래로 2,3번을 자식 노드로 갖는점에 유의해주세요! 세그 트리를 구.. 거듭제곱 이항 계수 이걸 하루 왠종일 할줄은 몰랐다 연말에 하루종일 이항계수 공부하는 인생.... 아무튼 시작 오탈자가 있어 수정한다 우측 상단에 inv(n!)이랑 (n!)^p-2랑 합동이란 뜻이다 dp를 분할정복이라 적어서 수정예정 이전 1 다음
