본문 바로가기

전체 글198

7. 스택 - 알고리즘 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로.. 2023. 7. 14.
6. 스택(Stack) 1. 스택(Stack) 개념 후입선출(Last-In-First-Out : LIFO)형 자료구조 인터넷 브라우저 뒤로가기 / Ctrl + Z 실행 취소 / 접시 쌓기 push() : 데이터를 넣는 작업 pop() : 데이터를 빼오는 작업 top(), peek() : 데이터를 그대로 둔채 데이터만 가져옴 2. 스택(Stack) 구현 - JAVA 노드 기반 / Head를 더미 노드로 구현 package stack; public class MyStack implements IStack { private int size; private Node head; public MyStack() { // 생성자 this.size = 0; this.head = new Node(data:null); } @Override pub.. 2023. 7. 14.
5. 리스트 - 알고리즘 문제 11728번: 배열 합치기 (acmicpc.net) 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 알고리즘 문제 풀이 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 그림으로 정.. 2023. 7. 12.
4. 리스트 - 이중 연결 리스트 (Double Linked List) 1. Double Linked List 개념 Pointer가 앞뒤로 두 개가 들어가기 때문에 동일 데이터 양의 Single Linked List 보다 더 많은 용량이 필요하다. 데이터 추가 시 Tail Node로 접근해서 데이터 추가가 가능하다. 데이터 검색/삽입 시 인덱스가 Head보다 Tail에 가까우면 Tail로 타고 들어가서 검색/삽입이 가능하다. 따라서 Double Linked List는 더 많은 필요 용량에도 불구하고 성능 상 나름의 장점을 가지게 된다. (시간 복잡도로는 Single Linked List와 동일하게 O(n)이지만 연산 속도가 더 짧을 것으로 예상할 수 있다) 2. Double Linked List 구현 (JAVA) single Linked List와 마찬가지로 Node 기반으.. 2023. 7. 11.
3. 리스트 - 연결리스트(Linked List) 1. Linked List 개념 Node는 데이터 필드와 다음 Node를 가르키는 포인터 필드로 구성되어 있다. 가장 앞에 위치한 Node = Head 가장 뒤에 위치한 Node = Tail 이며 Tail은 가르킬 Node가 없으므로 Null을 가르킨다. 데이터 검색 시 인덱스 기반이 아니라 Node들의 Pointer를 통해 검색해 들어가야하므로, 검색의 시간 복잡도가 데이터의 개수와 같은 O(n)이다. 데이터 추가 시 Tail에 추가 Node를 넣어주므로 시간 복잡도가 역시 O(n)이다. 데이터 삽입 시 데이터를 배열 리스트처럼 뒤로 미뤄줄 필요는 없고, 포인터를 통해 연결해주면 된다. 다만, 데이터 삽입 될 곳을 찾아가는 과정 때문에 시간 복잡도가 역시 O(n)이다. 또한, Head에 앞쪽으로 데이터.. 2023. 7. 11.

티스토리툴바