병아리 개발자의 실력 양성기

지도학습 중 이산변수인 category (class) 예측에 대한 평가 지표를 정리한다. 위 표는 confusion matrix 라는 것인데, actual class는 답, predicted class는 예측값이다. positive는 질병의 발병 등 무언가 중요한 사건을 말한다. TP와 TN는 모두 답을 맞춘 경우고, 그 외는 error로서, type I은 FP, type II는 FN이다. 즉, type I은 실제는 negative인데 positive로 잘못 예측한 경우이다. 예를 들어 질병이 없는데 질병이 있다고 예측한 것이다. type II는 실제는 positive인데 negative로 잘못 예측한 경우이다. 특히 이런 진단의 문제는 type II 오류를 늘리는 한이 있더라도(병이 있는데 병이 없다고..

비지도학습의 문제로, 어떤 데이터 포인트(관측) 집합이 있을 때 이를 생성했을 것으로 추정되는 분포를 구하는 문제가 있다. 이를 위해 모수적, 비모수적 방법이 연구되었는데, 아주 중요한 키워드 들이므로 하나씩 그 요점을 살펴본다. 모수적(매개변수적) 방법 데이터 집합에 의해 결정되는 적은 수의 매개변수에 의해 확률 분포가 조절됨. 선택된 밀도 함수가 데이터를 만들어낸 분포를 표현하기에 적절하지 않은 모델이었을 수 있음 GMM (Gaussian Mixture Model): 몇 개(k)의 가우시안 분포(모수는 mu, sig2)의 혼합(정확히는 선형결합. 그 가중치는 혼합계수인 pi)을 통해 분포를 구하며, 모수 세트(mu, sig2, pi)를 구하는 방법은 MLE, EM 이 있다. 비모수적(비매개변수적) 방..

N x N 체스말판이 있다. Queen N개가 서로 공격받지 않도록 말판에 배치하는 방법을 구하는 문제이다. 완전탐색, 백트래킹, dfs 등 여러가지로 문제유형을 부를 수 있다. 아래 소개하는 문제는 각각 방법들, 방법의 수, 그리고 조금 복잡한 조건이 더해질 경우의 방법의 수를 구하는 문제이다. https://leetcode.com/problems/n-queens/ N-Queens - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com https://leetcode..

서로 다른 동전으로 목표합을 구하는 방법의 수를 구하는 문제이다. 다만, 하나는 같은 동전 조합이면 순서가 달라고 1가지로 치고(조합), 나머지는 순열을 구하는 문제이다. 조합문제 https://leetcode.com/problems/coin-change-2/ Coin Change 2 - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 순열문제 https://leetcode.com/problems/combination-sum-iv/ Combination Sum I..

Linked List (singly) 도, Tree도 모두 DAG인 그래프의 일종이라 할 수 있다. 그래프의 사이클을 찾는 방법은 크게 방문된 노드를 기록해 두었다가 (O(n) space), 방문하려는 노드가 이미 방문한 적이 있다면 cycle 이 있다고 보고하는 방법과, Floyd가 제시한 two pointer를 사용하는 방법이 있다 (O(1) space). 이전에 전자에 대해 다루었으므로 오늘은 후자를 다뤄본다. 아무래도 공간을 사용한 전자가 더 속도가 빠르기는 하다. 사이클 여부 토끼는 2걸음씩, 거북이는 1걸음씩 걷는다. 사이클이 존재한다면 둘이 만날 것이고 그렇지 않다면 토끼가 먼저 종점에 도달할 것이다. # Definition for singly-linked list. # class ListN..

23:59, 00:00 의 분 단위 차이는 1분이다. 이런 시간들이 여러개 있을 때 그 최소 차이를 구하는 문제이다. https://leetcode.com/problems/minimum-time-difference/ Minimum Time Difference - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 시계 바늘처럼 일정 값에 도달하면 다시 원점으로 돌아가는 자료는 circular array로 모델링 할 수 있다. 아래 코드를 직접 보자. # https:/..

위상정렬 (topological sorting)은 DAG에서 DFS 탐색 순서대로 노드의 값을 나열하는 것을 말한다. DFS는 어느 source 노드를 먼저 탐색할지를 임의로 정할 수 있기 때문에 다양한 위상정렬이 있을 수 있지만 '탐색 순서대로' 라는 규칙은 맞아야 한다. 일반적인 해법은 각 노드에 대해 탐색 상태를 저장하는 배열을 하나 만들고, DFS를 하면서, 배열에 다음과 같이 값을 기록한다. state 0 (white) : 노드가 아직 처리되지 않음 state 1 (light gray) : 노드가 처리되는 중임(visiting) state 2 (dark gray) : 노드가 처리 완료 됨(visited) 처리 완료라는 말은 모든 후속 노드가 처리가 되었다는 뜻이다. 그럼 모든 후속 노드가 처리되..

많은 변형을 양산하는 구조이다. 컨셉을 제대로 이해할 필요가 있다. 결론적으로, DP 이지만 더 발전된 형태로 풀도록 하는 것이 요즘의 경향인 것 같다. 아래 array에서 가장 긴 subsequence (연속될 필요는 없는 배열 원소들의 부분 수열) 의 길이를 찾는 문제가 있다고 하자. nums = [5, 6, 7, 8, 1, 2, 3] https://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and..

아내에게 한도가 무한대인 카드와, 정해진 무게를 넘어서 담으면 찢어져 버리는 가방을 하나 주었다. 아내는 물건이 종류당 1개씩 있는 가게에 가방을 들고 가서 값어치 있는 물건들을 최대한 많이 가방에 담아서 나오려고 한다. 물건은 당연히 쪼갤 수도 없고, 정해진 용량을 넘을 수 없다. 이것이 바로 0/1 냅색 문제이다. 첫번째 해: top down DP stack overflow 때문에 일부러 @lru_cache는 쓰지 않고 table을 만들었다. Item = collections.namedtuple('Item', ('weight', 'value')) def optimum_subject_to_capacity(items: List[Item], capacity: int) -> int: # i: 1:i th i..

벽으로 둘러싸인 공간, 즉 방의 갯수를 구하는 Counting Rooms 라는 문제가 있다. https://cses.fi/problemset/task/1192/ CSES - Counting Rooms cses.fi 이는 DFS의 응용 형태로 푸는 것이다. DFS는 한 점에서 출발해 닿을 수 있는 미 방문점을 모두 방문하는 것이다. 방문할 때 마다 방문된 점을 표시하되 끝까지 방문이 되면 돌아온다. 이와 유사한 과정인 backtracking은 방문시마다 어떤 조건에 대해 확인하는 절차를 거쳐, 그 조건이 만족되지 않으면 방문을 종료하는 것이다. DFS에서 기본적으로 검증하는 조건은 바로 '방문여부'가 된다. 이미 방문된 것은 다시 방문하지 않는다. 이를 위해 방문된 노드에 대한 기호를 모아놓는 일을 set..