전체 글
백준 1654: 랜선자르기 해설- python
✏️ 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ✏️ 풀이 이진탐색을 이용하는 문제다. 이진탐색에 대한 내용은 여기에서 랜선의 길이에 대해서 이진탐색을 시행한다. k,n= map(int, input().split()) line = [] for _ in range(k): line.append(int(input())) start = 1 end = max(line) while(start=n: start=mid+..
![[JS] alert, prompt, confirm](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbNP2sR%2FbtrscOzAfvz%2FU6D2wUcOJnoDr7OoPTGTt0%2Fimg.png)
[JS] alert, prompt, confirm
alert alert('test'); 모달창을 띄운다. prompt let result=prompt('나이', 23); alert(`나이:${result}`); 나이: 사용자에게 보여줄 문자열, 23: 입력필드의 초깃값 confirm let a=confirm('이건 확인취소버튼있음'); 확인누르면 True, 취소누르면 False를 반환한다.
5. 기저와 차원
✏️ 기저(basis) 벡터공간 V와 부분집합 W를 생각하자. (1) W가 일차독립이고, (2) V를 생성하면 V의 기저(basis)라 한다. * span(Ø)={0}이고, Ø는 일차독립이다. 즉, Ø는 점공간(zero vector space)의 기저이다. * R^n의 기본단위벡터 e1,e2,⋯,ene1,e2,⋯,en는 일차독립이고 R^n을 생성한다는 것을 알고있다. 따라서 이들은 R^n에 대한 기저인데 이것을 표준기저(standard basis)라 한다. 대체정리(Replacement Theorem) 대체정리의 따름정리들은 기저에 관한 수많은 성질들을 보여준자. 대체정리를 이해하는 것은 기저를 손쉽게 다루기 위한 준비운동이다. 이에 대한 증명은 추후에 추가하도록 하겠다. 대체정리는 정성적으로 아래와 같..
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