본문 바로가기

취업과 기본기 튼튼

 (76)
빽 투더 기본기 [알고&자구 7편]. 프림 알고리즘 그래프에서 최소 신장 트리를 만드는 알고리즘 중, 크루스칼과 더불어 유명한 프림(Prim) 알고리즘을 잠깐 정리해볼까 한다. 글 대부분의 내용은 프로그래밍 자료 저장소님의 블로그와 Michael Sambol의 유튜브를 참고하였다. 그래프에서 최소 신장 트리 만들기 프림 알고리즘은, 크루스칼 알고리즘 같이 어떤 그래프가 주어져있을 때, 이 그래프에서 최소 신장 트리 (Minimum Spanning Tree) 를 만드는 알고리즘이다. 최소 신장 트리에 대한 이야기는 이전 글인 크루스칼 알고리즘에 보면 나와있다. 프림 알고리즘을 위해서는, 역시 먼저 그래프가 주어져야 한다. 그리고 이 그래프에서, 우리는 정점과 인접 행렬에 대한 정보가 주어져야 한다. 프림(Prim) 알고리즘 알고리즘 알고리즘을 간단하게 정리..
빽 투더 기본기 [알고&자구 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였..
빽 투더 기본기 [알고&자구 3편]. 균형 트리 트리의 구조 특성상 탐색의 시간 복잡도가 '대체로' O(log n) 만에 가능하다. 따라서, 파일 시스템 등, 자료를 저장하거나 관리하는 시스템에서 많이 사용되곤 한다. 아무튼 트리를 사용한다는 것의 핵심은, 빠르게 접근 하기 위함이고, 이를 위해 '그냥 트리' 에서 여러 형태로 변모된다. 2편에서, 트리와 바이너리 서치 트리를 살펴보았다. 하지만 '지금까지의 트리'의 문제점은, 트리가 한 쪽으로 치우쳐져 있는 경우, 탐색의 시간 복잡도가 O(n) 이 된다는 것이다. 따라서, 치우쳐지지 않게, 즉 균형있게 트리를 만드는 것이 트리 구성에 핵심 이슈가 된다. 균형있는 트리. 이를 Balnaced Tree 라고 하며, 기존 트리에서 더 발전된 (균형을 잡아주는) 트리 종류는 다음과 같다. AVL Tree B..
빽 투더 기본기 [알고&자구 2편]. 자료구조 기초 기초 자료구조에 대해서 정리해 놓는다. 그닥 내용은 없지만, 그냥 한번 훑어보는 정도. 자료구조 개요 어떤 자료구조를 안다함은, 다음을 안다는 것이다. 정의 특징 / 특이사항 접근 시간 사용 상황 구분 위 자료구조들은 기초적인 것으로, 굳이 여기에 다 적진 않는다. 트리 좀 더 자세히 알아보고 싶은 것은 비선형구조의 트리다. 선형 구조와 다르게, 비선형 구조는 구조 특성상 여러 형태로 응용되기 때문에, 좀 더 알 필요가 있다. 정의 트리의 정의는 다음과 같다고 한다. 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있..
빽 투더 기본기 [알고&자구 1편]. 정렬 기본 정렬에 대해서 정리해 놓는다. 그냥 나 알아보기 쉽게, 직관적으로만 설명한다. 시간 복잡도 O(n^2) 정렬 선택 정렬 뒤에 가장 큰, 또는 가장 작은 값을 현재 인덱스 뒤부터 찾아, 앞의 인덱스부터 하나씩 채워나가는 정렬. # selection sort a = [3,1,2,5,4,6,7] size = len(a) for i in range(size): for j in range(i+1, size): if a[j] < a[i]: a[i], a[j] = a[j], a[i] print(a) 버블 정렬 뒤에 가장 큰, 또는 가장 작은 값을 뒤로 밀어밀어 보내, 마지막 인덱스부터 하나씩 채워나가는 정렬 # bubble sort a = [3,1,2,5,4,6,7] size = len(a) for i in r..

티스토리툴바