22년 12월 16일_내일은 아바타 보려고요!, 알고리즘, 힙에 대한 내용

금요일[이번 주는 길었다.. 일희일비가 아닌 만희비비 했음..ㅎㅎ좋겠다]

 

1. 알고리즘

2. 이것이

 

1>

슬슬 쉬운 문제를 다 풀어서 한문제 풀 때마다 시간이 오래 걸리기 시작하였다ㅜ

 

문자열 내림차순으로  배치하기

기존에 내가 풀었던 방식

def solution(s):
    answer = ''
    a = []
    for i in s:
        a.append(ord(i))
    a.reverse()
    print(a)
    for j in a:
        answer += chr(j)
    print(answer)
    return answer

근데 결과 코드에서는 이게 먹지 않는다.

def solution(s):
    answer = ''
    a = sorted(s, reverse = True)
    for i in a:
        answer += i
    return answer

 

다른사람이 한 풀이

 

def solution(s):
    return ''.join(sorted(s, reverse=True))

문자열은 정렬이 안되는 줄 알았는데 sorted를 사용해서 정렬이 가능하다.

 

최댓값과 최솟값

def solution(s):
    s = list(s)
    s.sort
    a = ""
    b = " "
    if s[0] =="-":
        a = s[0]+s[1]
    if s[-2]== "-":
        b = s[-2]+s[-1]
    else:
        a = s[0]
        b = s[-1]
    
    answer = a," ",b
    if s[-2] == "-":
        answer = b," ",a
    return "".join(answer)

test  case는 맞게나오는데,,정답처리가 안난다ㅜㅠ

 

ㅜㅜ 모르겠어ㅜㅜ pass하는 문제가 점점 늘어난다.. 쉬운거 부터 진행한다.

 

직사각형 별찍기

a, b = map(int, input().strip().split(' '))
for i in range(b):
    print("*"*a)

 

푼 문제는 많지만 기재할 수 있는 문제가 없다ㅜ 테스트케이스는 통과인데 실제 돌려보면 실패가 뜬다..

jadenCase 문의 내가 작성한 것인데.. 정답이 뭐지..?ㅎ 오늘 알고리즘은 이만해야겠다.

def solution(s):
    answer = s.split()
    result = ""
    for i in answer:
        result += i[0].upper()+i[1:].lower()+" "
    return result.rstrip()

 

 

2>

-힙 설명

힙 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나다

스택은 가장 나중에 삽입된 데이터를 가장 먼저 삭제하고, 큐는 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다.

 

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있다.

자료구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

 

우선순위 큐의 활용 예시는 여러개의 물건 데이터를 자료구조에 넣어싿가 가치가 높은 물건 데이터부터 꺼내서 확인해야하는 경우

 

대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 지원함

 

파이썬에서 우선순위 큐가 필요할 때 PriorityQueue 혹은  heapq를 사용

이 두 라이브러리 모두 우선순위 큐 기능을 지원한다.

 

하지만 PriorityQueue  보다는 일반적으로 heapq가 더 빠리게 동작하는데 제한된 상황에서는 heapq를 사용하는 것을 권장한다.

 

우선순위 값을 표현할 때는 일반적으로 정수형 자료형 변수가 사용된다. 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정해보자. 그러면 모든 물건 데이터를 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 

이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 된다.

 

대부분의 프로그래밍 언어에서는 우선순의 큐 라이브러리에 데이터 묶음을 넣으면 첫 번째워소를 기준으로 우선순위를 설정한다. 따라서 데이터가 가치로 수어되면가치 값이 우선순위 값이되는것이다. 

 

우선순위 큐를 구현할 때는 내부적으로 최소 힙 혹은 최대 힙을 이요한다.최소 힙을이용하는 경우 값이 낮은 데이터가 먼저 삭제되며, 최대힙을 이용하는 경우 값이 큰 데이터가 먼저 삭제된다. 

 

파이썬 라이브러리에서는 기본적으로최소 힙 구조를 이용하는데 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬 우선순위 큐를 그대로 사용하면 적합하다.

 

또한 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부로를 붙여서 넣었다가 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있다. 

 

이러한 테크닉도 실제 코등테스트 환경에서는 자주사용되기 때문에 기억해 놓자

 

앞서 우선순위 큐를 구현할 대 힙자료궂를 이욯나다고 햇는데, 사실 우선순위 큐를 구현하는 방법은 다양하다.

 

우선순위 큐 구현방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

// yesterday wished to today list.

. 알고리즘_✔️

. 이것이_✔️