Krafton_jungle 5기 7일차 TIL - 알고리즘 문제풀이

1. 1181 단어정렬

문자열을 나눠서 정렬해보고 싶었지만 풀어야 할 문제가 많이 남아, 좀 더 활용하기 좋은 문제에서 사용해보기로 했다.

 

 

2. 1920 수찾기

# 일곱난쟁이 온몸비틀기
import sys
input = sys.stdin.readline

def binary_search(start, end, target):
    if start > end:
        print(0)
        return
    mid = (start+end) // 2
    if arr[mid] == target:
        print(1)
        return
    elif arr[mid] < target:
        binary_search(mid + 1, end, target)
    elif arr[mid] > target:
        binary_search(start, mid - 1, target)

# 힙 정렬
def heapify(arr, index, total_len):
    largest = index
    left = 2 * index + 1
    right = 2 * index + 2

    if left < total_len and arr[largest] < arr[left]:
        largest = left
    if right < total_len and arr[largest] < arr[right]:
        largest = right
    if largest != index:
        arr[index], arr[largest] = arr[largest], arr[index]
        heapify(arr, largest, total_len)

def heap_sort(arr):
    total_len = len(arr)
    for i in range(total_len//2-1, -1, -1):
        heapify(arr, i, total_len)

    for i in range(total_len-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)

n = int(input())
arr = list(map(int, input().split()))

# 힙정렬
heap_sort(arr)

m = int(input())
targets = list(map(int, input().split()))
for i in targets:
    binary_search(0, len(arr) -1, i)

이 문제는 기존에 학습했던 힙 정렬을 활용해서 코드를 작성해봤다.

솔직히 .sort 하나면 바로 O(n log n) 정렬이 되지만 그래도 앞으로 알고리즘 문제를 풀며 사용해야 할 정렬에 익숙해지기 위해 수고스럽지만 직접 정렬을 수행하는 코드를 작성했다.

 

3. 2309 일곱난쟁이

#파이썬 백트레킹 온몸비틀기
import sys
input = sys.stdin.readline

arr = []

def find_subsets(nums, target):
    result = []
    dfs(nums, target, [], result)
    return result

def dfs(elements, target, path, result):
    if len(path) > 7:
        return False  # 합이 타겟을 넘으면 해당 조합은 유효하지 않으므로 False 반환
    if sum(path) > target:
        return False  # 합이 타겟을 넘으면 해당 조합은 유효하지 않으므로 False 반환
    if sum(path) == target and len(path) == 7:
        result.extend(path[:])  # 결과에 현재 경로 추가
        return True  # 원하는 조합을 찾았으므로 True 반환

    for i, element in enumerate(elements):
        # 재귀 호출하여 다음 요소를 추가한 경우
        if dfs(elements[i+1:], target, path + [element], result):
            return True  # 원하는 조합을 찾았으므로 True 반환

    return False  # 모든 경우를 탐색했지만 원하는 조합을 찾지 못했으므로 False 반환

def heapify(arr, index, total_len):
    least = index
    left = 2 * index + 1
    right = 2 * index + 2
    if left < total_len and arr[least] > arr[left]:
        least = left
    if right < total_len and arr[least] > arr[right]:
        least = right
    if least != index:
        arr[index], arr[least] = arr[least], arr[index]
        heapify(arr, least, total_len)


nums = []
for _ in range(9):
    nums.append(int(input()))
target = 100
subsets = find_subsets(nums, target)

for i in range(len(subsets)//2 - 1, -1, -1):
    heapify(subsets, i, len(subsets))

for i in range(len(subsets)-1, -1, -1):
    subsets[0], subsets[i] = subsets[i], subsets[0]
    print(subsets.pop(-1))
    heapify(subsets, 0, i)

이 문제는 백트래킹을 사용해서 구현해봤는데 최대 길이가 7이면서 target과 값이 일치하는 경우의 수를 return하는 코드인데,

파이썬의 라이브러리를 사용해 경우의 수를 추출하고, 그 합을 더하면서 탐색하는 부르트포스 알고리즘보다는 백트래킹이 좀 더 효율적인것같아서 차용했다.

마찬가지로 힙 정렬도 직접 구현했는데, 사실상 그냥 코드 재활용에 가깝다.

굳이 일을 만들어서 하는 느낌이 드는건 어쩔 수 없지만, 그래도 이렇게라도 해야 머릿속에 특정 알고리즘의 동작 원리가 들어올 것 같아서 이렇게 사서 고생을 하고있다.

 

그래도 알고리즘 문제 조 아