Algorithm&DataStructure

# of Posts

1 more property

Gallery

[Algorithm] 던전 피로도 (완전 탐색)

문제 해석

•

과거에 잘못 풀었던 문제이다. 면적중에서 최소값을 구했지만 가로, 세로 길이의 최대값들을 구해내야 한다.

•

문제에서 가로 세로라는 명칭에 혼동되면 안된다.

•

배열로 묶인 요소들은 가로가 될 수도, 세로가 될 수도 있는 것을 생각하면된다.

•

따라서 요소(2값중)에서 큰 값에서의 최대값

•

요소(2값중)에서 작은값 에서의 최대값

•

을 가로, 세로로 정하면 모든 카드들을 넣을 수 있다.

[Algorithm] 최소직사각형 (완전탐색-모든요소)

Priority Queue?

우선순위 큐(Priority Queue)란?

일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 구조 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가집니다. PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다.

Priority Queue의 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함)

2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음

3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(N Log N)

4. 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰임

Priority Queue 선언

자바에서 우선순위 큐 라이브러리를 사용하고 싶다면 java.util.PriorityQueue 를 import 하고 Queue<Element> queue = new Queue<>()와 같은 형식으로 선언하면 됩니다. 기본은 우선순위가 낮은 숫자가 부여되고 만약 높은 숫자가 우선순위가 되게 하고 싶다면 선언 시 Collections.reverseOrder() 메서드를 활용합니다.

Priority Queue 값 추가

자바의 우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 됩니다.

add(value) 메서드의 경우 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킵니다. 이는 Queue와 동일합니다.

[자료구조] 우선순위 큐(Priority Queue)란?

문제 해석

우선 문제를 보고 든 풀이 흐름은 다음과 같다.

•

1. 정렬이 되야한다.

•

2. 0번째 값이 k보다 커져야 한다.

◦

3-1. 작은 경우, 0,1 번째 음식을 빼낸다.

◦

3-2 두개를 섞는다. newFood = arr[0] + (arr[1]*2)

◦

3-3 섞은 횟수가 1 증가한다 mixCnt++;

◦

3-3. newFood 는 다시 음식 배열에 들어간다

•

4. 다섞어서 음식이 하나남았는데도 K보다 작다면 -1을 반환한다.

여기서 간단히 ArrayList로 풀 수 있지 않을까? 해서 아래 처럼 접근했다.

[Algorithm] 더 맵게(Heap)

문제 해석

•

예시로 제공된 수식을 살펴보면 {{0, 3}, {1, 9}, {2, 6}} 가 입력될 것인데 이 작업이 어떻게 정렬되야 가장 빠를지를 결정짓는 문제이다.

•

이것은 각 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하는 것이 목표

•

SJF(Shortest Job First) 스케줄링 알고리즘

•

이는 PriorityQueue로 우선순위 큐가 사용된다.

•

processQueue라는 변수명으로 PriorityQueue객체를 만들어서 작업을 넣는데, 우선순위 큐를 통해 jobs[i][j]에서 j=1의 값들에 따라서 작은값들이 유리한것으로 보여졌다.

•

따라서 각 작업의 1인덱스(두번째값)이 작은순서로 정렬될 필요가 있었다.

[Algorithm] 디스크 컨트롤러(Heap)

문제 해석

•

우선 직관적으로 다리에 차들이 일렬로 지나가는 모습이 그려지면서 FIFO(First In First Out)의 자료구조가 필요하다고 판단되었다.

◦

Java에서는 큐를 통해서 구현 할 수 있다.

◦

[자료구조] 큐(Queue)란? 

•

하지만 생각보다 단순해 보이는 문제지만, 로직을 실제로 구성 할 때는 너무 복잡했다. 생각과 코드가 따로 노는 느낌이 많았다.

•

문제가 혼동을 주었던 부분은 계속해서 문제를 읽다보니 다리의 길이 = 경과 시간 인것을 알게 되었다.

•

생각보다 프로세스는 읽히지만 코드가 길어서 정신이 없다. 이런것을 잘 정리하는것에 익숙해지고싶다.

•

우선 문제를 보고 내가 생각했던 흐름은 다음과 같다.

규칙 찾아내기
우선 FIFO가 필요하다 먼저들어가서 먼저 나간다. -> Queue 자료구조를 사용해야한다.
최대 2대가 들어갈수있는데 truck_weights 2개가 max_weight보다 초과하면 진입안되기때문에 1개만 가야한다.
1개만 통과할땐 2초가 소요된다.(time=길이)
그럼 그 1개만 통과하고, 2번과 3번이 만약 max_weight보다 작으면 두개를 한번에 통과시켜도 된다.
2개가 한번에 통과된다면 1초가 소요된다.(time +1)
이게 파이프처럼 만약 10버티는 다리에 4가 먼저 진입하고 5가 이후에 진입해서 2대가되면, 4가먼저빠지는게 1초, 5가 빠지는게 1초, 그이후에 만약 또 4라면 1초, 마지막에 4가 한번 더 빠져나가는데 1초

 우선 Queue 객체는 다리라고 생각하면 되고
 다리에 트럭들을 순서대로 넣고 빼는것을 만드는것이 기본
 조건으로 Queue에 들어갈 수 있는 조건을 만들어야 한다.
 만약 다리에 첫번쨰요소가 들어갔다. 그럼 기본적으로 1초가 상승하고 length만큼 상승할것이다.
 그런데 두번째 요소가 들어 갈 수 있다면(둘을 더한값이 최대보다작다면)
 마지막요소의 시간만 재면된다. 따라서 +1상태에서 길이만큼 시간이 걸리는게 그 2개가 통과하는 시간이다.

