알고리즘 - 정렬

오늘은 2가지를 배웠다. 하나는 깃에 내가 푼 백준문제와 리트코드를 커밋하는것과 정렬이다.

내가 푼 문제를 시간 쓰지 않고 커밋할수 있다는 점이 유요했다.

오늘 배운 알고리즘은 정렬이다. 펴소 정렬은 그냥 sort()나 sorted로 했었는데 그건 배열정렬이었고 그 이외나 내장함수를 

사용하지 못한경우 다른 정렬방법을 사용해야한다.

 

1. 버블 정렬(Bubblesort)

  버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식.

• 작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경하시면 된다

2. 선택 정렬(Selectionsort)

 사람들이 일렬로 서 있는데, 둘러보면서 가장 키 작은 사람을 찾는것. 그리고 전부 다 봤다면, 그 중 가장 키 작은 사람을 맨 앞으로 불러 오고 다음에 또 둘러보면서 두 번째로 키 작은 사람을 두 번째에 배치 시키는 방식

 

3. 삽입 정렬(Insertionsort)

  선택 정렬이 전체에서 최솟값을 선택하는 거 였다면, 삽입 정렬은 전체에서 하나씩 올바른 위치에 삽입하는 방식이다.

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다. 즉 다음 원소가 그 정렬된 사람들 사이를 비집고 들어가면서 이미 키 순으로 정렬된 사람들이 일렬로 서 있는데 삽입하며 정렬하는 방식입니다.

 

4. 퀵소트(Quicksort)

 분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘이다. 배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눈다(Divide). 그리고 그 사이에 기준을 위치시킨다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있다.

 

*기본코드

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)
    return lst

 

5. 병합 정렬(mergesort)

 

*기본코드

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result


def mergesort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    L = lst[:mid]
    R = lst[mid:]
    return merge(mergesort(L), mergesort(R))

 

6. 힙 정렬(Heapsort)

  완전 이진트리인 힙의 특성을 이용한 정렬이다. 내장함수를 이용하면 쉽게 정렬을 할수 있다.

 

*기본코드

import heapq

def k_closest_builtin(points, k):
    dists = []
    heap = []
    for point in points:
        dist = cal_dist(point)
        heapq.heappush(heap, dist)
        dists.append(dist)

    kth_dist = [heapq.heappop(heap) for _ in range(k)][-1]
    return [points[idx] for idx, dist in enumerate(dists) if dist <= kth_dist]

 

 

오늘의 문제는 대부분 퀵,머지,힙 정렬의 기본코드로 이용해서 풀렸다. 그래서 해당 문제들은 문제 링크만 첨부하고 해당 정렬을 이용해서 풀지 않은 문제만 코드를 첨부한다.

 

1번 문제 - 수 정렬하기 2 : [boj] https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

2번 문제 - 나이순 정렬 : [boj] https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

3번 문제 - 가장 큰 수 https://leetcode.com/problems/largest-number

Largest Number - LeetCode

4번 문제 - 색 정렬 : https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

 

5번 문제 - 통계학 [boj] https://www.acmicpc.net/problem/2108

2108번: 통계학

from collections import Counter
def statistics(n):
    numbers = [int(input()) for _ in range(n)]

    # 산술평균
    average = sum(numbers) / n

    # 중앙값
    sorted_numbers = sorted(numbers)
    median = sorted_numbers[n // 2]

    # 최빈값 - 추가 설명 필요
    counter = Counter(numbers)
    max_count = max(counter.values())
    mode_candidates = [num for num, count in counter.items() if count == max_count]
    mode_candidates.sort()
    if len(mode_candidates) == 1:
        mode = mode_candidates[0]
    else:
        mode = mode_candidates[1]

    # 범위
    range_value = max(numbers) - min(numbers)

    # 출력
    print(round(average))
    print(median)
    print(mode)
    print(range_value)

n = int(input())
statistics(n)

 

각 해결사항을 대부분 내장함수로 해결했다. 최빈값에서 주로 에러가 발생했는데 한꺼번에 하기보다는 최빈값 후보들을 다 리스트에 넣어서 정렬한뒤 후보들을 넣은 리스트의 길이에 따라 값을 다르게 설정했다.

 

6번 문제 - 전화번호 목록 [boj] https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

def check_consistency(phone_numbers):
    phone_set = set(phone_numbers)
    for number in phone_numbers:
        for i in range(1, len(number)):
            if number[:i] in phone_set:
                return "NO"
    return "YES"

t = int(input())

for _ in range(t):
    n = int(input())
    phone_numbers = [input() for _ in range(n)]
    print(check_consistency(phone_numbers))

 

중복을 없애기 위해 set 처리를 했고 이중 for문으로 두번째 문자(첫번째는 접두사가 될수 없으므로)부터 number의 길이만큼 돌면서 2번째 문자부터 i까지의 문자열이 phone_set에 있는지 검사해줬다 그 결과 있으면 no를 리턴했고 이중 for문이 끝나도 없으면 yes를 리턴하는 방식으로 해결했다

 

*코드리뷰 할때 알게 된것이 startswith다. startswith는 문자열이 특정 접두사로 시작하는지를 확인하는 메서드다. 문자열이 지정된 접두사로 시작하면 True를 반환하고, 그렇지 않으면 False를 반환한다.

 

사용예제

text = "Hello, World!"

# 문자열이 "Hello"로 시작하는지 확인
result = text.startswith("Hello")
print(result)  # 출력: True

# 문자열이 "World"로 시작하는지 확인
result = text.startswith("World")
print(result)  # 출력: False

 

튜플로도 사용이 가능하다.

string = "abcdef"

# 문자열이 "abc" 또는 "def"로 시작하는지 확인
if string.startswith(("abc", "def")):
    print("문자열은 'abc' 또는 'def'로 시작합니다.")
else:
    print("문자열은 'abc' 또는 'def'로 시작하지 않습니다.")