전체 글
[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
[Java] abstract class vs interface
[Java] abstract class vs interface
2023.01.20abstract class에 대해 공부하다가 interface와의 차이점이 궁금하여 작성하였다. 추상 클래스(Abstract class) vs 인터페이스(Interface) 추상 클래스(Abstract class) 먼저 추상 클래스(abstract class)는 클래스 내에 추상 메서드가 하나 이상 포함된 클래스를 말한다. 클래스 안에 메서드가 하나 이상 있다면 그 클래스 앞에는 반드시 abstract 클래스명으로 표기되어야 하며 abstract와 final 키워드를 동시에 표기할 수 없다. 일반 클래스에서 추상 클래스를 상속을 받는다면 추상메서드가 있을 경우 모두 구현해주어야 한다. 인터페이스(Interface) 반면 인터페이스(interface)는 모든 메서드가 추상 메서드인 경우이다. 간단히 생각하..
[Java] stream vs for
[Java] stream vs for
2023.01.17이전에 한번 확인했던 내용이지만, 자바를 통해 프리코스를 수행하던 도중 다시 또 궁금증이 생기고 기억이 흐릿하여 작성해본다. 아마 자바를 공부해본 사람이라면 다 고민해봤을 내용이다. ※ 해당 내용은 우아한Tech 유튜브 채널의 "[10분 테코톡] 크리스, 로마의 stream vs for" 내용을 참고하였다 해당 영상의 자세한 내용은 https://www.youtube.com/watch?v=by8hb75i9X4 이 링크를 통해 보면된다. 코드 먼저 다음 코드는 Java 1부터 지원한 기본적인 for문이다. public static void main(String[] args) { List list = List.of(1, 2, 3, 4, 5); for (int i = 0; i < list.size(); i++..
[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, 오른쪽자식노드 = 부모노드 * ..
[Java] 3. Iterator
[Java] 3. Iterator
2022.08.17Iterator? Iterator는 컬렉션에 저장된 요소에 접근하는데 사용되는 인터페이스이다. Iterator의 구버전으로 Enumeration이 있고, 기능을 향상 시킨 ListIterator가 있다. iterator()는 Collection 인터페이스에 정의된 메서드이므로 List와 Set에도 포함되어 있다. Map Iterator 처리 Map 인터페이스를 구현한 컬렉션 클래스는 key와 value를 쌍으로 저장하고 있기 때문에 iterator()를 직접 호출할 수 없다. 대신 keySet()이나 entrySet()과 같은 메서드를 통해서 key와 value를 각각 따로 Set의 형태로 얻어 온 후에 다시 iterator()를 호출해야 Iterator를 얻을 수 있다. Iterator it = map..