알고리즘

print문 개행 없애기

print(내용, end='index')

print 문에 end='index'를 통해서 개행을 원하는 문자로 바꿀수 있다.

print(내용, end='\n')

원래 print 문에는 이러한 문구가 숨어있는것이라 생각해도 된다.

백준 파이썬 런타임에러(valueerror)

종이자르기 문제를 풀때 자꾸만 이러한 에러가 발생했다.

이러한 에러가 발생하는 이유는 보통은 실수때문이라고 한다.
입력의 마지막에 엔터가 들어오거나,
형 변환에서 실수가 있는 등의 실수에서 에러가 발생한다.

정렬 알고리즘

정렬이란?

💡 **정렬**이란 키를 항목값의 대소 관계에 따라 데이터 입합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다.

• 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순 정렬이라 한다.
• 큰 데이터를 앞쪽에 늘어놓는 것을 내림차순 정렬이라 한다.

정렬 알고리즘의 안정성

정렬 알고리즘은 안정적인 알고리즘과 안정적이지 않은 알고리즘으로 나눌수 있다.

안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다.

안정적이지 않은 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에 유지되지 않을수 있다.

내부 정렬과 외부 정렬

• 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘이다.
• 외부 정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘이다.

외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 별도로 작업용 파일이 필요하고 알고리즘도 복잡하다.

이 글에서는 내부 정렬만 다룰것이다.

힙 정렬

선택 정렬을 응용한 알고리즘은 힙 정렬을 알아보자

힙 정렬 알아보기

💡 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다.

그렇다면 힙은 무엇인가?

💡 힙은 ‘부모의 값이 자식의 값보다 항상 크다’는 조건을 만족하는 완전 이진 트리다. 이때 부모의 값이 자식의 값보자 항상 작아도 힙이라 한다. 즉, 대소 관계만 일정하면 된다.

최대 힙

힙에서 부모 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다.

힙의 원소를 어떻게 배열에 저장할 것인지는 다음의 이미지를 참조하면 된다

이러한 순서로 힙을 배열에 저장하면 부모 인덱스와 왼쪽 아래에 있는 자식(왼쪽 자식), 오른쪽 아래 있는 자식(오른쪽 자식) 인덱스 사이에는 다음과 같은 관계가 성립한다.

원소 a[i]에서
- 부모 : a[(i-1) // 2]
- 왼쪽 자식 : a[i * 2 + 1]
- 오른쪽 자식 : a[i * 2 + 2]

힙 정렬의 특징

힙 정렬은 힙에서 최댓값은 루트에 위치한다는 특성을 이용하여 정렬하는 알고리즘이다.

다음 동작을 반복한다.

- 힙에서 최댓값인 루트를 꺼낸다.
- 루트 이외의 부분을 합으로 만든다.

이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다.

즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이다.

또한 힙 정렬에서 최댓값인 루트를 꺼낸 뒤 다시 남은 원소 중에서 최댓값을 구해야 한다.

예를 들어 힙으로 이루어진 원소 10개에서 최댓값을 꺼내면 남은 9개 원소에서 다시 최댓값을 구해야 한다. 따라서 남은 9개 원소로 구성한 트리도 힙이 되도록 재구성해야 한다.