개발하는데 다 이유가 있겠지

알고리즘 및 정렬 구현

오늘은 문제를 제대로 푼 게 없는것 같다..

벌써 정체가 오면 안되는데, 하나도 쉬운게 없다.

남들은 진도가 쑥쑥 나가는데 조금 무섭다.

남들과 비교하면 안되지만 어쩔 수가 없다.

더 열심히 하자❗️

---

11279. 최대 힙

• 힙 정렬 구현
• 이중 완전 트리인 힙을 가장 마지막 노드의 부모 노드부터 순차적으로 힙 정렬
• 부모 노드와 마지막 노드를 스왑(Swap)하고 다시 힙 정렬 실시

def max_heapify(arr, n, i):
    largest = i  # 부모 노드의 인덱스로 초기화
    left = 2 * i + 1  # 왼쪽 자식 노드의 인덱스
    right = 2 * i + 2  # 오른쪽 자식 노드의 인덱스

    # 왼쪽 자식 노드가 부모 노드보다 크면 largest 값을 갱신
    if left < n and arr[largest] < arr[left]:
        largest = left

    # 오른쪽 자식 노드가 부모 노드보다 크면 largest 값을 갱신
    if right < n and arr[largest] < arr[right]:
        largest = right

    # largest 값이 갱신되었다면 노드를 교환하고, 재귀적으로 Max Heapify를 호출
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        max_heapify(arr, n, largest)

# 힙 정렬 함수
def heap_sort(arr):
    n = len(arr)

    # 입력 배열을 최대 힙 형태로 만듦
    # 마지막 노드의 부모노드
    for i in range(n // 2 - 1, -1, -1):
        max_heapify(arr, n, i)

    # 힙에서 최대 원소를 추출하고 정렬된 부분에 추가
    # 최대 원소를 마지막 원소와 교환하고 다시 힙정렬
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 최대 원소를 맨 뒤로 이동
        max_heapify(arr, i, 0)  # 힙 속성 유지

    return arr

 

9663. N-Queen

• 퀸의 상태를 체크하는 함수와 경우의 수를 구하는 함수로 구현
• 퀸이 모두 배치가 완료되면 카운트 증가
• 2차원 배열은 시간 초과발생해 1차원 배열의 인덱스를 x좌표 / 값을 y좌표로 생각

import sys
input = sys.stdin.readline

n = int(input())
rows = [0]*n
count = 0
# 퀸이 공격받고 있는지 여부 확인
# row[x] = y
# x는 행을 나타내고, y는 열을 나타냄
# 퀸이 전부 배치가 되면 count += 1

# 가로, 세로, 대각선 비교해서 안전한지 확인
def safe(x):
    for i in range(x):
        if rows[x] == rows[i] or abs(rows[x]-rows[i]) == abs(x-i):
            return False
    return True


def set_queen(start):
    global count

    if start == n:
        count += 1
    else:
        for i in range(n):
            rows[start] = i
            if safe(start):
                set_queen(start+1)


set_queen(0)
print(count)

 

1629. 곱셈

• 모듈러의 분배 법칙으로 해결해야 함
• 단순히 결과 값에 모듈러 연산을 수행하면 이미 결과값이 너무 커져서 오버플로우가 발생하거나 연산에 시간이 오래 걸리는 경우 발생

import sys
input = sys.stdin.readline

# 빠른 거듭제곱 함수
def fast_exponentiation(a, b, c):
    # 제곱 0이면 1
    if b == 0:
        return 1
    # 짝수일 경우
    elif b % 2 == 0:
        temp = fast_exponentiation(a, b // 2, c)
        return (temp * temp) % c
    # 홀수인 경우
    else:
        temp = fast_exponentiation(a, (b - 1) // 2, c)
        return (temp * temp * a) % c

a, b, c = map(int, input().split())
answer = fast_exponentiation(a, b, c)
print(answer)

 

1914. 하노이 탑

• 수학적 귀납법으로 증명
• 첫번째로 n-1개를 시작 기둥에서 보조 기둥으로 옮김 / (n-1)
• 두번째로 남은 1개(제일 큰 원반)을 목표 기둥으로 옮김 / (1)
• 세번째로 n-1개를 보조 기둥에서 목표 기둥으로 옮김 / (n-1)

n = int(input())


def hanoi(num, start, end, other):
    if num == 1:
        print(start, end, sep=" ")
        return
    hanoi(num-1, start, other, end)
    print(start, end, sep=" ")
    hanoi(num-1, other, end, start)


if n <= 20:
    print(2**n-1)
    hanoi(n, 1, 3, 2)
else:
    print(2**n-1)