Algorithm
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)
2023.02.14신장 트리(Spanning Tree)? Spanning Tree는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 최소 신장 트리(MST, Minimum Spanning Tre..
[Algorithm] 백트래킹(BackTracking)
[Algorithm] 백트래킹(BackTracking)
2023.02.14백트래킹? 백트래킹은 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS는 큐의 크기가 매우 커질 수 있고 속도도 차이가 없기 때문에 경우의 수 구하기는 일반적으로 DFS가 편리하다. 출처: 나무위키 DFS & 백트래킹 백트래킹은 DFS를 사..
[Algorithm] 비트마스킹(bitmasking)
[Algorithm] 비트마스킹(bitmasking)
2023.02.10비트마스킹? 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비트 마스크를 이용하면 더 빠른 수행시간, 간결한 코드, 적은 메모리 사용의 효과를 얻을 수 있다. 비트 연산자 a & b: AND 연산 a | b: OR 연산 a ^ b: XOR 연산 ~a: NOT 연산 a > b: a를 b비트 만큼 오른쪽으로 시프트 집합 표현 비트마스크를 이용하면 집합을 쉽게 표현할 수 있다. 원소 추가 현재 상태 cur이 있을 때, p번째에 원소를 추가한다고 하면 다음과 같다 cur = cur | (1
[Baekjoon] 17298: 오큰수
[Baekjoon] 17298: 오큰수
2022.12.06문제 각 원소 A_i에 대해 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 구하는 문제이다. (없을 경우 -1) 예를들어 3 5 2 7 이라는 수열이 있으면, 3의 오큰수는 5, 5의 오큰수는 7, 2의 오큰수는 7, 7의 오큰수는 없으므로 5 7 7 -1 이라는 결과가 나오게 된다. 풀이 내 풀이 import sys input = sys.stdin.readline n = input() arr = list(map(int, input().split())) result = [0] * len(arr) stack = [0] for i in range(1, len(arr)): while stack and arr[i] > arr[stack[-1]]: result[stack.pop()] = arr..
[Baekjoon] 3190: 뱀
[Baekjoon] 3190: 뱀
2022.10.23문제 어릴 때 많이 했던 뱀 게임을 구현하는 문제이다. 풀이 내 풀이 import sys from collections import deque n = int(sys.stdin.readline()) apple_count = int(sys.stdin.readline()) board = [[0 for i in range(n)] for i in range(n)] board[0][0] = 1 for i in range(apple_count): r, c = map(int, sys.stdin.readline().split()) board[r-1][c-1] = 2 directs = deque([]) for i in range(int(sys.stdin.readline())): s, d = sys.stdin.readlin..
[Baekjoon] 11054: 가장 긴 바이토닉 부분 수열
[Baekjoon] 11054: 가장 긴 바이토닉 부분 수열
2022.10.19문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * n for i, v in enumerate(seq): for j in range(i-1, -1, -1): if seq[j] v: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 이 문제는 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제에서 변형된 문제이다. 아이디어는 11053번 문제..
[Baekjoon] 1912: 연속합
[Baekjoon] 1912: 연속합
2022.10.19문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [0] * n dp[0] = arr[0] for i in range(1, len(arr)): dp[i] = max(dp[i-1] + arr[i], arr[i]) print(max(dp)) 이 문제는 단순하게 생각하여 현재까지 합들보다 현재 값이 크면 시작점을 현재 인덱스로 바꾸면 해결되는 문제이다. 이 문제에선 다음을 고려하여 풀이를 진행하면 해결법이 생각날 것이다. 음수 값이 포함되어도 합이 최대 일 수 있다는 점 그렇지만 음수는 합에 영향을 준다는 점 (모두 0 이상인 수라면 전체 합이 최대이다) 한 번 다음 ..
[Baekjoon] 11055: 가장 큰 증가 부분 수열
[Baekjoon] 11055: 가장 큰 증가 부분 수열
2022.10.13문제 가벼운 11053: 가장 긴 증가하는 부분 수열에서 변형된 가벼운 dp 문제이다 풀이 내 풀이 import sys n = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = seq[:] dp[0] = seq[0] for i, v in enumerate(seq): for j in range(i-1, -1, -1): if seq[j] < v: dp[i] = max(dp[i], v+dp[j]) print(max(dp)) 해당 문제는 제일 큰 수의 합을 기억하며 나아가는 해법을 찾아가야 한다. 처음 제출했을때 dp 리스트를 모두 0으로 채워놓고 시작했는데, 현재 값보다 작은 값이 발견이 안됐을 때 0으로 처리되어..
[Data Structure] 세그먼트 트리(Segment Tree)
[Data Structure] 세그먼트 트리(Segment Tree)
2022.09.08세그먼트 트리? 여러 개의 데이터가 존재할 때 특정 범위의 합을 구하는데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진트리의 형태이다. 0 1 2 3 4 5 6 7 8 9 5 6 9 3 8 2 5 1 4 7 위의 데이터에서 1부터 7까지의 합을 구한다 했을 때, 일반적으로 데이터를 하나씩 돌면서 더하면 O(N)의 시간이 걸린다. 하지만 세그먼트 트리를 사용하면 O(logN)의 시간에 구할 수 있다. 구현 세그먼트 트리 생성 먼저 전체 원소를 더한 값을 최상단 노드에 넣는다. 이때, 최상단 노드의 인덱스는 1을 부여한다. 트리를 구현하다보면 알겠지만, 양쪽 자식노드의 인덱스를 부여할 때 0부터 시작하는 것보다 1부터 시작하는 것이 편하다. 왼쪽자식노드 = 부모노드*2, 오른쪽자식노드 = 부모노드 * ..
[Data Structure] 이진 탐색 트리(Binary Search Tree)
[Data Structure] 이진 탐색 트리(Binary Search Tree)
2022.08.17이진 탐색 트리(Binary Search Tree)? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. 각 노드에 중복되지 않는 키가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다. 이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다. 이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다. 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만..
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap)
2022.08.17우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐의 요소는 모두 우선순위를 가지고 있으며, 우선순위가 같은 경우에는 큐의 순서에 따라 처리한다. 우선순위 큐는 여러 방식으로 구현할 수 있지만 힙(heap)이 가장 효율을 보이기 때문에 일반적으로 힙을 이용하여 구현한다. 방식 시간 복잡도 배열 O(N) 연결 리스트 O(N) 힙 O(logN) 힙(heap) 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드는 자식노드 사이에 대소관계를 가지고 있다. 중복된 키를 허용한다. 힙의 종류 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙 최소 힙(min heap): ..