본문 바로가기

Study52

Disjoint Set (Union find) Disjoint set이라고도 하고 union find라고도 하는 이 방법은 어느 두 집합을 합치고, 어느 두 요소가 같은 집합에 존재하는지 빠르게 알 수 있게 하는 방법이다. Disjoint Set은 아래 두 연산을 구현한다. union(a,b)는 a가 속한 집합과 b가 속한 집합을 합치는 연산이다. find(a)는 a가 속한 집합을 반환하는 연산이다. 아래는 위 두 연산을 사용하였을 때의 예제이다. 1~5의 요소가 있다고 하자. 각 요소는 초기에 서로 다른 집합에 속한다. (1), (2), (3), (4), (5) 1이 속한 집합과 2가 속한 집합을 합치자. : union(1,2) 결과 : (1,2), (3), (4), (5) find(1) == find(2)는 true이어야 한다. find(2) =.. 2023. 5. 1.
Binary Heap (이진 힙) 힙은 아래 성질을 만족하는 Alomost complete binary tree이다. Max heap의 경우 parent node의 값은 child node의 값보다 크거나 같다. Min heap의 경우 parent node의 값은 child node의 값보다 작거나 같다. 아래의 모든 설명은 Max heap을 기준으로 한다. Max heap의 경우 tree 내의 모든 노드에 대해 parent node의 값은 child node의 값보다 작지 않다. 그래서 Max heap에선 root node의 값이 가장 크다. 값을 삽입하고 뺄 때도 이 성질을 유지하면 root에서는 항상 tree 내의 가장 큰 값이 존재하게 된다. Cpp의 priority queue를 사용해 본 적이 있는가? 어떤 값을 priority.. 2023. 1. 31.
Binary Search, 이진탐색 정렬된 배열에서 특정 값의 위치 찾기 아래의 정렬된 배열에서 6을 찾는다고 하자. ---------- 0123456789 지금은 배열 전체가 탐색 범위이다. 여기서 중앙에 있는 값과 목표로 하는 값(6)을 비교해 보자. 중앙에 있는 값은 index가 4인 값이다. floor((0 + 9)/2) = floor(4.5) = 4, arr[4] target 임으로 i.. 2023. 1. 6.
Metrics - Accuracy, Precision, Recall and F1-Score Accuracy (정확도), Precision(정밀도), Recall (재현율) 그리고 F1 Score는 Classification을 수행한 모델이 잘 동작하였는지 확인하기 위한 척도입니다. Confusion Matrix 예측값 Positive 예측값 Negative 실제값 Positive TP FN = Type II error 실제값 Negative FP = Type I error TN 우선 TP, FN, FP, TN에 대해 먼저 알아봅시다. 이 값들은 실제 참혹은 거짓인 값들에 대해 몇 개를 정확히 예측하였는지, 그렇지 않았는지 알려줍니다. TP, FN, FP, TN 값의 의미는 아래와 같습니다. TP : Positive라 예측한 것중 맞은 것 FP : Positive라 예측한 것중 틀린 것 TN :.. 2022. 10. 2.
Entropy, Information Gain 그리고 Decision Tree Entropy 정보이론에서 Entropy는 어떤 확률 p를 가진 정보를 전송하는 데에 필요한 비트 수의 평균값입니다. 예를 들어 동전을 던졌는데 앞면이 나왔는지, 뒷면이 나왔는지를 상대방에게 알려주려고 합니다. 2가지의 경우밖에 존재하지 않음으로 1bit (0, 1)로 나타낼 수 있습니다. 두 경우의 확률 값이 0.5 임으로 0.5*1 + 0.5*1 = 1로 엔트로피는 1입니다. 그런데 이는 동전의 앞면과 뒷면이 나올 확률이 둘 다 1/2이라는 가정하에 일어나는 일입니다. 만약 던졌을 때 앞면만 나오는 동전이 있다면 불확실성은 존재하지 않습니다. 이 경우 엔트로피는 0입니다. 엔트로피는 문제의 복잡도를 측정하는 척도이며, 클수록 불확실성이 높으며 문제가 복잡합니다. 엔트로피는 아래와 같이 정의됩니다. $.. 2022. 10. 1.
Python NaN Python 에서 nan 값을 다루는 법을 알아봅니다. NaN 이란? NaN 값은 ‘Not a Number’ 을 뜻합니다. 숫자가 아니라는 뜻이죠. 0을 0으로 나누거나 음수의 제곱근을 구하고자 하면 정상적인 값을 얻지 못할 것입니다. 그럼에도 반환값을 받아야 하는 경우 nan 값을 받게 됩니다. Python에서는 0/0 을 수항하면 Error를 출력하는데, 다른 언어나 python의 numpy 라이브러리를 사용하는 경우 nan 값이 반환되는 것을 볼 수 있습니다. # nan returned a = np.array([1,2,3,0,5]) b = np.array([1,2,3,0,0]) print(a/b) # [ 1. 1. 1. nan inf] nan 은 IEEE 754 라 하여 부동소수점 연산에 관한 표준.. 2022. 7. 4.
Cython으로 속도 향상 꾀하기 Preface Python을 사용하면 적은 코드로 쉽게 기능을 구현할 수 있지만, C나 Cpp와 같은 언어에 비해 느립니다. 많은 작업을 최적화가 잘 된 라이브러리를 사용하여 처리할 수도 있겠지만, 원하는 작업을 수행하는 라이브러리가 없어 순수 python 코드로 작성하는 경우도 많습니다. 작성한 python 코드에 의한 속도 저하는 작은 데이터를 처리할 때는 신경쓰이지 않지만, 데이터가 커질 수록 실행속도가 느린 작업에 의해 우리가 기다려야 하는 시간이 눈에 띄게 됩니다. 가정 약 57만개의 row와 2개의 column으로 이루어진 names.csv 파일이 있습니다. 두 column은 어느 장소의 이름이고, 하고자 하는 작업은 두 column에 대해 LCS (Longest Common Sequence).. 2022. 6. 30.
RDT RDT Reliable Data Trasfer Protocol Sender는 receiver의, receiver는 sender의 fsm state를 모른다. Interfaces of RDT rdt_send() called from above Passed data deleiver to receiver upper layer udt_sent() called by rdt to transfer packet over unreliable channel to receiver rdt_rcv() called when packet arrives on receiver deliver_data() called by rdt to deliver data to upper layer RDT 1.0 매우 단순 unreiliable cha.. 2022. 6. 24.
Android 간단한 RecyclerView 사용법 RecyclerView를 사용해보자. 참고로 이 예제는 View Binding을 사용하였다. 최종 결과물을 미리 보자면 아래와 같다. 1. RecyclerView가 추가될 위치에 삽입하기 먼저, xml 파일 상에서 원하는 위치에 RecyclerView를 추가한다. 나는 mainactivity에 추가할 것이기 때문에, activity_main.xml에 recyclerview를 아래와 같이 추가하였다. 2. 하나의 Row 디자인 만들기 RecyclerView 내부에 보여질 열(Row) view의 xml을 만들어 주자. 이 예제에서는 row_item.xml에 해당 파일을 만들어 주었다. 위 xml의 디자인은 아래와 같다. RecyclerView는 위 디자인의의 열에 적절한 값이 들어가고, 이것이 반복되는 꼴이.. 2022. 5. 24.
Next permutation, 다음 순열 구하기 어떤 순열이 주어져 있을 때 다음 순서의 순열을 구하는 알고리즘이다. 참고로 여기서 말하는 순서는 어떤 요소들로 순열을 만들고 이 순열들을 사전 순서대로 정리하듯 정렬하였을 때를 기준으로 한다. 예를 들어 어떤 1, 2, 3을 가지고 모든 순열을 만들고 이를 사전 순서대로 정리하면 아래와 같다. 123 132 213 231 312 321우리가 하고자 하는 것은 어떤 순열이 주어졌을 때 다음 순열을 구하는 것이다. 예를 들어 231 이 주어졌을 경우 312를 반환하는 것이다. Algorithm 어떤 순열을 arr라고 하자. arr[i] arr[i] 인 j 중 가장 큰 j를 구한다. swap(arr[i],arr[j]).. 2022. 4. 4.

티스토리툴바