분류 전체보기
4. 일차종속과 일차독립
✏️ 일차종속(Linearly dependent)과 일차독립(Linearly independent) 벡터공간 V의 부분집합 S에 대하여 a1u1+a2u2+...+anun=0을 만족하는 유한개의 서로 다른 벡터 u1, u2...un ∈과 적어도 하나는 0이 아닌 스칼라 a1, a2,...,an이 존재하면 집합 S는 일차종속이라한다. 이때 S의 벡터 또한 일차종속이다. 벡터공간의 부분집합 S가 일차종속이 아니면 일차독립이다. 이때 S의 벡터 또한 일차독립이다. ✏️ Example(작성중) 1. 다음 정리를 증명하라. " V는 벡터공간이고 S1⊆S2⊆V이다. S1이 일차종속이면 S2도 일차종속이다." 2. 명제의 참과 거짓 판명 (a) 집합 S가 일차종속이면 S의 모든 벡터는 (S의) 다른 벡터의 일차결합이다..
3. 일차결합(Linear combination)과 Span
✏️ linear combination V는 벡터공간이고 S는 V의 공집합이 아닌 부분집합이라고 하자. 유한개의 벡터 u1, u2, u3..., un ∈ S와 스칼라 a1, a2, ...,an에 대하여 다음을 만족하는 벡터 v∈V는 S의 일차결합이라고 한다. v=a1u1 + a2u2 + ... + anun 이때 v는 벡터 u1, u2...un의 일차결합이고 a1, a2...,an은 이 일차결합의 계수(coefficient)이다. ✏️ Span Span(S)는 S의 벡터를 사용하여 만든 모든 일차결합의 집합이다. 편의를 위해 span(Ø)={0}으로 정의한다. ✏️ Example 명제의 참과 거짓 판명 (a) 영벡터는 공집합이 아닌 임의의 (벡터에 대한 )집합의 일차결합이다. > True. 일차결합의 정의..
![[알고리즘] Lower Bound와 Upper Bound](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcdaiNd%2FbtrscOrNAc5%2FrFozFBsAqSggsTtiehn3uk%2Fimg.png)
[알고리즘] Lower Bound와 Upper Bound
✏️ 무엇인가? Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다. 이진탐색(Binary Search)가 '원하는 값을 찾는 과정' 이었다면 Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고, Upper Bound는 '원하는 값이 나오는 마지막 위치를 찾는 과정'이다. Array = [1, 1, 2, 2, 3, 4, 4, 4, 6] 이런 리스트가 있에서 Lower Bound로 4를 찾는다면 4가 처음 나오는 인덱스인 5가 Output이 될 것이고, Upper Bound로 찾는다면 4가 마지막으로 나오는 인덱스인 7이 Output이 될 것이다. ✏️ 구현과정의 고민 사실 선형 탐색으로 구현하면 바로 해결되지만 기왕이면 O(N)보다는 O(lgN)이 좋지 않겠나..
백준 10816: 숫자카드 2 해설- python
✏️ 문제 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 아래는 10815에서 만들어쓴 이진탐색 함수이다. def BS(array, target, start, end): if start > end: return 0 mid=(start+end)//2 if array[mid]==target: return 1 elif array[mid]>target: return BS(array, target, start, mid-1) else: return BS(array, targe..
백준 10815: 숫자카드 해설- python
✏️ 문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 1920 수찾기 문제와 완전하게 동일한 문제였다. 해당 문제의 해설과 이진탐색에 대한 설명은 여기를 참고 (Python) N=int(input()) card=list(map(int,input().split())) card=sorted(card) M=int(input()) target_list=list(map(int,input().split())) def BS(array, target, start, end): if..
Binary Search (이진탐색) 알고리즘
✏️ 이진탐색알고리즘의 작동방식 이진탐색은 정렬된 리스트에서 특정 요소를 찾는 알고리즘이다. 분할(Devide) 리스트를 중간값을 기준으로 두개의 리스트로 분할한다. 정복(Conquer) - 검색할 숫자 중간값 이면 중간값 뒤의 리스트에서 검색할 요소를 찾는다. - 검색할 숫자 == 중간값 이면 값을 리턴한다. ✏️ 이진탐색알고리즘 구현 (Python) 재귀적 구현 def BS(array, target, start, end): if start>end: return None mid=(start+end)//2 if array[mid]==target: return mid elif array[mid]>target: return B..
2. 부분공간(Subspace)
✏️ subspace 벡터공간 V의 부분집합 W를 생각하자. W가 V상에서 정의된 덧셉과 스칼라곱에 대해 그 자체로 벡터공간이 된다면 이때 W를 V의 Subspace라고 한다. 모든 벡터공간 V에 대하여 V와 {0}은 부분공간이다. 특히 {0}은 'zero subspace'라고 한다. W가 V의 부분공간이기 위한 필요충분조건은 다음 세가지 조건을 만족하는 것이다. (1) 0 ∈ W (2) 모든 x ∈ W, y ∈ W에 대해서 x+y ∈ W 이다. (덧셈에 대하여 닫혀있다. closed under addition) (3) 모든 c ∈ F와 모든 x ∈ W에 대하여 cx∈ W이다. (스칼라 곱에 대해 닫혀있다. closed under scalar multiplication) ✏️ Example 명제의 참과 ..
1. 벡터공간 (Vector Space)
✏️ 사전정의 지금부터 사용하는 '벡터'라는 단어는 유향성분 벡터가 아닌 벡터공간의 원소를 가리키는 개념으로써 사용한다. 여기서 벡터공간의 field F는 주로 실수집합 R 또는 복소수 집합 C이다. ✏️ vector space field F에서의 벡터공간(vector space) 또는 선형공간(linear space) V는 다음 8가지 공리를 만족하는 두 연산, 합(sum)과 스칼라 곱(product)를 가지는 집합이다. (VS1) 모든 x,y ∈ V에 대하여 x+y = y+x 이다. (덧셈의 교환법칙) (VS2) 모든 x,y,z ∈ V에 대하여 (x+y)+z = x+(y+z) 이다. (덧셈의 결합법칙) (VS3) 모든 x ∈ V에 대하여 x+0 = 0+x = x 인 0∈V가 존재한다. 이 0을 영벡터..
백준 12015: 가장 긴 증가하는 부분 수열 2- python
✏️ 문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ✏️ 풀이 11053 가장 긴 증가하는 부분 수열 1과 뭐가 다를까? 다른 것은 단 하나. N의 조건 범위이다. 11053에서는 1
백준 11053: 가장 긴 증가하는 부분 수열 해설- python
✏️ 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✏️ 풀이 LIS(Longest Increasing Subsequence)라는 유명한 DP문제이다.만약 A={6, 2, 5, 1, 7, 4, 8, 3} 가 있을때 LIS는 {2, 5, 7, 8}이 된다. 증가하는 수열은 {2, 5}, {2, 7} 등 많지만 그 중 가장 긴 것이 LIS가 된다. - dp[i]를 전부 1로 초기화했다. LIS의 길이는 기본적으로 1은 될 것이기 ..