꾸준히 개발하자

세그먼트 트리란? 세그먼트 트리란 데이터의 합을 가장 빠르고 간단하게 구하거나 수정할 수 있는 자료구조이다. 보통 배열을 통해 데이터의 합을 구하려면 O(N)의 시간복잡도가 나오지만 트리 구조를 이용한 세그먼트 트리의 구간합은 O(logN)의 시간 복잡도가 나온다. 따라서 훨씬 빠른 속도로 구간합을 구할 수 있다는 사실을 알 수 있다. 그렇다면 어떻게 구간합을 구하길래 이렇게 빠른 시간안에 찾을 수 있을까? 세그먼트 트리를 이용하기 위해 먼저 주어진 값으로 세그먼트 트리를 만들어야 한다. 1. 구간 합 트리 만들기 만약 배열의 값이 다음과 같이 있다 해보자. i 0 1 2 3 4 5 6 7 A[i] 1 9 5 4 8 7 2 3 배열 A의 크기 N = 8이고, 세그먼트 트리를 이용해 이 배열의 구간합을 구..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 7. 6. 13:45

비트 마스킹이란? 정수의 이진수 표현을 자료구조로 쓰는 기법으로 0, 1로 true/false, on/off와 같은 상태를 나타내는 것이 가능하다. 비트 마스크의 장점 1. 빠른 수행시간 - 비트 마스킹은 bit연산이므로 거의 모든 연산이 O(1)의 시간 복잡도를 갖고 있다. 2. 간결한 코드 - 다양한 집합 연산을 비트 연산자를 이용하여 한 줄로 작성이 가능하다. 3. 작은 메모리 사용량 - 1bit로 상태 저장이 가능하므로 메모리 사용량이 적어 DP에 유리하다. 비트 연산자 비트 연산자 논리 의미 & AND 양쪽 비트가 모두 1인 경우에만 1, 나머지 모든 경우 0 | OR 양쪽 비트가 모두 0인 경우에만 0, 나머지 모든 경우 1 ^ XOR 양쪽 비트가 서로 다른 경우 1, 같은 경우 0 ~ NOT..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 6. 16. 20:47

boolean containsKey(Object Key) HashMap에 지정된 Key가 포함되어 있는지 알려준다. boolean containsValue(Object Value) HashMap에 지정된 Value가 포함되어 있는지 알려준다. boolean isEmpty HashMap이 비어있는지 확인한다. void clear() HashMap에 저장된 모든 객체를 제거한다. Object put(Object Key, Object Value) HashMap에 Key와 Value를 저장한다. 이때 기존에 해당 Key에 대한 Value가 존재했을 경우에 그 Value값을 반환하고 만약 새로운 Key와 Value가 저장된다면 null을 반환한다. Object remove(Object Key) HashMap에 지..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 5. 3. 14:20

프림 알고리즘 프림 알고리즘은 주어진 그래프에서 MST(Minimum Spanning Tree = 최소 신장 트리)를 찾는 알고리즘이다. MST란 모든 노드를 연결하는 트리 중 간선의 가중치의 합이 가장 작은 트리를 말한다. MST를 찾는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘 2개가 있는데 주어진 그래프의 노드의 개수보다 간선의 수가 훨씬 많을 때는 프림 알고리즘을 사용하는 것이 더 효율적이다. 프림 알고리즘은 다음과 같이 진행된다. 1. 어떤 노드를 방문해 방문처리를 하고 우선순위 큐에 노드와 연결된 간선들을 넣는다 (만약 간선의 도착지가 방문한 노드면 큐에 넣지 않는다) 2. 우선순위 큐는 자동으로 간선의 가중치를 기준으로 오름차순 정렬을 유지한다 3. 큐에서 빼낸 값은 가장 낮은 가중치를 갖..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 28. 18:16

해시법 해시법이란 data를 저장할 인덱스를 간단한 연산으로 구하여 검색, 추가, 삭제를 효율적으로 수행할 수 있는 자료구조이다. 해시법에는 data를 저장할때 key값과 함께 저장하는데 이 key값과 해시 함수(간단한 연산)를 통해 얻은 해시값을 index로 사용한다. 예를 들면 다음과 같다. 해시 함수 : key % 13 key 35 80 75 63 21 1 해시값 (index) 9 2 10 11 8 1 이렇게 key값을 해시함수에 넣어 얻은 해시값을 index로 해서 key값과 data값을 저장하면 된다. 위와 같이 해시값을 index로 하여 key값과 data를 저장하는 자료구조를 해시 테이블이라고 하고 그 안에 요소들을 버킷(bucket)이라고 한다. 해시 테이블에서 원하는 data를 찾으려면 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 22. 10:54

위상 정렬 위상 정렬은 그래프의 정렬을 의미한다. 이를 위해서는 그래프가 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 할 필요가 있다. DAG란 간선이 단방향이어야 하며, 사이클이 존재하지 않는(어떤 노드를 출발했을 때 다시 그 노드로 돌아올 수 없는)그래프여야 한다. 위상 정렬은 그렇게 어렵지 않다. 만약 아래와 같은 그래프가 있다고 하자. 동그라미 안에 있는 숫자는 노드의 번호이고 네모 안에 있는 숫자는 노드를 가리키는 간선의 개수이다. 간단하게 다음 규칙에 맞게 정렬을 해주면 된다. (BFS 방법) 1. 네모 안에 숫자가(노드를 가리키는 간선의 개수) 0인 노드들을 Queue에 넣어준다. 2. Queue에서 노드 하나를 빼서 방문한 뒤 해당 노드의 간..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 20. 13:47

이진 탐색 트리 이진 탐색 트리는 이진 트리의 한 종류로써 각 노드가 key 값을 가지고 있다. 모든 노드들은 왼쪽 서브트리에 자신보다 작은 key값을 갖고있는 노드들을 포함하고 오른쪽 서브트리에 자신보다 큰 key값을 갖고있는 노드들을 포함한다. 보통 삽입, 삭제, 검색 등이 O(logN)의 시간복잡도를 갖기 때문에 빠른 정렬, 검색이 가능하다. 또한 중위 순회를 하면 key값의 오름차순으로 노드를 탐색할 수 있다. 단점은 중복 key값을 가질 수 없고 트리가 편향되면 탐색 시간이 늦어진다. (트리가 편향되는 문제를 해결하기 위해 레드-블랙 트리 등의 균형잡힌 이진 탐색 트리가 만들어졌다) 이진 탐색 트리 구현 기본적으로 Tree 클래스를 만들고 내부에 Node 클래스를 만들어 구현한다. Node들은 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 18. 03:46

리스트란? 리스트는 데이터를 순서대로 나열해 놓은 자료구조를 말한다. 리스트는 선형 리스트와 연결 리스트로 나눌 수 있는데 선형 리스트는 데이터들이 메모리에서 배열처럼 연속적으로 저장되어있는 리스트를 말하고 연결리스트는 각각의 데이터들이 메모리에 연속적으로 저장되어 있지는 않지만 각각의 데이터 안에 다음 순서의 데이터의 위치가 저장되어있는 리스트이다. 선형 리스트 구현 선형 리스트는 배열과 같은 구조이기 때문에 1차원 배열을 통해 쉽게 구현할 수 있다. class Student{ String name; int no; Student(String s, int n) { name = s; no = n; } } class Main { public static void main(String[] args) throw..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 16. 17:01