알고리즘 문제 풀어보기

소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

풀이 코드

function solution(numbers) {
    var result = new Set();
    
    function getPermutation (arr, fixed) {
        if(arr.length >= 1) {
            for (let i=0; i<arr.length; i++) {
                const newFixed = fixed + arr[i];
                const copyArr = [...arr];
                copyArr.splice(i, 1);
                
                if(isPrimeNumber(parseInt(newFixed))) {
                    result.add(parseInt(newFixed));
                }
                
                getPermutation(copyArr, newFixed);
            }
        }
    }
    
    function isPrimeNumber(num) {
        if (num <= 1) return false;
        if (num === 2) return true;
        for( let i = 2; i <= Math.sqrt(num); i++) {
           if(num % i === 0) {
               return false;
           }
        }
        return true;
    }
    
    getPermutation(numbers, '')

    return result.size;
}

풀이 과정

순열을 찾을 함수, 소수일때 true를 반환하는 함수를 만든다.

기술면접 문제 풀어보기

14. 다음의 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해주세요

- 선택 정렬(Selection Sort)
- 버블 정렬(Bubble Sort)
- 병합 정렬(Merge Sort)
- 삽입 정렬(Insertion Sort)
- 퀵 정렬(Quick Sort)
- 힙 정렬(Heap Sort)

선택 정렬(Selection Sort)

• 시간 복잡도 : O(n^2)
• 가장 작은 요소를 찾아서 맨 앞의 요소와 교환하는 방식.
• 예시 코드

def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 예시 사용
print(selection_sort([64, 25, 12, 22, 11]))

버블 정렬(Bubble Sort)

• 시간 복잡도 : O(n^2)
• 인접한 두 요소를 비교해서 큰 값을 뒤로 보내는 방식.
• 예시 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 예시 사용
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

병합 정렬(Merge Sort)

• 시간 복잡도 : O(nlogn)
• 배열을 반으로 나눠서 재귀적으로 정렬 후, 나눠진 배열을 병합하면서 최종 정렬을 만듦 (배열의 길이가 1이 될 때까지 나눔)
• 예시 코드

def merge_sort(arr):
    # 배열의 길이가 2보다 작으면 이미 정렬된 상태이므로 그대로 반환
    if len(arr) < 2:
        return arr
    
    # 중간 인덱스 계산
    mid = len(arr) // 2
    
    # 배열을 두 개의 하위 배열로 나누고 재귀적으로 정렬
    left = merge_sort(arr[:mid])  # 왼쪽 하위 배열
    right = merge_sort(arr[mid:])  # 오른쪽 하위 배열

    # 두 개의 하위 배열을 병합하기 위한 배열 초기화
    merged_arr = []
    l = r = 0  # 왼쪽과 오른쪽 하위 배열의 인덱스 초기화

    # 두 하위 배열을 비교하여 정렬된 배열을 만듭니다
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged_arr.append(left[l])  # 왼쪽 배열의 요소를 추가
            l += 1  # 왼쪽 인덱스 증가
        else:
            merged_arr.append(right[r])  # 오른쪽 배열의 요소를 추가
            r += 1  # 오른쪽 인덱스 증가

    # 남은 요소가 있을 경우 추가
    merged_arr += left[l:]  # 왼쪽 배열에 남은 요소 추가
    merged_arr += right[r:]  # 오른쪽 배열에 남은 요소 추가

    return merged_arr  # 병합된 배열 반환

삽입 정렬(Insertion Sort)

• 시간 복잡도 : O(n^2)
• 1번 인덱스부터 시작해서 앞에 있는 요소들과 비교해서 현재 인덱스의 값보다 작은 값을 만나면 그 작은 값의 뒤에 삽입하는 방식
• 예시 코드

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 예시 사용
print(insertion_sort([12, 11, 13, 5, 6]))

퀵 정렬(Quick Sort)

• 시간 복잡도 : O(nlogn)
• 기준이 될 피벗을 선책하고 피벗보다 작은 값은 왼쪽에, 큰 요소는 오른쪽에 배치하는 방식
• 예시 코드

def quick_sort(arr):
    # 배열의 길이가 1 이하인 경우, 이미 정렬된 상태이므로 그대로 반환
    if len(arr) <= 1:
        return arr
    
    # 피벗(pivot) 설정: 배열의 중간 요소를 피벗으로 선택
    pivot = arr[len(arr) // 2]
    
    # 피벗보다 작은 요소들로 이루어진 배열 생성
    left = [x for x in arr if x < pivot]
    
    # 피벗과 같은 요소들로 이루어진 배열 생성
    middle = [x for x in arr if x == pivot]
    
    # 피벗보다 큰 요소들로 이루어진 배열 생성
    right = [x for x in arr if x > pivot]
    
    # 재귀적으로 왼쪽, 중간, 오른쪽 배열을 정렬하고 병합하여 반환
    return quick_sort(left) + middle + quick_sort(right)

# 예시 사용
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))  # 출력: [1, 1, 2, 3, 6, 8, 10]

힙 정렬(Heap Sort)

• 시간 복잡도 : O(nlogn)
• 완전 이진 트리를 이용한 최대 힙이나 최소 힙 트리 구조를 활용해 정렬하는 방식
• 배열로부터 최대 힙 구성 => 루트(가장 큰 값)에 배열 마지막 요소를 넣고 다시 최대 힙 구성
• 예시 코드

def heapify(arr, n, i):
    largest = i  # 현재 노드의 인덱스
    left = 2 * i + 1  # 왼쪽 자식 노드의 인덱스
    right = 2 * i + 2  # 오른쪽 자식 노드의 인덱스

    # 왼쪽 자식이 현재 노드보다 큰 경우
    if left < n and arr[i] < arr[left]:
        largest = left  # largest를 왼쪽 자식으로 업데이트

    # 오른쪽 자식이 현재 largest보다 큰 경우
    if right < n and arr[largest] < arr[right]:
        largest = right  # largest를 오른쪽 자식으로 업데이트

    # largest가 현재 노드가 아닌 경우
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        heapify(arr, n, largest)  # 재귀적으로 heapify 호출

def heap_sort(arr):
    n = len(arr)  # 배열의 길이

    # 배열을 힙으로 변환 (최대 힙 생성)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 힙에서 요소를 하나씩 꺼내어 정렬
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 최대 요소를 배열의 끝으로 이동 (swap)
        heapify(arr, i, 0)  # 남은 힙을 다시 힙화

    return arr  # 정렬된 배열 반환

# 예시 사용
print(heap_sort([12, 11, 13, 5, 6, 7]))  # 출력: [5, 6, 7, 11, 12, 13]

최종프로젝트

이전부터 계속 있던 문제의 원인을 찾았다. loadAssets.js는 이전에 사용했던 것을 가져와서 사용한것이니 문제가 없을거라 생각하고 getJobById가 값을 못찾는다 생각해서 이부분만 확인했었는데 알고보니
game.proto에서 C_Enter가 받는 payload값을 nickname과 job으로 해두고 정작 enterHandler에서는 nickname과 class를 받으려했다. 그러니 당연히 class값이 undefined가 뜨지...

위 사진과 같이 class => job으로 바꿔주니 잘 작동했다..이거한다고 시간 많이 버렷는데 간단한 문제였고 저번 개인 과제때처럼 오타검수를 해봣더라면 문제 없었을텐데..너무 아쉽다.