Algorithm&DataStructure

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

•

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

•

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

•

따라서 요소(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보다 커져야 한다.

•

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

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

•

문제는 내가 원하는 방식대로 풀이되는 줄 알았지만 문제가 발생했다.

•

나는 가장 작은값, 그 다음값을 찾아내기 위해서 반복문 1회마다 계속해서 정렬하는 방식을 사용하고 있다. 여기서 효율성에 대한 문제가 발생하고 있었다.

•

질답 게시판 들에서도 나와 비슷한 사례가 있었으며 답변에서 매번 정렬을 진행하는것은 성능적 이슈가 있을 것이라는 답변을 보고 다른 방법으로 접근해됨을 알게되었다.

•

중요한것은 최소값을 추출하는 가장 효율적인 방법이 필요했다. 만약 정렬되지 않는다면, 또 비교 검색을 통해서 가장 작은값을 추출해야 할텐데 비효율적일 것이다.

•

여기서 ChatGPT의 도움을 통해 어떤 방식이 최소값을 추출하는데 가장 적합할지 찾아보니 다음과 같은 답변을 얻을 수 있었다.

매번 정렬하는 부분이 효율성에 영향을 미치고 있다면, 정렬을 최소화하는 방법을 찾아보는 것이 좋아. ArrayList에서 가장 작은 값과 그 다음 값을 찾는 방법을 바꿔보자.

대신에 PriorityQueue를 사용하면 효율적으로 최소값을 추출할 수 있어. PriorityQueue는 내부에서 힙(heap)을 사용하여 최소값을 빠르게 추출할 수 있도록 도와줘.

[Algorithm] 더 맵게(Heap)

문제 해석

•

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

•

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

•

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

•

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

•

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

•

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

•

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

문제 풀이

•

우선 프로세스 순서인 0번째 인덱스별로 정렬하고

•

Arrays.sort(jobs, (a, b) -> a[0] - b[0])에서 a[0] - b[0]은 작업의 요청 시간을 기준으로 오름차순 정렬하도록 하는 부분입니다.

•

따라서 배열을 처음에 {0, 3}, {1, 9}, {2, 6} 순서대로 정렬하고 우선순위 큐에 저장됩니다.

•

큐에 저장되고있는 작업들은 우선순위 큐는 두번째 인덱스인 [1]에 따라 내림차순으로 정렬됩니다.

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

문제 해석

•

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

•

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

•

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

•

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

•

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

•

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

문제 풀이

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

문제 해석

•

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

•

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

•

문제의 의도에서는

•

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

문제 풀이

배열의 요소들을 스택 객체에 복사하는 시점에, 중복값이 있는 경우 continue를 통해 다음 요소로 넘어가도록 설정했다.

하지만 정답을 추출할때는 스택의 pop은 FILO인 것을 고려해야 한다. 역순으로 추출(pop)되기 때문에 그 역순을 다시 역순으로 바꿔서 추출하면 원하는 답을 얻을 수 있었다.

[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<객체> 변수명 = new Stack<객체>();

큐와는 달리 Stack만을 Import하여 사용합니다.

Stack에 값을 추가하는 방법(add와 push의 차이점)

•

Stack변수.push(값);

•

Stack변수.add(값);2가지 방법이 있으며, 과정은 비슷하나 결과가 다릅니다.

•

add의 경우 true를 return하고, push는 push한 item을 return합니다.

[자료구조] 스택(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<객체> 변수명 = new LinkedList<객체>();

•

Queue와 LinkedList 유틸을 모두 import해줘야 정상적으로 사용 가능합니다.

Queue에 값을 추가하는 방법(add와 offer의 차이점)

•

Queue변수.offer(값);

•

Queue변수.add(값);이렇게 2가지 방법이 있으며, 과정은 비슷하나 결과가 다릅니다.

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

문제 해석

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

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

문제 풀이

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

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

getOrDefault(Object key, V DefaultValue)

반환 값 : 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환되는 것이다.

풀어쓰면 동일한 이름이 있으면 value가 1증가하게 되도록 된 것이다.

참가자 맵인 comMap에서 name을 추출해서 완주자 parMap에서 존재하지 않는것을 체크하면서 그 이름을 반환한다.

또한 comMap.get(name) > parMap.get(name)는 동명이인인 경우에 혹시 참가자가 동일한 이름이 2명이면 1, 완주자는 0으로 나타날 수 있어서 그런 경우 그 동명이인 참가자가 완주하지 못했을 것을 체크하는 부분이다.

동명이인에 대한 처리를 어떻게 해야 할 지 바로 생각나지 않을 것 같다. 여러 연습을 해봐야 할 것 같다.

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