1주차 확률과 통계 내용 정리 목차 Introduction to Probablity Set Theory (operations & relations) The definition of probability Introduction to Probablity 목차 Experiment Sample Space Event Experiment Experiment는 가능한 식별 가능한 모든 결과를 말한다. 모든 경우의 수를 다 세는 것을 설명하신듯. Sample Space $S$ 로 표기한다. 한 experiment에 대해 가능한 모든 결과들의 집합을 말한다. 주사위를 한 번 던질 때의 Sample Space는 다음과 같이 나타낸다. $$ S = {1, 2, 3, 4, 5, 6} $$ Event $E$ 로 표기한다. 조건..

아무래도 이미지를 다루니까 이미지에 대해 설명하지 않을 수 없다. 이미지는 픽셀들의 집합이고, 각 픽셀들은 색을 가지고 있다. 모든 색은 빨강, 초록, 파랑의 적절한 조화로 만들 수 있음을 알고있는가? 몰랐다면 알아두자. 모든 색은 빨강, 초록, 파랑을 적절히 섞어 만들 수 있다. 따라서 하나의 픽셀은 빨강, 초록, 파랑 3개로 나누어서 볼 수 있다. 이렇게 나누면 각각의 색깔은 하나의 숫자로 표현이 된다. 이 숫자는 0~255사이의 숫자로 255에 가까울수록 밝아지고, 0에 가까울수록 어두워진다. 즉, 각각의 숫자 자체는 밝기를 나타낸다. 앞으로 사용할 이미지들은 데이터 타입이 numpy.uint8 이다. 따라서 값이 uint8 범위를 넘어가버리면 오버플로우가 일어나서 이미지가 비정상적으로 변할 수 있..

[펜윅 트리] 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(BIT, Binary Indexed Tree)라고도 불린다. 펜윅 트리는 구간 트리에서 부분합에 대한 질의를 더 효율적으로 하기 위해 만들어졌다. 부분합을 통해 구간합을 구할 수도 있으므로 구간합에 대한 질의도 답할 수 있다. 단순히 부분합만 구한다고 하면 당연히 트리구조를 사용할 이유가 없지만, 원소를 변경할 때는 트리구조의 장점이 들어난다. 배열로만 부분합을 구현했다면, 배열의 원소가 바뀔때마다 O(N)의 연산을 해줘야한다. 하지만 펜윅트리는 이를 O(logN)만큼만 걸리게 함으로써 속도를 올린다. 펜윅 트리는 기존 구간트리에서 각 노드에 대해 right에 해당하는 자식 노드들을 죄다 지운 형태다. 이유는 부분합 자체가 배열의 ..

구간 트리(segment tree)는 이미 존재하는 자료들(정렬되지 않음)을 전 처리한 후, 특정 구간에 대한 질의(query)를 효율적으로 답하는 자료구조이다. 물론 작성하려는 부분은 컴퓨터 공학에서 다루는 구간 트리 와는 구현 방식을 비슷하지만 엄밀히 따지면 다른 자료구조로 그저 알고리즘 대회에서 사용되는 구간 트리를 다룰 것이다. 특정 구간에 대한 질의는 그 형식이 다양하다. 예를 들어 특정 구간에 대한 합이 될 수도 있고, 특정 구간에 대한 최솟값 혹은 최댓값이 될 수도 있다. 이를 배열에서 구현하게 되면 특정 구간을 순회하면서 답을 내야 하기 때문에 질문 하나에 대해 O(N)의 시간이 걸리게 된다. 구간 트리는 이진트리로 구현하며, 루트 노드는 모든 구간 [0, n-1]을 의미하고 left는 [..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 로직 자체는 떠올리기 쉬웠다. i번째 비행기가 1~gi 까지 도킹할 수 있을 때, gi부터 차례대로 보면서 자리가 남아있으면 채우면 된다. 즉, 도킹할 수 있는 구간중 게이트 번호가 가장 큰 수를 먼저 고르면 가장 많은 비행기를 도킹할 수 있다. 만약 그렇지 않으려면, 다른 순서로 도킹하는 방법이 위 방법보다 더 많은 비행기를 도킹시킬 수 있음을 보이면 된다. 도..

1. Lower Bound lower_bound는 이름에서 알 수 있듯, 하한선을 의미한다. 레퍼런스에 있는 std::lower_bound는 찾고자 하는 value와 같거나 더 큰 값을 찾는다고 되어있다. Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found. 즉, value 이상인 값이 처음으로 나오는 위치를 찾는 것이다. 다음은 lower_bound를 구현한 코드이다. #include using namespace std; int a[10] = {1, 1, ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 해답이 너무 뻔했다. 왼쪽에서 오른쪽으로 가는 경로는 여러개 있다. 문제는 한번 지나간 점은 다시 지날 수 없다는 것인데, 이 점이 핵심이 된다. 경로가 서로 겹쳐질 수 없기 때문이다. 따라서 경로를 하나의 실로 표현을 하자면, 위부터 차곡차곡 쌓아나가야 경로를 최대한 많이 만들 수 있다. 하나라도 겹쳐지는 순간 미래에 경로를 만들 때 문제가 될 수 있기 때문이다. 결론적으로 시작점을 맨 위부터 아래방..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전www.acmicpc.net도저히 어떻게 풀어야할지 감을 못잡았다. 찾아보니 페이지 교체 알고리즘과 관련이 있다는 것을 알았다.  Belady algorithm페이지 교체 알고리즘이란 메모리에 페이지를 효율적으로 올리기 위해 나왔다.페이지를 메모리에 올리는데 비용이 많이 들기 때문이다.   물론 메모리에 몇 종류의 페이지를 올려놓고, 같은 페이지가 나오면 메모리에서 가져다 쓰면 된다.문제는 메모리에 올라와 있는 페이지 말고 새로..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 이 문제의 핵심은 무게들의 합으로 만들 수 없는 무게들 중 가장 작은 값을 원한다는 것이다. 즉, 굳이 모든 무게들의 조합을 구하지 않아도 됨을 암시하고 있다. 작은 무게들의 조합부터 따져야하기 때문에 무게를 기준으로 추들을 먼저 정렬하자. 먼저 누적합으로 접근해보자. 0번째 추부터 k번째 추까지 만들 수 있는 무게의 조합들을 0부터 k까지의 합으로 알 수 있을까? 그럼 0번째 추의 무게가 1, 1번째 추의..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 냅색이긴 한데.. 느낌이 달랐다. 이 문제의 핵심은 가방 하나에 넣을 수 있는 보석들 중, 가장 가치가 높은 보석을 넣어야한다는 것이다. 먼저 떠올린 해법은 가방 하나에 보석 전체를 순회하면서 가장 가치가 높은 것을 넣는 것이었지만, 이는 O(N*K)이고 N과 K는 둘다 300,000이 최대이므로 TLE가 난다. 가방을 하나씩 잡고 검사..