Min IT's Devlog

전에서 관련 알고리즘을 찾아보고 코딩 문제를 해결했던 것 같은데 오랜만에 다시보니 기억이 나지 않아 이번에 정리해보고자 한다. 언어는 python을 사용해서 진행해보고자 한다. 최장 증가 부분 수열(Longest Increasing Subsequence) 해당 알고리즘은 DP(Dynamic Programming) 문제로 자주 나오고 있으며 O(N^2)의 시간복잡도를 가지고 있는 알고리즘과 O(NLogN)의 시간복잡도를 가지고 있는 알고리즘이 존재한다. [개념] LIS는 어떤 수열에서 만들 수 있는 부분수열 중에서 가장 길면서 오름차순을 유지하는 수열이다. 여기서 부분 수열이란 주어진 수열에서 일부 수를 뽑아내어 만든 수열을 의미한다. 2 5 3 1 4 7 6 예를 든다면 위에 주어진 수열에서 부분 수열은..

Deque 선형 자료구조 컨테이너의 양쪽 끝에서 삽입과 제거가 이루어지는 스택과 큐를 합쳐놓은 자료구조 Deque에는 일반적인 Deque와 한쪽에서만 입력하도록 제한된 Scroll Deque, 한쪽에서만 제거하도록 제한된 Shelf Deque가 있다. 멤버변수: rear, head( element가 삽입되거나 제거되는 위치) Deque 사용법 import java.util.Deque 자바는 java.util.Deque interface로 Queue를 제공하고 있다. Deque 선언 Deque deque = new LinkedList(); // Deque를 구현한 linkedlist class 이용 Deque deque1 = new ArrayDeque(); // Deque를 구현한 ArrayDeque cl..

Queue 선형 자료구조 한쪽 끝에서만 삽입이 이루어지고 다른 한쪽 끝에서는 삭제이 이루어지는 FIFO구조의 자료구조 Queue에는 선형 큐,원형큐, 링크드리스트 큐, 우선순위큐 등의 종류가 존재한다. 컴퓨터의 버퍼에서 사용하는 형태 멤버변수: rear(새로운 element가 들어가는 위치) head(element가 나가는 위치) Queue 사용법 import java.util.Queue; 자바는 java.util.Queue 인터페이스로 Queue를 제공하고 있다. Queue 선언 Queue queue = new LinkedList(); // linkedlist를 이용한 Queue 사용법 Queue 자체는 인터페이스이기 때문에 LinkedList를 이용하여 Queue를 선언해야 한다. Queue 메서드 ..

Stack 선형 자료구조 한 쪽 끝에서 자료를 넣고 뺄 수 있는 LIFO구조의 자료구조 사용 분야: 함수 호출 순서의 제어, 인터럽트 처리, 수식 계산, 재귀적 문제를 동적 프로그래밍 방식으로 해결 멤버변수: top(현재 위치) Stack 사용법 import java.util.Stack; 자바는 java.util.Stack Class를 통해 Stack을 제공하고 있다. Stack 선언 Stack s = new Stack(); Stack의 경우 생성자가 하나뿐이다. Stack 메서드 데이터 삽입 stack.push(E element); // element를 stack의 top에 추가 데이터 삭제 stack.pop(); // 스택의 제일 위에 있는 element를 반환하고 스택에서 제거 데이터 검색 stac..

지금까지 ArrayList와 LinkedList의 특징과 장단점, 구현까지 해보았다. [Java] ArrayList 사용과 구현 ArrayList List 인터페이스를 상속받은 클래스 일반적인 배열과 동일하게 연속적인 공간을 사용하고 인덱스 또한 0부터 시작된다. 인덱스를 통한 임의접근이 가능하다 객체가 추가되면서 현재 가 minit-devlog.tistory.com [Java] LinkedList 사용과 구현 LinkedList List 인터페이스를 상속받은 클래스 연속적인 공간을 사용하지 않고 모든 데이터가 노드(데이터 + 주소)로 구성되어있다. index가 없기 때문에 임의접근이 불가능하다. Singly LinkedList(data + n minit-devlog.tistory.com Collecti..

LinkedList List 인터페이스를 상속받은 클래스 연속적인 공간을 사용하지 않고 모든 데이터가 노드(데이터 + 주소)로 구성되어있다. index가 없기 때문에 임의접근이 불가능하다. Singly LinkedList(data + nextNode주소) , Doubly LinkedList(prevNode주소 + data + nextNode주소) 자바에서는 LinkedList는 Doubly LinkedList로 구현되어 있다. 데이터의 순서가 있으며 동일 데이터에 대한 중복 저장을 허용한다. LinkedList 멤버변수: size(들어있는 element 개수), head(시작 node주소), tail(마지막 node주소) LinkedList 사용법 import java.util.LinkedList; 자바..

ArrayList List 인터페이스를 상속받은 클래스 일반적인 배열과 동일하게 연속적인 공간을 사용하고 인덱스 또한 0부터 시작된다. 인덱스를 통한 임의접근이 가능하다 객체가 추가되면서 현재 가용량(capacity)을 넘어선다면 자동으로 크기가 늘어나는 특징을 가진다. (가변적) List이기에 데이터 순서가 있으며 동일 데이터에 대한 중복 저장을 허용한다. ArrayList 0 1 2 3 4 멤버변수: capacity(용량), size(들어있는 element 개수) ArrayList 사용법 import java.util.ArrayList; 자바는 java.util.ArrayList Class를 통해 ArrayList를 제공하고 있다. ArrayList 선언 ArrayList al = new ArrayL..