코딩 테스트 면접 대비 v 1.0 (손 코딩 테스트) - Python

문지은·2024년 6월 21일

algorithm coding test data structure python

Algorithm with Python

목록 보기

19/19

코딩 테스트 면접을 준비하며 자료구조와 빈출 주제 위주로 정리하였습니다.

배열

회문(Palindromes) 찾기 ⭐

왼쪽 포인터는 0번 인덱스를, 오른쪽 포인터는 마지막 인덱스를 가리킨다.
왼쪽 포인터의 위치가 오른쪽 포인터보다 작으면 반복한다.
- 각 포인터가 가리키는 문자를 비교한다.
- 다르면 False를 반환한다.
반복문을 빠져나오면 True를 반환한다.

def is_palindrome(word):
    left = 0
    right = len(word)-1
    while left < right:
        if word[left] != word[right]:
            return False
        left, right = left + 1, right - 1
    return True

최댓값, 최솟값 찾기

def find_max_min(arr):

    max_value = arr[0]
    min_value = arr[0]

    for i in range(1, len(arr)):
        if arr[i] > max_value:
            max_value = arr[i]
        if arr[i] < min_value:
            min_value = arr[i]

    return max_value, min_value

가장 큰 두 수 찾기

def find_max_two(arr):
    if len(arr) < 2:
        return arr
    max1, max2 = arr[:2]
    if max2 > max1:
        max1, max2 = max2, max1
    for n in arr[2:]:
        if n > max1:
            max1, max2 = n, max1
        elif n > max2:
            max2 = n
    return [max1, max2]

투 포인터

배열 뒤집기

