본문 바로가기

알고리즘/복습8

Priority Queue (우선순위 큐) PriorityQueue PriorityQueue란? PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아니라 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. PriorityQueue를 사용하기 위해서 우선순위 큐에 저장될 객체는 필수적으로 Comparable Interface를 구현해야한다. Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다. 우선순위를 반전시키는 방법은 객체 생성 .. 2022. 4. 7.
최장증가수열(LIS) 최장증가수열(LIS : Longest Incresing Subsequence) 수열이 나열되어있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제 ex) 3,2,6,4,5,1 라는 수열에서 최장증가 수열은 [2,4,5] 혹은 [3,4,5]이고, 길이는 3이다 이는 어떻게 구할까? 부분집합 부분집합을 통해 증가하면서 길이가 가장 긴 수열을 구할 수도 있지만, 부분집합은 시간복잡도가 2의 n승이기 때문에 수열이 길어질수록 시간적으로 부담이된다. https://java-is-happy-things.tistory.com/8?category=1266501 [Java] 부분집합 부분집합 : 한 집합에 포함될 수 있는 모든 집합들, 부분집합의 수는 2의n승이다. [입력] 3.. 2022. 4. 6.
Knapsack알고리즘 Knapsack알고리즘 아래와 같이 n개의 물건과 각 물건i의 무게Wi와 가치Vi가 주어지고 배낭의 용량은 W일때, 배낭에 담을 수 있는 물건의 최대가치를 찾는 문제를 다뤄본다. 단, 배낭에 담은 물건의 무게 합은 배낭의용량W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다. 배낭 문제를 DP로 접근해보자. 변수는 물건, 물건의무게, 물건의가치, 배낭의 용량 총 4가지 이다. 이 중 물건과 물건의 무게는 부분문제를 정의하는데 반드시 필요하다. 왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는것과 안담는것을 현재 배낭에 들어있는물건의 가치의 합에 근거하여 결정해야 하기 때문이다. 또한 물건을 배낭에 담으려고 할 경우 배낭용량의 초과여부를 검사해야 한다. W : 배낭의 용량 (vi, w.. 2022. 4. 5.
[Java] Stack Stack : 자료구조 중 하나, 먼저 집어넣은 데이터가 가장 나중에 나오는 선입후출의 구조(LIFO: Last In First Out) top : 맨 위에 위치한 인덱스 -> 가장 최근에 들어온 데이터이자 다음에 출력될 값 [활용사례] 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) 재귀함수 = 깊이우선탐색 (DFS,Depth-First Search) 구현 [구현] Stack stack = new Stack(); stack.push() : 스택에 값 삽입 stack.pop().. 2022. 3. 19.
[Java] Queue Queue Queue : 자료구조중 하나, 먼저 집어넣은 데이터가 먼저 나오는 선입선출의 구조(FIFO: First In First Out) Front : 맨 앞에 위치한 인덱스 -> 다음에 출력될 값 Rear : 맨 뒤에 위치한 인덱스 -> 가장 최근에 입력된 값 [활용] 너비 우선 탐색(BFS, Breadth-First Search) 구현 캐시(Cache) 구현 우선순위가 같은 작업 예약 선입선출이 필요한 대기열 콜센터 고객 대기시간 프린터의 출력 처리 윈도 시스템의 메시지 처리기 프로세스 관리 [구현] 큐는 인터페이스이기 때문에 LinkedList 또는 ArrayDeque로 구현해주어야 한다. Queue queue = new LinkedList(); 또는 Queue queue = new ArrayD.. 2022. 3. 19.
[Java] 부분집합(Subset) 부분집합(Subset) 부분집합 : 한 집합에 포함될 수 있는 모든 집합들, 부분집합의 수는 2의n승이다. [입력] 3 1 2 3 [출력] 1 2 3 1 2 X 1 X 3 1 X X X 2 3 X 2 X X X 3 X X X [변수] - N : 존재하는 원소의 수 - input : 존재하는 원소들을 담고있는 배열 - isSeletcted : 선택된 수의 정보를 표시하는 배열 - cnt : 뽑은갯수를 파악하기 위한 인자값 [풀이] 재귀로 구현하였다. 모든 원소에 대해 뽑는경우, 안뽑는 경우로 돌린다. 처음에는 마지막까지 다 뽑으므로 input배열 [1,2,3]에 대하여 isSelected배열이 [true,true,true]가 될것이다. => 1,2,3 그리고 return되어 다시 마지막 3에 재귀에서 안뽑.. 2022. 3. 15.

티스토리툴바