Knowledge/Data Structure
-
덱에 대해 알아보자Knowledge/Data Structure 2019. 10. 18. 17:15
- 덱이란? 양쪽 끝 모두에서 자료를 넣고 뺄 수 있는 자료구조. 한 쪽에서만 자료를 넣고 빼면 스택처럼 사용할 수 있고 한 쪽에서 자료를 넣고 한 쪽으로 빼면 큐처럼 사용할 수 있다. 하지만 덱을 사용해야만 풀 수 있는 문제는 거의 없기 때문에 PS에서는 거의 사용되지 않는다 - 주로 사용하는 메소드 addFirst: 덱 앞 쪽에 자료를 넣는 연산 addFirst: 덱 뒷 쪽에 자료를 넣는 연산 removeFirst: 덱 앞 쪽에서 자료를 빼는 연산 removeLast: 덱 뒷 쪽에서 자료를 빼는 연산 getFirst : 덱 앞 쪽에있는 자료를 가져온다 getLast : 덱 뒷 쪽에있는 자료를 가져온다 empty: 덱이 비어있는지 아닌지를 알아보는 연산 자세한 메소드는 1 java.util.Deque ..
-
큐에 대해 알아보자Knowledge/Data Structure 2019. 9. 5. 18:24
- 큐란? 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 구조 먼저 넣은 것이 가장 먼저 나오기 때문에 FIFO ( First In First Out) 라고도 한다 - 주로 사용하는 메소드 ( Java ) push, pop, front, back, empty, size가 있다고 하는데 그건 C나 C++ 얘기인 것 같고 자바에서 LinkedList로 큐를 구현했을 경우는 - isEmpty() : 비어있는지 확인 - offer() : 큐의 뒤에 값을 입력한다 - poll() : 큐의 가장 앞에 있는 값을 꺼내고 반환한다 - peek() : 큐의 가장 앞에 있는 값을 확인만 한다 - 구현 이 역시도 백준 큐 구현 문제 ( https://www.acmicpc.net/problem/10845 ) 에 ..
-
스택에 대해 알아보자Knowledge/Data Structure 2019. 9. 4. 22:25
- 스택이란? 한쪽 끝 ( 가장 위 - Top )에서만 자료를 넣고 뺄 수 있는 자료구조. 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO ( Last In First Out ) 라고도 한다. - 주로 사용하는 메소드 push: 스택에 자료를 넣는 연산 pop : 스택에서 자료를 빼는 연산 peek: 스택의 가장 위에 있는 자료를 보는 연산 empty: 스택이 비어있는지 아닌지를 알아보는 연산 size: 스택에 저장되어있는 자료의 개수를 알아보는 연산 - 구현 정확한 구현이 아닌 백준 10828번 스택 문제 ( https://www.acmicpc.net/problem/10828 ) 의 조건 push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출..
-
시간복잡도를 표현하자! Big O 표기법Knowledge/Data Structure 2019. 9. 4. 16:42
- 문제의 크기와 조건 알고리즘 문제가 주어졌을 경우 우선 문제의 크기와 조건 고려해야 한다. 예를 들어 '메뉴판에 있는 모든 메뉴를 읽는데 걸리는 시간을 구하라' 라는 문제가 있을 때 메뉴판이 하나뿐이라면 시간은 사람수 N X 메뉴 갯수 M 만큼 걸리겠지만 사람수만큼 메뉴판이 있다고 조건이 바뀌면 메뉴 갯수 M 만큼만 걸릴테니까. 그렇기에 문제가 주어졌을 땐 항상 문제의 크기와 조건을 먼저 보고 방법을 생각해야 한다. - 시간 복잡도 방법을 생각했다면 그 다음 고려해야 할 것은 시간 복잡도이다. 문제 해결 능력을 측정하는 알고리즘 문제 해결에선 특히 시간이 짧을 수록 효율적이라고 본다 그렇기에 문제가 주어졌을 때 떠올린 해결 방법이 최악의 경우 얼마나 시간이 걸릴지를 대문자 O를 사용하는 표기하는 Bi..