CS
[Algorithm] 최소 신장 트리 Minimum Spanning Tree
Minimum Spanning Tree(MST) MST(Minimum Spanning Tree)에 대해 알아보기 전에 Spanning Tree가 무엇인지 부터 알아야 한다. Spanning Tree란 1. 그래프의 모든 정점을 포함 2. 간선의 수가 가장 적음(n-1개) 3. 사이클이 없음 인 트리의 특수한 형태이다. 위의 두 조건을 만족하는 경우는 여러가지 이므로 하나의 그래프에는 많은 신장 트리(spanning tree)가 존재할 수 있다. 이는 BFS, DFS를 이용하여 찾을 수 있다. 그렇다면 MST는 무엇일까 MST는 위에서 설명한 spanning tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비..
[BaekJoon] 백준 18870번 좌표 압축
[BaekJoon] 백준 18870번 좌표 압축 문제: https://www.acmicpc.net/problem/18870 내코드 처음 문제를 풀었을 때 시간초과가 났다. 이유가 뭘지 고민하다가 검색해보니까 다른 사람도 나와 같이 풀어서 시간 초과가 난 경우가 많았다.(역시 사람 생각하는건 다 똑같..) 문제는 index 메서드였다. index 메서드는 O(N)의 시간 복잡도를 가지기 때문에 for문 안에서 N*N이 되어 시간이 오래 걸리는 거였다. # 틀린 코드 # BaekJoon18870.py N = int(input()) arr = list(map(int, input().split())) sorted_arr = sorted(list(set(arr))) for i in range(N): arr[i] ..
[BaekJoon] 백준 2630번 색종이 만들기
[BaekJoon] 백준 2630번 색종이 만들기 문제: https://www.acmicpc.net/problem/2630 내코드 재귀로 푸는 쉬운 문제였다. 배열 정보를 받아서 한변의 길이 & x 좌표 & y 좌표 이렇게 3개의 값으로 사분면 모두를 돈다. 만약 특정 사분면의 모든 값이 같다면 더이상 자를 필요가 없으므로 해당 색상 + 1 을 해주고 해당 사분면을 확인하는 것을 종료하고 만약 특정 사분면의 모든 값이 같지 않다면 한번더 4등분해서 들어간다(재귀). def checkSame(n, x, y): global arr value = arr[x][y] for i in range(n): for j in range(n): if arr[x + i][y + j] != value: return False ..
[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜
[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜 문제: https://www.acmicpc.net/problem/1620 내코드 처음엔 무작정 배열에 넣어풀어봤다. 역시나 시간초과가 났다. N, M 최대값이 100,000인데 python의 list 자료형에서 index 메서드의 시간 복잡도가 O(n)이라서 총 O(M*N)의 시간 복잡도가 나오기 때문인가보다. 1억당 1초라 하면 100,000 * 100,000를 게산하면 1억을 훌쩍 넘겨버린다. # 틀린코드 N, M = map(int, input().split()) arr = ["" for _ in range(N)] for i in range(N): arr[i] = input() for _ in range(M): question = inp..
[BaekJoon] 백준 1074번 Z (Python)
[BaekJoon] 백준 1074번 Z 문제: https://www.acmicpc.net/problem/1074 내코드 처음에 생각한 방식은 다음과 같다. 1. 한변 길이가 4이상이면 나눠서 재귀로 돌기 2. 한변 길이가 2이면 r, c에 맞는 위치가 있는지 확인하고 없으면 다음 사분면 돌기 하지만 이렇게 하면 시간 초과가 났다. # 잘못 푼 코드 # BaekJoon1074.py def solv(n, x, y): global result if n == 2: if y == r and x == c: print(result) exit() elif y == r and x+1 == c: print(result + 1) exit() elif y+1 == r and x == c: print(result + 2) ex..
[Algorithm] Hash table
Hash Table 이란? (key, value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다는 장점이 있다. 해시 테이블이 빠른 검색 속도를 제공하는 것은 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. Ex) (key, value) = ("John Smith", "521-1234")를 크기가 16인 해시 테이블에 저장하면, 먼저 index = hash_function("John Smith") % 16으로 index를 구해서 array[index] = "521-1234"로 저장한다. 평균 시간 ..
[Algorithm] 이진 힙 Binary Heap
이진 힙이란? 이진힙은 우선 순위 큐를 위해서 만들어진 완전 이진 트리의 한 종류이다. 즉, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조다. 이진 힙은 힙 중에서 가장 널리 쓰이며 힙의 특징(ex. 최대힙의 경우 부모 노드는 자식 노드보다 값이 커야 한다)을 만족한다. 참고로 이진 탐색 트리에서는 중복된 값을 허용하지 않지만, 힙 트리에서는 중복된 값을 허용한다. 종류 최대 힙 max heap: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 min heap: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 일반적으로 배열을 이용해서 구현한다. 구현을 쉽게 하기 위해서 배열의 첫 번째 인덱스인 0은 사용되지..
[Algorithm] Red Black Tree
레드 블랙 트리 (Red Black Tree)란? 레드블랙 트리는 지난번에 포스팅했던 트리에서 이어진다. 균형 이진 탐색 트리의 예시에서 레드블랙 트리를 언급했었고, 상당히 내용이 있는 이론이기 때문에 새로운 포스팅으로 옮겼다. 따라서 이진 탐색 트리에 대해서 안다고 가정하고 이어서 작성해보려고 한다. 특징 모든 노드는 빨간색 또는 검은색이다. 루트 노드는 검은색이다. 잎 노드는 검은색이다. (NIL 노드) 빨간 노드의 자식은 모두 검은색이다. (레드 노드는 연달아 나타날 수 없다.) 루트 노드에서 모든 잎 노드 사이에 존재하는 검은색 노드의 수는 모두 동일하다. 구현 탐색의 경우 기존의 BST와 동일하게 해주면 된다. 하지만 노드의 삽입과 삭제에서 문제가 발생한다. 트리의 균형이 유지가 안되기 때문이다..