본문 바로가기

분류 전체보기

 (249)
빽 투더 기본기 [알고&자구 6편]. 크루스칼 알고리즘 그래프에서 최소 신장 트리를 만드는 알고리즘 중, 가장 유명한 크루스칼(Kruskal) 알고리즘을 잠깐 정리해볼까 한다. 글 대부분의 내용은 heejeong Kwon님의 블로그 와 나동빈님의 유튜브를 참고하였다. 그래프에서 최소 신장 트리 만들기 크루스칼 알고리즘은, 어떤 그래프가 주어져있을 때, 이 그래프에서 최소 신장 트리 (Minimum Spanning Tree) 를 만드는 알고리즘이다. 최소 신장 트리란, 어떤 그래프에서 각 정점간 간선을 1개씩만 선택하여, 결과적으로 모든 정점을 잇는 하나의 그래프(트리) 를 말한다. 정점이 n개 있다고 할 때, 간선은 n-1개가 된다. 그럼 이걸 왜하느냐? 대표적인 예로, 여러 도시가 있고, 각 도시간 도로를 깔 수 있는 경로와 비용이 이미 파악되어있다고 하자..
빽 투더 기본기 [알고&자구 5편]. 다익스트라 알고리즘 그래프에서 경로찾는 알고리즘 중, 가장 유명한 다익스트라(Dijkstra) 알고리즘을 잠깐 정리해볼까 한다. 글 대부분의 내용은 Chancethecoder님 블로그 와 허민석님 유튜브를 참고하였다. 한 점에서 다른 정점으로 가는 최단 경로 찾기 위 제목이, 다익스트라 알고리즘이 하는 일이다. 방향 혹은 무방향 그래프에서, 어떤 한 점에서, 다른 모든 점으로 가는 최단 경로와 거리(weight) 을 O(|V||E|) 만에 찾아서 반환한다. 이 때, 거리(weight) 는 모두 양수여야 알고리즘이 제대로 작동한다. 또, 정점(vertex)과, 인접 행렬(adjacent)이 입력으로 주어져야 한다. 알고리즘 알고리즘을 간단하게 정리하면 다음과 같다. 1. 시작점에서 모든 정점까지의 거리를 담는 배열 (dist..
빽 투더 기본기 [알고&자구 4편]. 해시 테이블 기본적인 자료구조들 중, 트리에 이어 또 하나 자세히 살펴볼만한 자료구조가 바로 해시 테이블이다. Ratsgo's blog 님의 정리된 내용을 가지고 간단히 요약해보려고 한다. 정의 key, value 형태로 자료를 저장하는 구조를 해시 테이블이라고 한다. 이 때, 테이블에서 인덱스 역할인 key를 만드는 함수를 해시 함수라고 하고, 본래 값에서 해시 함수를 먹여 해시 값(키)를 만드는 과정을 해싱이라고 한다. 특징 삽입, 삭제, 탐색에서 해시 충돌이 발생하지 않는다면, 시간복잡도 O(1) 을 보인다. 아래 다른 자료구조들과 비교해보았을 때, 매우 극적인 성능을 보이는 자료구조다. 자료구조 삽입 삭제 탐색 배열 O(n) O(n) O(1) 리스트 O(1) O(1) O(n) 트리 O(1) O(1) O(log..
[BOJ] 2493. 탑 문제 탑 (https://www.acmicpc.net/problem/2493) 풀이 1. 초기 접근 문제조건 해석 N 이 500,000만 이하로 주어진다고 한다. 즉 O(N) 또는 O(N log N) 안으로 풀어야 한다. 선형 탐색 한 번만 가능한 것이다. 알고리즘 주어진 예제 6 9 5 7 4 에서 앞의 인덱스부터 하나씩 탐색해나간다 했을 때, 현재 인덱스의 값의 올바른 정답이 무엇인지 차근차근 생각해보자. 맨 왼쪽 6은 수신하는 곳이 없으니 항상 0일 것이다. 9 도 마찬가지로, '지금까지' 9 보다 큰 값이 없었으므로, 값은 0이 된다. 5 에서는, 지금까지5 보다 큰 값인 9가 있었다. 따라서 값은 배열에서 9의 인덱스값인 1이 된다. 7도 마찬가지다. 지금까지 7보다 큰 값은 9였..
가설검정 단계 (지금까지) 유튜브 HSM - edu 통계 채널의 '손으로 푸는 통계', 27. Z검정의 한계(정규성,t,비모수검정의 출현+디시전트리) 에 나오는 강의 영상 중 하나로 한 눈에 봐보자. 요약하면, 일단 모수의 분산을 아느냐 모르느냐로, Z검정, T검정으로 나눈다. 모수의 분산을 알고, 표본 분포가 정규성을 만족하는 경우, Z검정을 한다. 모수의 분산을 모르고, 표본 분포가 정규성을 만족하는 경우, T검정을 한다. 일반적으로 정규성을 만족하지 않는 경우, 비모수 검정을 한다. 정규성을 만족한다는 말은, 말 그대로 정규분포를 따른다고 알려져있거나, 알려져 있지 않더라도, 데이터 개수 n이 30이상인 경우, 중심극한정리에 의해 정규본포를 따른다. 데이터 개수 n이 30 미만인 경우, 별도의 정규성 테스트를 ..
표본 분산은 왜 n-1로 나눌까? 유튜브에 HSM - edu 통계 채널의 '손으로 푸는 통계' 를 보면 잘 설명되어 있다. 주요 키워드들로 간단히 요약해보면, 표본을 뽑아서 무언가를 하는 목적은, 대부분 모수를 추정하기 위함이다. 표본에서 뽑은 통계값 (평균, 분산) 을 추정량 이라고 한다. 그 중에, 불편 추정량 (unbiased estimator) 이라는 말이 있는데, 추정량의 기댓값이 모수가 되는 추정량이라는 말이다. 즉, 표본 평균의 기댓 값 = 모수의 평균 표본 분산의 기댓 값 = 모수의 분산이 되면, 이 표본 추정량은 불편 추정량이라고 할 수 있다. 표본 평균의 기댓값은, 표본들을 가지고 평균을 내면 모수의 평균으로 딱 나오는 반면, 표본들을 가지고 분산을 내면 모수의 분산으로 딱 나오지 않는다. 즉, 표본 평균과 표본 분산은..
빽 투더 기본기 [알고&자구 3편]. 균형 트리 트리의 구조 특성상 탐색의 시간 복잡도가 '대체로' O(log n) 만에 가능하다. 따라서, 파일 시스템 등, 자료를 저장하거나 관리하는 시스템에서 많이 사용되곤 한다. 아무튼 트리를 사용한다는 것의 핵심은, 빠르게 접근 하기 위함이고, 이를 위해 '그냥 트리' 에서 여러 형태로 변모된다. 2편에서, 트리와 바이너리 서치 트리를 살펴보았다. 하지만 '지금까지의 트리'의 문제점은, 트리가 한 쪽으로 치우쳐져 있는 경우, 탐색의 시간 복잡도가 O(n) 이 된다는 것이다. 따라서, 치우쳐지지 않게, 즉 균형있게 트리를 만드는 것이 트리 구성에 핵심 이슈가 된다. 균형있는 트리. 이를 Balnaced Tree 라고 하며, 기존 트리에서 더 발전된 (균형을 잡아주는) 트리 종류는 다음과 같다. AVL Tree B..
빽 투더 기본기 [알고&자구 2편]. 자료구조 기초 기초 자료구조에 대해서 정리해 놓는다. 그닥 내용은 없지만, 그냥 한번 훑어보는 정도. 자료구조 개요 어떤 자료구조를 안다함은, 다음을 안다는 것이다. 정의 특징 / 특이사항 접근 시간 사용 상황 구분 위 자료구조들은 기초적인 것으로, 굳이 여기에 다 적진 않는다. 트리 좀 더 자세히 알아보고 싶은 것은 비선형구조의 트리다. 선형 구조와 다르게, 비선형 구조는 구조 특성상 여러 형태로 응용되기 때문에, 좀 더 알 필요가 있다. 정의 트리의 정의는 다음과 같다고 한다. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있..

티스토리툴바