이코테 복습

자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조

• Overflow: 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입시 발생
• Underflow: 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행시 발생

Stack

• 선입후출 구조 (First In Last Out)
• Push(append), Pop(pop)

Queue

• 선입선출 구조 (First In First Out)
• Push(append), Pop(popleft)

그래프

• 인접 행렬 (Adjacency Matrix)
• 인접 리스트 (Adjacency List)

재귀함수

자기 자신을 다시 호출하는 함수(Recursive Function)

• 종료 조건을 꼭 명시해야 한다

DFS/BFS

DFS

깊이 우선 탐색 (Depth First Search)

• 재귀 함수를 사용 (Stack)

BFS

너비 우선 탐색 (Breath First Search)

• Queue 자료구조를 사용

음료수 얼려 먹기

• n*m 크기의 얼음틀, 0: 뚫린부분, 1: 칸막이
• 0끼리 상하좌우 붙어있는 경우 서로 연결된것으로 간주
• 총 아이스크림의 개수 출력

풀이특징

• DFS (재귀 사용)

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상, 하, 좌, 우

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]

def dfs(x, y):
    visited[x][y] = True
    # (x, y) 기준 인접한 상, 하, 좌, 우 탐색
    for move in moves:
        nx = x + move[0]
        ny = y + move[1]
        if nx < 0 or nx >= n:
            continue
        if ny < 0 or ny >= m:
            continue
        if visited[nx][ny] == False and graph[nx][ny] == 0:
            dfs(nx, ny)

count = 0
for x in range(n):
    for y in range(m):
        if visited[x][y] == False and graph[x][y] == 0:
            dfs(x, y)
            count += 1
            
print(count)

미로 탈출

• n*m 크기의 미로, 시작: (1, 1), 출구: (n, m)
• 괴물: 0, 없는부분: 1
• 탈출하기 위해 움직여야 하는 최소 칸의 수 출력

풀이특징

• BFS (queue 사용)

from collections import deque
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상, 하, 좌, 우

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

def bfs():
    que = deque()
    que.append((0, 0))
    
    while que:
        x, y = que.popleft()
        for move in moves:
            nx = x + move[0]
            ny = y + move[1]
            
            if nx < 0 or nx >= n:
                continue
            if ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                que.append((nx, ny))

dfs()
print(graph[n-1][m-1])

정렬

선택 정렬 (Selection Sort)

O(n^2)

def sort(array):
    for i in range(len(array)):
        min_index = i
        for j in range(i+1, len(array)):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]

삽입 정렬 (Insertion Sort)

거의 정렬되어 있을 때 효율적
O(n^2)

def sort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
            else:
                break

퀵 정렬 (Quick Sort)

거의 정렬되어 있는 경우 비효율적
O(N log N)

def sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return sort(left_side) + [pivot] + sort(right_side)

계수 정렬 (Counting Sort)

데이터 개수(N) 제한, 최댓값(K) 제한 상황
O(N + K)

def sort(array):
    count = [0]*(max(array)+1)
    
    for i in range(len(array)):
        count[array[i]] += 1
    
    sorted = []
    for i in range(len(count)):
        sorted.extend([i]*count[i])
        
    return sorted

병합 정렬 (Merge Sort)

분할(Divide), 정복(Conquer), 결합(Combine)
O(N log N)

def merge_sort(array):
    if len(array) <= 1:
        return array
    # Devide
    mid = len(array) // 2
    left_sorted = merge_sort(array[:mid])
    right_sorted = merge_sort(array[mid:])
    
    # Combine
    sorted = []
    l = 0
    r = 0
    
    while l < len(left_sorted) and r < len(right_sorted):
        if left_sorted[l] < right_sorted[r]:
            sorted.append(left_sorted[l])
            l += 1
        else:
            sorted.append(right_sorted[r])
            r += 1
    
    sorted.extend(left_sorted[l:])
    sorted.extend(right_sorted[r:])
    
    return sorted

병합 정렬 블로그

위에서 아래로

• 내림차순 정리

n = int(input())
array = [int(input) for _ in range(n)]
array.sort(reverse=True)

for i in array:
    print(i, end=" ")

성적이 낮은 순서로 학생 출력하기

• 이름과 성적 입력, 성적오름차순 정렬 후 이름 출력

n = int(input())
array = []
for _ in range(n):
    name, score = input().split()
    array.append((name, int(score)))

array.sort(key = lambda x: x[1])
for student in array:
    print(student[0], end=" ")

두 배열의 원소 교체

• n개원소인 두 a, b 배열
• 최대 k번 a 와 b 배열 원소끼리 교체 가능
• a 배열 원소합이 최댓값 출력

n, k = map(int, input().split())
array_a = list(map(int, input().split()))
array_b = list(map(int, input().split()))

array_a.sort()
array_b.sort(reverse=True)

for i in range(k):
    if array_a[i] < array_b[i]:
        array_a[i], array_b[i] = array_b[i], array_a[i]
    else:
        break

print(sum(array_a))

이진 탐색

O(log N)

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if target == array[mid]:
            return mid
        elif target < array[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1

부품 찾기

• n개의 부품, m개의 부품을 주분받는다
• 부품 순으로 있으면 yes, 없으면 no를 출력

풀이특징

• 이진 탐색 활용 가능
• set + in 조합도 가능

import sys
input = sys.stdin.readline

n = int(input())
items = list(map(int, input().split()))
m = int(input())
orders = list(map(int, input().split()))

items.sort()

def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if target == items[mid]:
            return True
        elif target < items[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return False

for i in orders:
    print("yes" if binary_search(i, 0, len(items)-1) else "no", end=" ")

import sys
input = sys.stdin.readline

n = int(input())
items = set(map(int, input().split()))
m = int(input())
orders = list(map(int, input().split()))

for i in orders:
    print("yes" if i in items else "no", end=" ")

떡볶이 떡 만들기

• n개의 떡과 m 길이의 떡을 요청
• n개의 떡들을 높이 h로 잘랐을 경우 남은 부분들의 총합이 m이 되도록
• 높이 h의 최댓값을 출력

풀이특징

• 파라메트릭 서치

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
heights = list(map(int, input().split()))
heights.sort()

def getSum(h):
    sum = 0
    for i in heights:
        if i > h:
           sum += (i - h)
    return sum

def parametric_search(start, end, sum):
    temp = 0
    while start <= end:
        mid = (start + end) // 2
        currentSum = getSum(mid)
        if currentSum == sum:
            return mid
        elif currentSum < sum:
            end = mid - 1
        else:
            temp = mid
            start = mid + 1
    return temp

print(parametric_search(min(heights), max(heights), m))