def reverse_array(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

    return arr

Two Sum

더해서 target이 되는 두 숫자의 인덱스 찾기

def twoSum(nums, target):
    # 숫자와 숫자의 원래 인덱스를 저장하는 2차원 배열을 생성한다.
    nums = [[n, i] for i, n in enumerate(nums)]
    # 배열을 숫자의 오름차순으로 정렬한다.
    nums.sort(key=lambda x: x[0])
    # 첫 번째 인덱스와 마지막 인덱스를 각각 가리키는 두 포인터를 생성한다.
    l, r = 0, len(nums) - 1

    # 왼쪽 포인터가 오른쪽 포인터보다 작을 동안 반복한다.
    while l < r:
        num_sum = nums[l][0] + nums[r][0]
        # 만약 두 포인터가 가리키는 숫자의 합이 target과 같으면 결과 출력한다.
        if num_sum == target:
            return [nums[l][1], nums[r][1]]
        # 합이 target보다 크면 오른쪽 포인터를 왼쪽으로 한칸 옮긴다.
        elif num_sum > target:
            r -= 1
        # 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로 한칸 옮긴다.
        else:
            l += 1

0과 1로 구성된 배열 정렬하기

def bin_array_sort(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        while left < len(arr) and arr[left] == 0:
            left += 1
        while right >= 0 and arr[right] == 1:
            right -= 1
        if left < right:
            arr[left], arr[right] = 0, 1
            left, right = left + 1, right - 1

문자열

Anagram 판별하기 ⭐

정렬 사용 - $O(nlogn)$

def are_anagrams(str1, str2):
    # 길이가 다르면 애너그램이 될 수 없음
    if len(str1) != len(str2):
        return False
    
    # 두 문자열을 정렬하여 비교
    return sorted(str1) == sorted(str2)

해시 테이블(딕셔너리)을 사용 - $O(n)$

def are_anagrams(str1, str2):
    # 길이가 다르면 애너그램이 될 수 없음
    if len(str1) != len(str2):
        return False
    
    # 두 문자열의 각 문자의 빈도를 저장할 딕셔너리
    count1 = {}
    count2 = {}

    # str1의 각 문자의 빈도 계산
    for char in str1:
        if char in count1:
            count1[char] += 1
        else:
            count1[char] = 1
    
    # str2의 각 문자의 빈도 계산
    for char in str2:
        if char in count2:
            count2[char] += 1
        else:
            count2[char] = 1
    
    # 두 빈도 딕셔너리를 비교
    return count1 == count2

문자열 안에 문자들이 고유한 문자인지 확인 (중복 문자열 확인)

정렬 사용 - $O(nlogn)$

def has_unique_chars(s):
    sorted_s = sorted(s)
    for i in range(1, len(sorted_s)):
        if sorted_s[i] == sorted_s[i - 1]:
            return False
    return True

해시 테이블 사용 - $O(n)$

def has_unique_chars(s):
    char_set = {}
    for char in s:
        if char in char_set:
            return False
        char_set[char] = True
    return True

문자열 뒤집기

def reverse_string(s):
    reversed_s = ""
    for char in s:
        reversed_s = char + reversed_s
    return reversed_s

연결 리스트

단일 연결 리스트 구현하기 ⭐⭐

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        # 연결 리스트의 머리(head) 노드
        self.head = None

		# 리스트의 끝에 새 노드를 추가
    def append(self, data):
        # 새 노드를 생성
        new_node = Node(data)
        # 리스트가 비어있으면 새 노드를 머리로 설정
        if self.head is None:
            self.head = new_node
            return
        # 리스트의 마지막 노드를 찾음
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        # 마지막 노드의 다음을 새 노드로 설정
        last_node.next = new_node

		# 리스트의 머리에 새 노드를 추가
    def prepend(self, data):
        # 새 노드를 생성
        new_node = Node(data)
        # 새 노드의 다음을 현재 머리로 설정
        new_node.next = self.head
        # 머리를 새 노드로 업데이트
        self.head = new_node

		# 주어진 키를 가진 첫 번째 노드를 삭제
    def delete_node(self, key):
        # 현재 노드를 머리로 설정
        current_node = self.head

        # 삭제할 노드가 머리에 있는 경우
        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return

        # 삭제할 노드를 찾음
        previous_node = None
        while current_node and current_node.data != key:
            previous_node = current_node
            current_node = current_node.next

        # 삭제할 노드를 찾지 못한 경우
        if current_node is None:
            return

        # 이전 노드의 다음을 삭제할 노드의 다음으로 설정
        previous_node.next = current_node.next
        current_node = None

		# 주어진 키를 가진 노드를 검색
    def search(self, key):
        # 현재 노드를 머리로 설정
        current_node = self.head
        # 노드를 순회하며 키를 찾음
        while current_node and current_node.data != key:
            current_node = current_node.next
        # 키를 찾으면 True, 아니면 False 반환
        return current_node is not None

		# 리스트의 모든 노드를 순회하며 데이터 값을 출력
    def print_list(self):
        # 현재 노드를 머리로 설정
        current_node = self.head
        # 노드를 순회하며 데이터 값을 출력
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

스택, 큐

Stack 구현하기 ⭐

class Stack:
    def __init__(self):
        # 내부 리스트를 사용하여 스택 요소를 저장
        self.stack = []

    def push(self, item):
        # 스택의 맨 위에 요소를 추가
        self.stack.append(item)

    def pop(self):
        # 스택이 비어있는 경우 예외 처리
        if self.is_empty():
            raise IndexError("pop from empty stack")
        # 스택의 맨 위 요소를 제거하고 반환
        return self.stack.pop()

    def peek(self):
        # 스택이 비어있는 경우 예외 처리
        if self.is_empty():
            raise IndexError("peek from empty stack")
        # 스택의 맨 위 요소를 반환 (제거하지 않음)
        return self.stack[-1]

    def is_empty(self):
        # 스택이 비어있는지 여부를 반환
        return len(self.stack) == 0

    def size(self):
        # 스택의 요소 개수를 반환
        return len(self.stack)

    def print_stack(self):
        # 스택의 모든 요소를 출력
        print(self.stack)

스택 응용 문제

단어 역순으로 출력하기

def reverse_word(word: str) -> str:
    answer: str = ""
    s = Stack()
    for w in word:
        s.push(w)
    while not s.is_empty():
        answer += s.pop()
    return answer

괄호 짝 확인하기
- 수식에서 한 문자씩 가져와서 반복한다.
  - 왼쪽 괄호가 나오면 스택에 넣는다.
  - 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호를 하나 뺀다.
  - 스택이 비었으면, False 반환한다.
- 모두 검사했는데, 스택이 비었으면 True를 반환하고, 그렇지 않으면 False를 반환한다.

def check_bracket(expression):
    s = Stack()
    for exp in expression:
        if exp == "(":
            s.push(exp)
        elif exp == ")":
            if not s.pop():
                return False
    return True if s.is_empty() else False

배열의 각 요소의 다음 큰 요소(Next Greater Element, NGE) 찾기

def find_nge(arr)]:
    n = len(arr)
    stack = []
    res = [-1] * n
    for i in range(n-1, -1, -1):
        while stack:
            if stack[-1] > arr[i]:  # 스택의 맨 위 요소가 현재 요소보다 큰 경우 NGE
                res[i] = stack[-1]
                break
            else:
                stack.pop()
        stack.append(arr[i])
    return res

Queue 구현하기 ⭐

class Queue:
    def __init__(self):
        # 내부 리스트를 사용하여 큐 요소를 저장
        self.queue = []

    def enqueue(self, item):
        # 큐의 끝에 요소를 추가
        self.queue.append(item)

    def dequeue(self):
        # 큐가 비어있는 경우 예외 처리
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        # 큐의 맨 앞 요소를 제거하고 반환
        return self.queue.pop(0)

    def front(self):
        # 큐가 비어있는 경우 예외 처리
        if self.is_empty():
            raise IndexError("front from empty queue")
        # 큐의 맨 앞 요소를 반환 (제거하지 않음)
        return self.queue[0]

    def is_empty(self):
        # 큐가 비어있는지 여부를 반환
        return len(self.queue) == 0

    def size(self):
        # 큐의 요소 개수를 반환
        return len(self.queue)

    def print_queue(self):
        # 큐의 모든 요소를 출력
        print(self.queue)

큐 응용 문제

1 번부터 N 번까지 원을 이루고 앉아있는 사람들 중에서 순서대로 K 번째 사람 제거하기 (요세푸스 순열)
- K 번째마다 제거한다면 K-1번 dequeue 해서 enqueue 하고 K 번째 dequeue로 제거 대상을 제거 (반복)!

def josephus_q(n, k):
    res = []
    q = Queue()

    # 큐에 사람들을 추가 (1부터 n까지)
    for i in range(n):
        q.enqueue(i + 1)

    # Josephus 문제 해결
    while q.size() > 1:
        # k-1번 dequeued된 요소를 다시 enqueue하여 순환시킴
        for _ in range(k - 1):
            q.enqueue(q.dequeue())
        # k번째 사람을 큐에서 제거하고 결과 리스트에 추가
        res.append(q.dequeue())

    # 마지막 남은 사람을 결과 리스트에 추가
    res.append(q.dequeue())

    return res

이진수 만들기

def generate_binary_numbers(n):
    result = []
    q = Queue()

    # 큐에 첫 번째 이진수 "1" 추가
    q.enqueue("1")

    # n번 반복
    for _ in range(n):
        # 큐에서 요소 꺼내기
        current = q.dequeue()
        result.append(current)

        # 새로운 이진수 생성하여 큐에 추가
        q.enqueue(current + "0")
        q.enqueue(current + "1")

    return result

Stack 두 개를 이용하여 Queue 구현하기 ⭐⭐

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있다.

구현 방법

enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 하자.

두 개의 stack으로 queue를 구현하는 방법은 다음과 같다.

enqueue() :: instack에 push()를 하여 데이터를 저장한다.
dequeue() ::
1. 만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣는다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.
2. outstack.pop()을 하면 가장먼저 왔던 데이터가 가정 먼저 추출된다.(FIFO)

시간 복잡도

enqueue() : instack.push()만 하면 되기 때문에 O(1)의 시간복잡도를 갖는다.
dequeue() : outstack.pop()만 하면 되기 때문에 O(1)의 시간복잡도를 갖는다.
- outstack이 비어있는 경우 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 한다. 따라서 총 2*n 번의 operation이 실행되어야 하므로 O(n)의 시간복잡도를 갖는다. (worst case)

class Queue(object):
    def __init__(self):
        self.instack=[]
        self.outstack=[]

    def enqueue(self,element):
        self.instack.append(element)

    def dequeue(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

Queue 두 개를 이용하여 Stack 구현하기 ⭐⭐

구현 방법

push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 하자.

두 개의 queue로 stack을 구현하는 방법은 다음과 같다.

push() :: q1으로 enqueue()를 하여 데이터를 저장한다.
pop() ::
1. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()한다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
2. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
3. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

시간 복잡도

push() : q1.enqueue()를 한번만 하면 되기 때문에 $O(1)$ 의 시간복잡도를 갖는다.
pop() : q1에 저장되어 있는 n개의 원소중에 n-1개를 q2로 옮겨야 하므로 $O(n)$ 이 된다.

import queue

class Stack(object):
    def __init__(self):
        self.q1 = queue.Queue()
        self.q2 = queue.Queue()

    def push(self, element):
        self.q1.put(element)

    def pop(self):
        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())

        temp = self.q1
        self.q1 = self.q2
        self.q2 = temp

        return self.q2.get()

원형 큐 구현하기 ⭐

큐의 끝이 다시 처음으로 연결되는 구조를 가진 큐

class CircularQueue:
    def __init__(self, capacity):
        # 큐의 최대 용량을 설정
        self.capacity = capacity
        # 큐의 요소를 저장할 리스트를 초기화, 초기에는 None으로 채움
        self.queue = [None] * capacity
        # 큐의 첫 번째 요소를 가리키는 인덱스
        self.front = -1
        # 큐의 마지막 요소를 가리키는 인덱스
        self.rear = -1

    def is_full(self):
        # 큐가 가득 찼는지 확인
        # rear의 다음 위치가 front와 같다면 큐가 가득 찬 상태
        return (self.rear + 1) % self.capacity == self.front

    def is_empty(self):
        # 큐가 비어있는지 확인
        # front가 -1이면 큐는 비어 있음
        return self.front == -1

    def enqueue(self, item):
        # 큐에 요소를 추가
        if self.is_full():
            raise OverflowError("Circular Queue is full")
        if self.is_empty():
            # 큐가 비어있으면 front를 0으로 설정
            self.front = 0
        # rear를 순환하여 다음 위치를 가리키게 함
        self.rear = (self.rear + 1) % self.capacity
        # 큐의 rear 위치에 새로운 요소를 추가
        self.queue[self.rear] = item

    def dequeue(self):
        # 큐에서 요소를 제거하고 반환
        if self.is_empty():
            raise IndexError("Circular Queue is empty")
        # front 위치의 요소를 임시 저장
        item = self.queue[self.front]
        # 큐에 요소가 하나만 있는 경우
        if self.front == self.rear:
            # 큐를 비우므로 front와 rear를 초기 상태로 설정
            self.front = -1
            self.rear = -1
        else:
            # front를 순환하여 다음 위치를 가리키게 함
            self.front = (self.front + 1) % self.capacity
        return item

    def peek(self):
        # 큐의 맨 앞 요소를 제거하지 않고 반환
        if self.is_empty():
            raise IndexError("Circular Queue is empty")
        return self.queue[self.front]

    def print_queue(self):
        # 큐의 모든 요소를 출력
        if self.is_empty():
            print("Circular Queue is empty")
            return
        if self.rear >= self.front:
            # rear가 front보다 크거나 같은 경우
            # front부터 rear까지의 요소를 출력
            print("Queue:", self.queue[self.front:self.rear + 1])
        else:
            # rear가 front보다 작은 경우 (순환이 발생한 경우)
            # front부터 끝까지와 시작부터 rear까지의 요소를 출력
            print("Queue:", self.queue[self.front:] + self.queue[:self.rear + 1])

해시 테이블

해시 테이블 구현하기 - 체이닝 방법

같은 해시 값을 가지는 키가 여러 개일 수 있기 때문에 충돌 처리가 필요
- 체이닝(Chaining)을 이용해서 충돌을 처리
- 동일한 버킷에 여러 키-값 쌍을 리스트 형태로 저장하는 방법

class HashTable:
    def __init__(self, length=5):
        self.max_len = length
        self.table = [[] for _ in range(self.max_len)]

    def _hash(self, key):
        # 키의 각 문자의 아스키 값을 더하고 테이블 크기로 나눈 나머지를 해시 값으로 사용
        res = sum([ord(s) for s in key])
        return res % self.max_len

    def set(self, key, value):
        # 키에 대한 해시 값을 계산하여 인덱스를 얻음
        index = self._hash(key)
        # 해당 인덱스의 리스트에 키-값 쌍을 추가
        self.table[index].append((key, value))

    def get(self, key):
        # 키에 대한 해시 값을 계산하여 인덱스를 얻음
        index = self._hash(key)
        # 해당 인덱스의 리스트를 검색하여 키가 일치하는 값을 찾음
        value = self.table[index]
        if not value:
            return None
        for v in value:
            if v[0] == key:
                return v[1]
        return None

중복된 값 찾기

def find_duplicates(arr):
    # 해시 테이블 역할을 하는 딕셔너리
    hash_table = {}
    # 중복된 값을 저장할 리스트
    duplicates = []

    # 배열의 각 요소를 순회
    for value in arr:
        # 값이 해시 테이블에 이미 존재하는지 확인
        if value in hash_table:
            # 중복된 값이 이미 저장되어 있는지 확인 후 추가
            if value not in duplicates:
                duplicates.append(value)
        else:
            # 해시 테이블에 값을 추가
            hash_table[value] = True

    return duplicates

합이 0인 부분 배열 중 가장 긴 배열 길이 구하기

def maxLen_dic(arr):
    dic = {0: -1}  # 초기 딕셔너리
    ans = 0  # 최대 길이 초기화
    total = 0  # 부분 누적 합 초기화

    for i in range(len(arr)):
        total += arr[i]  # 현재 인덱스까지의 누적 합 계산
        if total in dic:
            # 현재 인덱스와 누적 합이 처음 등장한 인덱스 사이의 부분 배열 길이 계산
            ans = max(ans, i - dic[total])
        else:
            # 누적 합이 처음 등장했으므로 인덱스를 딕셔너리에 추가
            dic[total] = i
    
    return ans  # 최대 길이 반환

트리

트리 순회

레벨 순서 순회(Level order traversal)

def levelorder(tree):
    if not tree:
        return []
    res, queue = [], [0]

    while queue:
        index = queue.pop(0)
        res.append(tree[index])
        index = 2 * index + 1
        if index < len(tree) and tree[index] is not None:
            queue.append(index)
        index += 1
        if index < len(tree) and tree[index] is not None:
            queue.append(index)
    return res

from collections import deque

def levelorder(root):
    visited = []
    if root is None:
        return 0
    q = deque()
    q.append(root)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

전위 순회(Preorder traversal)

def preorder(root):
	if root is None:
		return
	print(root)
	preorder(root.left)
	preorder(root.right)

def preorder(tree):
    if not tree:
        return []
    res, stack = [], [0]

    while stack:
        index = stack.pop()
        res.append(tree[index])
        index = 2 * index + 2
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
        index -= 1
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
    return res

중위 순회(Inorder traversal)

def inorder(root):
	if root is None:
		return
	inorder(root.left)
	print(root)
	inorder(root.right)

def inorder(tree):
    if not tree:
        return []
    index = 0
    res, stack = [], []

    while True:
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
            index = 2 * index + 1
        elif stack:
            index = stack.pop()
            res.append(tree[index])
            index = 2 * index + 2
        else:
            break
    return res

후위 순회(Postorder traversal)

def postorder(root):
	if root is None:
		return
	postorder(root.left)
	postorder(root.right)
	print(root)

def postorder(tree):
    if not tree:
        return []
    res, stack = [], [0]
    visit_order = []

    while stack:
        index = stack.pop()
        visit_order.append(index)
        index = 2 * index + 1
        if index < len(tree) and tree[index] is not None:
            stack.append(index)
        index = index + 1
        if index < len(tree) and tree[index] is not None:
            stack.append(index)

    while visit_order:
        index = visit_order.pop()
        res.append(tree[index])
    return res

힙(Heap)

heappush, heappop 구현하기 - min heap

def heappush(heap, data):
    heap.append(data)
    # 추가한 원소의 인덱스를 구한다.
    current = len(heap) - 1
    # 현재 원소가 루트(인덱스 0)에 도달하면 종료
    while current > 0:
        # 추가한 원소의 부모 인덱스를 구한다.
        parent = (current - 1) // 2
        # 새 값이 부모의 값보다 작으면 값을 교환
        if heap[parent] > heap[current]:
            heap[parent], heap[current] = heap[current], heap[parent]
            # 추가한 원소의 인덱스를 갱신한다.
            current = parent
        else:
            break
            
def heappop(heap):
    if not heap:
        return "Empty Heap!"
    elif len(heap) == 1:
        return heap.pop()

    pop_data, heap[0] = heap[0], heap.pop()
    current, child = 0, 1
    while child < len(heap):
        sibling = child + 1
        if sibling < len(heap) and heap[child] > heap[sibling]:
            child = sibling
        if heap[current] > heap[child]:
            heap[current], heap[child] = heap[child], heap[current]
            current = child
            child = current * 2 + 1
        else:
            break
    return pop_data

heapify 구현하기 - min heap

def heapify(arr):
    last = len(arr) // 2 - 1
    for current in range(last, -1, -1):
        while current <= last:
            child = current * 2 + 1
            sibling = child + 1
            if sibling < len(arr) and arr[child] > arr[sibling]:
                child = sibling
            if arr[current] > arr[child]:
                arr[current], arr[child] = arr[child], arr[current]
                current = child
            else:
                break

그래프

DFS

재귀

visited = []

def dfs(cur_v):
    visited.append(cur_v)
    for v in graph[cur_v]:
        if v not in visited:
            dfs(v)

스택

def dfs(graph, node):
    # 방문할 노드를 저장한 스택과 방문 여부를 확인한 집합을 만든다.
    # 스택과 집합에 방문할 첫 노드를 넣는다.
    res = []
    stack = [node]
    visited = set(stack)

    # 스택이 빌 때까지 반복한다.
    while stack:
        # 스택에서 노드를 꺼내고 방문처리한다.
        u = stack.pop()
        res.append(u)

        # 현재 노드에 연결된 다른 노드를 확인한다.
        # 다른 노드가 아직 방문하지 앟는 노드이면, 스택과 집합에 넣는다.
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                stack.append(v)
    return res

BFS

from collections import deque

def bfs(graph, start_v):
    visited = [start_v]
    queue = deque(start_v)
    while queue:
        cur_v = queue.popleft()
        for v in graph[cur_v]:
            if v not in visited:
                visited.append(v)
                queue.append(v)
    return visited

정렬 알고리즘

버블 정렬

인접한 두 개의 원소를 비교하여 크기가 작은 원소를 왼쪽으로, 큰 원소를 오른쪽으로 교환하는 과정을 반복하여 정렬하는 알고리즘
시간 복잡도 : $O(n^2)$

def bubble_sort(arr):
    n = len(arr)
    # 반복문을 돌면서 인접한 두 원소를 비교
    for i in range(n-1):
        for j in range(n-i-1):
            # 현재 원소가 다음 원소보다 크면 두 원소의 위치를 바꿈
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

선택 정렬

배열에서 최소값을 찾아 가장 앞에 있는 값과 교환하고, 그 다음으로 작은 값을 찾아 그 다음 위치의 값과 교환하는 방식으로 정렬
시간 복잡도 : $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

삽입 정렬 ⭐⭐

두 번째 인덱스부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후 원소를 뒤로 옮기고 지정된 자리에 원소를 삽입하며 정렬
시간 복잡도 : $O(n^2)$

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

퀵 정렬 ⭐⭐

분할 정복(divide and conquer) 방법을 기반으로 한 정렬 알고리즘 중 하나
1. 리스트 중 하나의 원소(pivot)를 선택
2. pivot을 기준으로 리스트를 두 개의 부분 리스트로 나눈다.
3. pivot보다 작은 값은 왼쪽 부분 리스트, 큰 값은 오른쪽 부분 리스트에 위치시킨다.
4. 각 부분 리스트에 대해 1단계부터 재귀적으로 수행한다.
5. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
시간 복잡도 : $O(nlogn)$

def quicksort(arr):
    # 배열의 크기가 1 이하이면 정렬할 필요가 없으므로 해당 배열을 반환한다.
    if len(arr) <= 1:
        return arr
    
    # 배열의 가운데 값을 pivot으로 지정한다.
    pivot = arr[len(arr) // 2]
    
    # pivot을 기준으로 작은 값은 left 배열, 큰 값은 right 배열, 같은 값은 equal 배열에 담는다.
    left = []
    right = []
    equal = []
    for num in arr:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            equal.append(num)
    
    # left, equal, right 배열을 각각 재귀적으로 정렬한 후 합쳐서 반환한다.
    return quicksort(left) + equal + quicksort(right)

퀵 정렬 - K 번째 큰 수 구하기 ⭐

def quick_select(arr, left, right, k):
    # 배열의 left에서 right까지 부분에서 k번째 큰 수를 찾는 함수
    if left <= right:
        pivot_index = partition(arr, left, right)
        
        if pivot_index == k:
            # 피벗 인덱스가 k와 같으면 피벗 위치의 값이 k번째 큰 수
            return arr[pivot_index]
        elif pivot_index < k:
            # 피벗 인덱스가 k보다 작으면 오른쪽 부분 배열에서 탐색
            return quick_select(arr, pivot_index + 1, right, k)
        else:
            # 피벗 인덱스가 k보다 크면 왼쪽 부분 배열에서 탐색
            return quick_select(arr, left, pivot_index - 1, k)

def partition(arr, left, right):
    # 배열을 피벗을 기준으로 나누는 함수
    pivot = arr[right]
    i = left - 1
    
    for j in range(left, right):
        if arr[j] >= pivot:  # 내림차순으로 정렬하기 위해 `>=` 사용
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

def find_kth_largest(arr, k):
    # k번째 큰 수를 찾는 함수 (k를 0부터 시작하는 인덱스로 조정)
    return quick_select(arr, 0, len(arr) - 1, k - 1)

힙 정렬

힙(Heap) 자료구조를 이용하여 구현
주어진 배열을 힙으로 만들고, 가장 큰 값을 추출하여 배열의 뒤부터 차례대로 저장하는 방식으로 정렬
시간 복잡도 : $O(nlogn)$

def heapify(arr, n, i):
    """
    주어진 배열을 힙으로 만드는 함수입니다.
    """
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[largest] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    """
    Heap Sort 알고리즘을 구현한 함수입니다.
    """
    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[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr

피보나치 알고리즘 ⭐⭐

재귀를 이용한 피보나치

def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

메모이제이션을 이용한 피보나치

def fibo(n, memo):
    if memo[n] != 0:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo)
    return memo[n]
    
memo = [0] * (n + 1)

반복문(동적계획법) 이용한 피보나치

def fibo(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

팩토리얼

반복문을 이용한 팩토리얼

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

재귀를 이용한 팩토리얼 ⭐

def factorial_recursive(n):
    if n <= 1:
        return 1
    else:
        return n * factorial_recursive(n - 1)

메모이제이션을 이용한 팩토리얼

def factorial_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = 1
    else:
        memo[n] = n * factorial_memoization(n - 1, memo)
    return memo[n]

팩토리얼 수 중에 0인 것 찾기 ⭐

주어진 숫자의 팩토리얼 결과에서 끝자리의 0이 몇개인지 구하는 문제
끝자리의 0은 곱해진 수에서 10의 개수에 의해 결정되므로, 2와 5가 얼마나 많이 곱해졌는지 확인하면 된다.
- 팩토리얼 수에서 2의 개수는 항상 5의 개수보다 많으므로, 5의 개수만 세면 된다.

def count_trailing_zeros(n):
    count = 0
    while n >= 5:
        count += n // 5
        n //= 5
    return count

정수론

소수 구하기 ⭐

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

에라토스테네스의 체 알고리즘

import math

n = int(input()) # 2부터 n까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            array[i * j] = False
            j += 1

최소 공배수, 최대 공약수 구하기 - 유클리드 호제법 ⭐

# 최대공약수 구하기
def gcd(a, b):
    # b가 0이면 a가 최대 공약수
    if b == 0:
        return a
    else:
        #  a를 b로 나눈 나머지를 구하여 재귀호출
        return gcd(b, a % b)

# 최소 공배수 = 두 수의 곱을 두 수의 최대공약수로 나눈 값 
lcm = a * b // gcd(a, b)

기타 ⭐

석차 구하기

def calculate_ranks(scores):
    n = len(scores)
    ranks = [1] * n  # 모든 학생의 초기 순위를 1로 설정

    for i in range(n):
        for j in range(n):
            if scores[i] < scores[j]:  # 다른 점수가 더 높은 경우
                ranks[i] += 1  # 현재 학생의 순위를 증가

    return ranks

진수 변환

def decimal_to_base(n, base):
    if n == 0:
        return "0"
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    result = ""
    while n > 0:
        result = digits[n % base] + result
        n = n // base
    return result

References

손코딩 테스트 대비
기술 면접 - 손코딩
손코딩 면접 준비
좌충우돌, 파이썬으로 자료구조 구현하기
[Python] 파이썬 정렬 알고리즘 구현 (선택정렬, 삽입정렬, 퀵정렬, 힙정렬, 버블정렬)

문지은

코드로 꿈을 펼치는 개발자의 이야기, 노력과 열정이 가득한 곳 🌈

이전 포스트