•

이게 생각은 정리가 되는것 같지만 코드로 옮기는것이 생각보다 쉽지는 않았다.

◦

다른 문제풀이를 통해서 힌트를 얻어내며 풀게되었다.

◦

우선 내가 만들어야 하는 배열이 여러개인것부터 정리했어야 했다.

▪

대기큐, 건너는큐, 시간체크용큐, 완료큐

▪

이렇게 각 배열들을 만들고 실제로 요소를 옮겨가는 상황을 시뮬레이션 했어야 했다.

▪

그리고 건너 가는 상황에 대한 로직을 하나씩 작성해나갔으면 풀이에 도전 할 수 있었을것 같다.

[Algorithm] 다리를 지나는 트럭(Queue)

문제 해석

•

처음 문제를 봤을때 핵심은 중복제거로 보였다.

◦

중복을 허용하지 않는 자료구조를 사용하면 쉽게 해결될 것 같았다.

◦

중복을 허용하지 않는 자료구조는 Set이 있으며 HashSet 또는 TreeSet으로 구현된다.

◦

하지만 모든 중복을 제거해버리는 문제가 발생했다.

public class Solution {
    public int[] Solution(int[] arr){
		HashSet<Integer> arrSet = new HashSet<>();
        for(int i=0;i<arr.length;i++) {
            arrSet.add(arr[i]);
        }
        return arrSet;

		public static void main(String[] args){
        Solution sol = new Solution();
        int[] arr = {1,1,3,3,0,1,1};
        System.out.println(Arrays.toString(sol.Solution(arr)));
    }
}
Java
복사

•

하지만 HashSet은 모든 중복을 제거해버린다. 내가원하는 결과와 달랐다.

•

문제의 의도에서는

◦

{1,1,3,3,0,1,1}에서 결과가 {1,3,0,1}이 유지되어야 한다.

◦

이는 곧 연속된 중복만 제거되어야 한다.

◦

먼저 들어간 요소와 이제 들어갈 요소가 들어가는 시점에, 값이 같은 경우에 넣지 않는 것을 활용하면 될것으로 판단되었다.

▪

[자료구조] 스택(Stack)이란? 

•

따라서 해당 문제는 스택(Stack) 자료구조를 활용하고 조건문을 통해서 중복되는 것을 흘려 보낸다면 풀이가 될 것으로 판단되었다

문제 풀이

[Algorithm] 같은 숫자는 싫어(Stack)

Stack?

Stack이란?

"스택을 쌓는다" 라는 표현을 실생활에서도 간간히 사용하기 때문에, 큐와는 다르게 그나마 기억하기가 편한 것 같습니다.

자료구조의 일종으로서 큐(Queue)와는 다르게 후입선출의 형식입니다. - LIFO(Last In First Out)나중에 들어오는 값이 가장 먼저 나가는 것으로,큐와는 다르게 Index의 개념이 존재합니다.

Java Development Kit Version 17 API Specification

declaration: module: java.base, package: java.util, class: Stack

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Stack.html

Stack의 선언 방법

[자료구조] 스택(Stack)이란?

Queue?

Queue란?

자료구조의 일종으로서 리스트성의 자료나 나열되는 자료, 순환적인 자료, 대기열 등에 사용됩니다.

Queue는 선입선출의 형식이며, "먼저 들어온 놈이 먼저 나간다" 라고 보시면 됩니다.FIFO(First In First Out) 이런 식으로 표현하기도 합니다.

Queue는 특이하게 contains() 함수를 통해 어떠한 값이 포함되어있는지는 확인할 수 있지만 Index의 개념이 없어서 어떠한 값이 몇 번째에 있는지는 알 수 없습니다.

Java Development Kit Version 17 API Specification

declaration: module: java.base, package: java.util, interface: Queue

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html

Queue의 선언 방법

[자료구조] 큐(Queue)란?

문제 해석

참가자는 완주자보다 -1 작을것이라는 것에서 이건 무조건 큰것에서 작은것을 빼다보면 남는것을 출력하면 문제가 해결될 것으로 곧바로 생각이 되었다.

이전 문제에서 해시맵을 사용했기 때문에 해시맵에 각 배열 요소들을 저장해서, 큰 맵에서 작은 맵의 요소들을 하나씩 검색해서 빼기로 했다.

문제 풀이

처음엔 동명이인에 대한 처리를 어떻게 해야 할 지 애매했다. 다른 풀이를 참고하면서 Map의 메소드 중 getOrDefault()라는 메소드를 확인하게 되었다.

키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드로

[Algorithm] 완주하지 못한 선수(해시맵 - 동일값 비교, 동일한 값에 대한 문제)