짧은코딩

최적의 해를 구하기 위해 시간 소요가 많거나 메모리를 많이 차지하는 문제는 컴퓨터로도 해결하기 어렵다. 그래서 연산 속도, 메모리를 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 어떤 문제는 메모리 공간을 약간만 더 사용하면 속도를 비약적으로 증가시킬 수 있다. 이런 것을 동적 계획법이라고 한다. 다이나믹 프로그래밍 방식은 탑다운, 보텀업 2가지 방식이 있다. 특히 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법도 있다. 프로그래밍에서 다이나믹은 '프로그램 실행되는 도중에'라는 의미이다. 하지만 다이나믹 프로그램에서 '다이나믹'은 이런 의미가 아니다. -피보나치 수열 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시는 피보나치 수열이 있다. 피보나치 수열의 점화식(인접한 항..

이 문제는 전형적인 이진 탐색 문제이자 파라메트릭 서치 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 예/아니요로 답하는 문제인 결정 문제로 바꾸어 해결하는 기법이다. 이 문제 풀이는 절단기 높이를 반복해서 조정하는 것이다. 당연한 말이지만 절단기 높이는 0부터 가장 긴 떡의 길이 안에 있어야 한다. 따라서 절단기의 범위인 0~가장 긴 떡의 길이를 고려하면 된다. start는 0이고 end는 가장 긴 떡의 길이로 두면 된다. 내 풀이 n, m = map(int, input().split()) ary = list(map(int, input().split())) ary.sort() def search(ary, target, start, end): mid = (start + end) // 2 sum = 0..

내 풀이(이진 탐색을 어이없게 구현하지 못함) # 이진 탐색 def binary(ary, target, start, end): left = start mid = (start + end) // 2 right = end if left > right: return "no" if target == ary[mid]: return "yes" elif target < ary[mid]: return binary(ary, target, left, mid-1) else: return binary(ary, target, mid+1, right) n = int(input()) ary = list(map(int, input().split())) ary.sort() m = int(input()) chk = list(map(int..

트리 이진 탐색의 전제 조건은 데이터가 정렬되어 있어야 한다. DB는 내부적으로 대용량 데이터 처리에 적합한 트리 구조를 사용하여 데이터가 항상 정렬되어 있다. 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있다. 1. 트리는 부모, 자식 노드로 구성 2. 최상단 노드 = 루트 노드 3. 최하단 노드 = 단말 노드 4. 일부를 때어내도 트리 구조이며 서브 트리라고 부른다. 5. 파일 시스템처럼 계층적이고 정렬된 데이터를 다루기 적합하다. 이진 탐색 트리 트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 1. 부모 노드보다 왼쪽 자식 노드가 작다. 2. 부모 노드보다 오른쪽 자식 노드가 크다. -이진 탐색 트리 1. 위 그림에서 37를 찾기 위해서는 먼저 루트 노드부..

이진 탐색은 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 순차 탐색 순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 원하는 원소를 찾을 수 있다. 순차 탐색은 이름처럼 순차적으로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하여 검사하여 구현도 간단하다. for문 한번으로 구현할 수 있어서 최악의 경우 시간 복잡도는 O(N)이다. 이진 탐색(반으로 쪼개면서 탐색하기) 이진 탐색은 데이터가 정렬되어 있어야지만 사용 가능하다. 이진 탐색은 범위를 절반씩 좁혀가며 탐색하는 특징이 있다. 이진 탐색은 시..

-처음에 생각한 풀이 처음엔 max, min 메소드를 이용하면 될 것이라고 생각했지만 이거로는 충분하지 않았다. -풀이 n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() #오름차순 b.sort(reverse=True) #내림차순 for i in range(k): if a[i] < b[i]: a[i], b[i] = b[i], a[i] else: break print(sum(a)) a를 오름차순, b를 내림차순으로 입력 받는다. 그리고 k만큼 반복하면서 비교한다. 만약 a가 b보다 작으면 두 집합의 원소를 바꾼다. a가 b보다 같거나 커지면 반복문을 종료한..

이 문제는 최대 100,000개까지 입력이 가능하여 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. -내 풀이 n = int(input()) def setting(data): return data[1] ary = [] for i in range(n): x = input().split() ary.append((x[0], int(x[1]))) ary.sort(key=setting) for i in ary: print(i[0], end=" ") -교재 풀이 n = int(input()) ary = [] for i in range(n): x = input().split() ary.append((x[0], int(x[1]))) ary = sorted(a..

퀵 정렬 퀵 정렬은 지금까지 배운 정렬 알고리즘 중에서 가장 많이 사용된다. 이 교재에는 없지만 병합 정렬도 퀵 정렬과 같이 빠르다. 퀵 정렬은 기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 기준 숫자인 피벗이 사용된다. 리스트에서 피벗을 정한다. 피벗을 정하고 나면 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 교환한다. 이렇게 있을 때, 5를 피벗으로 정했다. 그러면 왼쪽에선 7이 피벗보다 크고, 오른쪽에선 4가 피벗보다 작다. 따라서 7과 4의 위치를 바꿔준다. 이러다보면 왼쪽 리스트는 모두 피벗보다 작고 오른쪽은 모두 피벗보다 큰 데이터가 위치한다. 이렇게 ..

정렬 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능하다. 정렬 중에서 많이 사용하는 것은 선택, 삽입, 퀵, 계수 정렬 등이 있다. 파이썬에서는 리스트의 원소를 뒤집는 메서드를 제공하고 이 것은 O(N) 복잡도로 간단하게 수행된다. 선택 정렬 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이 선택 정렬이다. 이렇게 데이터가 있으면 처음엔 0이 선택되어 맨 앞의 7과 자리가 바뀌게된다. 그 다음엔 제일 작은 1이 선택되어 5와 자리를 바꾼다. 이런식으로 하다보면 정렬이 가능하다. 이 과정에서 가장 작..

from collections import deque n, m = map(int, input().split()) ary = [] for i in range(n): ary.append(list(map(int, input()))) #상하좌우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): q = deque() q.append((x, y)) while q: x, y = q.popleft() #상하좌우 방문 for i in range(4): nx = x + dx[i] ny = y + dy[i] #범위 벗어나면 continue if nx = n or ny = m: continue #괴물 만나면 continue if ary[nx]..