nose딩

결과 : 

1주차에 공부했던 것(힙(Heap))을 바탕으로 프로그래머스에서 문제 풀이를 진행하였다.

*더 맵게

먼저 우선순위 큐를 선언 한 후, scovile배열의 원소들을 다 넣어주었다.

그리고 모든 원소가 k 이상이 될 때까지 반복하기 위해,

while문 조건은 q.peek()<K 로 설정하였다.

우선순위큐이기 때문에 정렬이 되어있고, 따라서 peek를 하게되면 가장 작은 값이기 때문이다.

그리고 얼마나 이 과정을 반복하는 지 count해서 리턴하여 해결하였다.

*디스크 컨트롤러

이 문제는 클래스를 이용하였다.

많은 풀이를 살펴보았는데 보통은 우선순위 큐 하나와 리스트를 이용하는 경우를 많이 보았다.

나도 첨엔 그렇게 하다가, 그냥 리스트 하나로 정렬을 하면 되지 않을 까 싶어서 이렇게 구현하였다.

리스트에다가 DiskRequest를 생성하여 집어넣고, Collections.sort를 통해 정렬해준다.

기본적으로는 작업의 소요시간(time)을 기준으로 정렬하였고, 작업의 소요시간이 같을경우 작업의 요청시간(start)가 기준이된다. 

시작시간이 현재시간(t)보다 작은 경우에만 작업을 처리한다.

그래서 t를 증가시키고, answer에 각 작업의 요청부터 종료까지 걸린시간(현재시간-작업의 요청시간)을 추가한다. 

만약 이 경우에 걸리지 않고, 시작시간이 현재시간보다 작지 않다면 시간을 1 초 증가시킨다.

이 작업을 리스트가 빌 때까지 반복한다.

그리고 jobs.length로 나눠 리턴하면 된다.

++ 디스크 컨트롤러 문제는 많은 시간을 헤맸다. 😂

예제는 해결했지만 계속 틀렸다고 나와서 많이 도전하였고 결국 검색의 힘을 많이 받았다.

따라서 다음에 다시 또 복습하고자 한다.

회의 일자 : 

2020.12.30 20:00 ~ 23:00 

목표 : 

- 1주차에 공부한 것( 힙(Heap) )을 가지고 알고리즘 문제 해결 ( 프로그래머스 문제 풀기 ) 

결과 : 

힙(Heap)은 최댓값과 최솟값을 쉽게 찾아내기 위해 사용한다.

최소힙과 최대힙이 있는데,

부모노드가 자식노드보다 작으면 최소 힙(MinHeap)이고, 

부모노드가 자식노드보다 크면  최대 힙(MaxHeap)이다.

*삽입:

힙은 완전 이진 트리의 구조를 유지해야한다.

따라서 삽입 할 때 트리의 가장 마지막에 원소를 추가한다.

그 후 힙의 조건이 맞는 지 확인한다. !

예를 들어, maxheap의 경우,

마지막에 원소 추가 한 후에 부모노드와 검사를 해서

조건이 맞지 않으면(부모노드가 더 작은경우) 자리를 바꾼다.  

그리고 조건이 맞을 때 까지 반복하여 검사한다.

루트 노드에 위치하게 되는 경우에는 더 이상 검사를 하지않고 끝난다.

*삭제:

삭제연산은 루트에서 이루어진다.

루트에서 노드가 삭제된 후, 가장 마지막 노드를 루트로 옮긴다. 이는 완전 이진 트리를 유지하기 위함이다.

루트로 옮겨지면 자식노드와 비교하여 힙 조건을 검사한다.

조건이 맞지않으면 루트노드와 자식노드를 바꿔준다.

힙 조건을 만족할 때 까지 조건검사를 반복하여 진행한다.

+ 

대표적으로 힙을 활용하는 것이 우선순위 큐가 있다.

* 우선순위 큐가 사용되어야 하는 경우 ?

  -> 원소를 삽입, 삭제 후 매번 정렬을 해야하는 문제 !

  -> Collections.sort와 같은 퀵 정렬을 사용하면 시간복잡도가 nlogn으로 커지게 된다.

  -> 우선순위 큐를 사용하면 원소 삽입 또는 삭제 시 logn의 시간복잡도로 정렬할 수 있음 !

*PriorityQueue 사용법

  일단 PriorityQueue를 import 해준다.

  그 후 타입에 따라 선언을 해준다.

  ex ) int형의경우

  PriortyQueue<Integer> pq = new PriorityQueue<>();

  와 같이 선언한다.

  - 삽입 : add()

    ex) pq.add(1) 을 해주면 1이 삽입된다.

  - 삭제 :  poll(), remove() - 우선순위 가장 높은 값 제거(루트)

    poll() : 값을 반환하고 제거, 비어있다면 null

    remove() : 제거 (반환 x )

삽입, 삭제 과정을 그림도 그려보고, 구현 된 코드를 살펴보며 알고리즘 및 자료구조 시간에 다루었던 heap에 대해 복습할 수 있었다.

다음 시간에는 이를 바탕으로 알고리즘 문제를 풀어 심화시켜보고자 한다. ! 

회의 일자 : 

2020.12.28 20:00 ~ 23:00 

목표 : 

- 힙(Heap) 공부

  : Heap에 대한 이해와 기초 다지기

1회차(12.28) 

  - 학습목표 :  힙(Heap) 공부

2회차(12.30)

  - 학습목표 :  1주차에 공부한 것을 가지고 알고리즘 문제 해결

3회차(01.04)

  - 학습목표 : 깊이/너비 우선 탐색(DFS/BFS) 공부

4회차(01.06)

  - 학습목표 :  3회차에 공부한 것을 가지고 알고리즘 문제 해결

5회차(01.11)

  - 학습목표 : 해시, 스택/큐 공부

6회차(01.13)

  - 학습목표 : 5회차에 공부한 것을 가지고 알고리즘 문제 해결