citeFred’s Blog

/

/

Algorithm&DataStructure

citeFred’s Blog

/

/

Algorithm&DataStructure

Share

🏷️

Algorithm&DataStructure

# of Posts

10

1 more property

Gallery

Search

[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)란?

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

1. 정렬이 되야한다.

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

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)의 자료구조가 필요하다고 판단되었다.

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

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

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

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

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

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

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

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

문제의 의도에서는

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

[Algorithm] 같은 숫자는 싫어(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는 선입선출의 형식이며, "먼저 들어온 놈이 먼저 나간다" 라고 보시면 됩니다.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] 완주하지 못한 선수(해시맵 - 동일값 비교, 동일한 값에 대한 문제)

Load more