재밌는 코딩 공부

임포트 방법

import java.util.PriorityQueue;

생성 방식

PriorityQueue<Integer> heapq = new PriorityQueue<>();

배열로부터 데이터 할당 방식

         for (int s: scoville) {
             pqScov.add(s);
         }

pop 방식

heapq.remove()

peek 방식

heapq.peek()

요소 갯수 리턴 방식

heap.size()

https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 

 오늘 heap을 활용해 더 맵게라는 문제를 풀었다. 

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >=2:   
        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        temp = min1 + min2*2
        heapq.heappush(scoville,temp)
        answer +=1
        if K <= scoville[0]:
            return answer      
    return -1

모든 음식의 스코빌 지수가 K 이상이어야 문제가 해결 되는 것인데

최초로 섞은 음식값이 K 값을 넘었을 때 값을 리턴해버리는 실수를 해서 해결하는데 오래걸렸다. 

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap)자료구조를 제공한다.

사용법

import heapq

# 자료형은 특수한 자료형이 아닌 리스트이다.
heap = []
# 값 넣는 방법
heapq. heappush(heap, 4)
# 값 빼는 법
print(heapq.heappop(heap))
# 값 삭제하지 않고 얻기
print(heap[0])
# 기존 리스트를 힙으로 변환
heapq.heapify(heap)

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 알고리즘을 버블 정렬이라 한다.

옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법이다.

#include<stdio.h>

int main()
{
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	
	for(i = 0; i < 10; i++){
		for(j = 0; j<9 - i; j++) {
			if(array[j] > array[j+1])
			{
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
	
	for(i=0; i<10; i++)
	{
		printf("%d, ", array[i]);
	}
	
	return 0;
}

선택 정렬은 배열의 가장 작은 인덱스부터 작은 값을 정렬시키고,

버블 정렬은 배열의 가장 큰 인덱스부터 큰 값 부터 정렬시킨다.

O(n*2) -> 선택 정렬과 같이 성능이 좋지 않다.

선택 정렬은 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘이다.

#include<stdio.h>

int main()
{
	int i, j, temp, min, index;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};	
	min = 9999;
		
	for(i=0; i<10; i++) {
		min = 9999; // min 값을 지속적으로 가장 큰 값으로 초기화 하는 이유는 그렇지 않으면 
        			// min 값에 가장 작은 값이 계속 저장되어 array[j]>min 경우만 발생한다.
		
		for(j =i; j<10; j++){
			if(array[j]<min)
			{			
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = min;
		array[index] = temp;
		
	}
	
	for(i=0; i<10; i++)
	{
		printf("%d, ",array[i]);
	}
	
	return 0;
}

선택 정렬은 등차 수열로 진행된다.

배열에 {1, 2, 3, 4, 5 ,6 ,7 ,8 9, 10} 값이 무질서하게 정렬 되었을 때 

선택 정렬을 사용한다면

반복문은 10 + 9 + 8 ... + 1 이런 식으로 반복 된다.

이런 원리를 나타내는 경우 이런 식으로 변경할 수 있다. 

=> (10 * (10+1))/2

=> N * (N + 1) / 2

tip) 빅오 표기법 특정한 알고리즘의 수행시간을 간략하게 나타내는 표기법이다.

선택 정렬의 시간 복잡도 => O(n^2)