자료구조
자료구조(Data Structure)란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법을 이야기 한다.
자료구조는 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다.
- 선형 자료구조 : 데이터가 일렬로 나열되어 있음.
* 배열 (Array)
* 연결리스트
* 스택
* 큐
- 비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음.
* 트리
* 그래프
배열
: 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조.
* 배열의 특징
- 데이터 접근이 용이.
- 데이터 삽입 / 삭제가 어려움 (뒤로 1칸식 밀어주어야함. 최악의 경우 O(n))
- 구조가 간단하여 프로그램 작성이 쉬움.
연결리스트
: 각 노드가 데이터와 포인터를 가지고 일렬로 연결되어있는 방식으로 데이터를 저장하는 자료구조.
* 연결리스트의 특징
- 배열과 반대되는 특징을 가짐.
- 데이터 접근이 느림.
- 데이터의 삽입 / 삭제 연산이 용이.
- 포인터를 위한 추가 공간 필요, 프로그램 작성이 어려움.
스택
- 삽입연산, 삭제연산이 한 방향에서 이루어지는 선형 자료구조.
- 한 방향에서 삽입과 삭제가 이루어지기 때문에 나중에 삽입된 데이터가 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조를 가진다.
- 스택에 데이터가 삽입될 위치를 Top이라고 한다.
큐
- 한 방향에서는 삽입연산이, 반대편에서는 삭제연산이 이루어지는 자료구조.
- 스택과 마찬가지로 선형 자료구조이다.
- 한쪽 방향에서 삽입이, 반대편에서 삭제가 이루어지기 때문에 먼저 삽입된 데이터가 먼저 삭제되는 선입선출(FIFO, First In First Out) 구조를 가진다.
- 데이터가 삭제될 위치를 Front / Head, 마지막 데이터가 삽입된 위치를 Rear / Tail이라 부른다.
- 양 방향에서 삽입연산과 삭제연산이 모두 이루어지는 큐를 덱(Deque)이라고 한다.
트리
: 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식관계로 표현된다.
- 트리는
이진트리
힙 (우선순위 큐)
인덱스 트리 (Segment Tree)
TopBottom 방식
static long makeTree(int node, int left, int right) {
//리프 노드
if(left == right) {
if (left <= N) {
return tree[node] = nums[left];
} else {
return tree[node] = 0;
}
}
//리프가 아니면 mid를 나누고, makeTree호출
int mid = (left + right) / 2;
tree[node] = makeTree(node*2, left, mid);
tree[node] += makeTree(node *2+1, mid + 1, right);
return tree[node];
}
static long query(int node, int left, int right, int qLeft, int qRight) {
if(qRight < left || right < qLeft) { //쿼리 밖
return 0;
} else if (qLeft<= left && right <= qRight) {
return tree[node];
} else {
int mid = (left + right) / 2;
return query(node * 2, left, mid, qLeft, qRight) + query(node * 2+1, mid + 1, right, qLeft, qRight);
}
}
static void update(int node, int left, int right, int index, long diff) {
if (left <= index && index <= right) {
tree[node] += diff;
if (left != right) {
int mid = (left + right) / 2;
update(node * 2, left, mid, index, diff);
update(node * 2 + 1, mid +1, right, index, diff);
}
}
}BottomUp 방식
static void makeTree() {
for(int i=0; i < N; i++) {
tree[S+i] = nums[i+1];
}
for(int i = S - 1; i > 0 ; i--) {
tree[i] = tree[i*2] + tree[i*2 +1];
}
}
static long query(int left, int right) {
long sum = 0;
left += S - 1;
right += S - 1;
while(left <= right) {
if(left % 2 == 1) {
sum += tree[left++];
}
if(right % 2 == 0) {
sum += tree[right--];
}
left /= 2;
right /= 2;
}
return sum;
}
static void update(int index, long value) {
index += S - 1;
tree[index] = value;
index /= 2;
while (index >= 1) {
tree[index] = tree[index * 2] + tree[index * 2 + 1];
index /= 2;
}
}
트라이노드
static void dfs(int x, int y, TrieNode current) {
// 1. 체크인
visited[x][y] = true;
sb.append(board[x][y]);
current = current.children[board[x][y] - 'A'];
// 2. 목적지에 도착했는가?
if(current.isEnd && !current.isHit) {
current.isHit = true;
hit++;
String foundword = sb.toString();
cnt += score[foundword.length()-1];
if(compare(max, foundword) > 0) {
max = foundword;
}
if(foundword.length() >= 8) {
visited[x][y] = false;
sb.deleteCharAt(sb.length()-1);
return ;
}
}
// 3. 연결된 곳을 순회
for(int i = 0 ; i < 8; i++) {
int tx = x + mx[i];
int ty = y + my[i];
//4. 갈수 있는가? if (맵을 벗어나지 않고)
if ((0 <= tx && tx < 4) && (0 <= ty && ty < 4)) {
int Index = board[tx][ty] - 'A';
// 4. 갈 수 있는가?
if(!visited[tx][ty] && current.children[Index] != null) {
// 5. 간다
// System.out.println(tx+","+ty+","+(char)board[tx][ty]);
dfs(tx, ty, current);
}
}
}
// 6. check out
visited[x][y] = false;
sb.deleteCharAt(sb.length()-1);
}
static void insert(String word) {
TrieNode current = root;
for (int i = 0 ; i < word.length(); i++) {
int wordIndex = word.charAt(i) - 'A';
if(current.children[wordIndex] == null) {
current.children[wordIndex] = new TrieNode();
}
current = current.children[wordIndex];
}
current.isEnd = true;
static boolean containsNode(String word) {
TrieNode current = root;
for (int i = 0 ; i < word.length(); i++) {
int wordIndex = word.charAt(i) - 'A';
if (current.children[wordIndex] == null) {
return false;
}
current = current.children[wordIndex];
}
return current.isEnd;
}
static int compare(String arg0, String arg1) {
int result = Integer.compare(arg1.length(), arg0.length());
if (result == 0) {
return arg0.compareTo(arg1);
} else {
return result;
}
}
class TrieNode{
TrieNode[] children = new TrieNode[26];
boolean isEnd;
boolean isHit;
public void clearHit() {
isHit = false;
for(int i=0;i < children.length; i++) {
if(children[i] != null) {
children[i].clearHit();
}
}
}
boolean hasChild(char c) {
return children[c - 'A'] != null;
}
TrieNode getChild(char c) {
return children[c - 'A'];
}
public String toString(String current, int depth) {
StringBuilder sb = new StringBuilder(current);
sb.append(isEnd ? "." : "");
for(int i = 0 ; i < children.length; i++) {
if(children[i] != null) {
sb.append("\n");
for(int j=0; j < depth; j++) {
sb.append("_");
}
sb.append(children[i].toString((char)('A' + i)+"", depth + 1));
}
}
return sb.toString();
}
}해싱
셋
맵
백준문제
- 스택 (10828)
- 큐 (10845)
- 트리순회 (1991)
- 구간 합 구하기 (2042)
- 괄호의 값 (2504)
- 트리인가? (6416)
- 이진 검색 트리 (5639)
- 생태학 (4358)
- Boggle (9202)
- 최소 힙 (1927)
- 최대 힙 (11279)
- 가운데를 말해요 (1655)
- 보석도둑 (1202)
- 사탕상자 (2243)
- 개똥벌레 (3020)
- 커피숍2 (1275)
- 소수의 곱 (2014)
- 강수량 (2094)