📌 Dynamic Programming(DP) 🤔 원리 가장 대표적인 예로 피보나치 수열을 들어보자면.. 피보나치 수열을 계산할 때 재귀 함수를 사용하게 되면, 매번 f(i-2)와 f(i-1)을 호출해야 하므로, 시간을 엄청 낭비하게 된다. 이렇게 낭비되는 부분을 줄이기 위해서는 배열을 사용하여, f[i] = f[i-2] + f[i-1]와 같이 이미 계산된 이전 인덱스들을 이용한다. DP는 이처럼 배열에 각각 저장된 결과들을 재활용하여 새로운 결과를 만드는 느낌으로 접근한다. A지점까지 가는 경우의 수를 구하는 경우, A지점의 직전 지점까지 가는 경우의 수를 구해서 1을 더하는 느낌이다. 원점 좌표에서 한칸 한칸 이동해보면서 A지점까지 오는 모든 경우를 구하는 것 보다, 각 지점에서 이전 지점까지의 경우..
알고리즘 공부
📌 이진 탐색 🤔 원리 1. 왼쪽 기준값과 오른쪽 기준값을 정한다. 2. 그 두 값의 중간값을 구한다. 3. 찾고자 하는 값의 위치를 파악한다. 3-1. 찾는 값이 중간값보다 왼쪽에 위치하는 경우 : 왼쪽 기준값은 유지, 오른쪽 기준값을 기존 중간값으로 갱신 3-2. 찾는 값이 중간값보다 오른쪽에 위치하는 경우 : 왼쪽 기준값을 기존 중간값으로 갱신, 오른쪽 기준값은 유지 4. 지정한 종료 시점까지 해당 프로세스를 반복한다. 🤔 장점 처음부터 끝까지 탐색하는 브루트포스 알고리즘과 다르게, 탐색 범위를 크게 줄일 수 있다. 🤔 단점 탐색 대상 데이터가 정렬되어 있어야 한다. ⚙️ 이진 탐색 구현 예시 k, n = map(int, input().split()) had = [] for i in range(k)..
📌 Stack & Queue 🤔 파이썬의 Stack 구조 데이터 입력 : append()를 통해 데이터를 맨 뒤에 쌓는다. 데이터 출력 : pop()을 통해 데이터를 맨 뒤에서 뽑아낸다. 👉🏻 후입선출구조! 🤔 파이썬의 Queue 구조 데이터 입력 : append()를 통해 데이터를 맨 뒤에 쌓는다. 데이터 출력 : pop(0)을 통해 데이터를 맨 앞에서 뽑아낸다. 👉🏻 선입선출구조! 😩 한계점 이전 포스팅에서 다뤘듯이 파이썬에서 append나 pop을 사용하는 경우 리스트의 크기에 따라 처리 속도가 비례하게 증가하기 때문에, 코드가 상당히 비효율적으로 작동되는 부분이 생긴다. (ex. 코딩테스트 문제에서 시간 초과로 인한 오답 처리 가능성 높음) 📌 그래프 탐색: DFS 🤔 DFS(Depth First..
📌 개요 알고리즘 문제를 푸는 과정에서, 코드의 간단한 차이가 시간초과 여부를 가르는 현상을 경험했다. 채점 결과, 시간 초과가 발생한 코드 n = int(input()) array = [(i+1) for i in range(n)] while len(array) > 1: array.remove(array[0]) array.append(array[0]) array.remove(array[0]) print(array[0]) 채점 결과, 정답 인정이 된 코드 from collections import deque n = int(input()) array = deque() for i in range(n): array.append(i+1) while len(array) > 1: array.popleft() arra..
📌 개요 알고리즘 문제를 푸는 과정에서 다음과 같은 경험을 하게 되었다. 채점 결과, 시간 초과가 발생한 코드 import sys n = sys.stdin.readline() cards = list(map(int, sys.stdin.readline().split())) m = sys.stdin.readline() find = list(map(int, sys.stdin.readline().split())) for items in find: if items in cards: print("1", end=' ') else: print("0", end=' ') 채점 결과, 정답 인정이 된 코드 import sys n = sys.stdin.readline() cards = set(map(int, sys.stdin...
📌 개요 파이썬으로 알고리즘 공부를 난이도 있게 해보려 하다 보니, 아무리 봐도 더 시간을 절약할 수 없을 것 같음에도 시간 초과 문제가 발생하는 결과가 종종 발생했다. 파이썬은 나중가면 라이브러리 싸움이라는 얘기를 간혹 들어보긴 했었는데, 막상 이렇게 문제에 직면해보니 math나 numpy, scipy같이 익숙한 라이브러리 외에도 다양한 라이브러리를 알고 있는 것이 도움이 될 것 같아 관련 글들을 작성해보기로 했다. 📌 sys 라이브러리 import sys sys 라이브러리는 기본적으로 설치되어 있어서 별도로 설치할 필요는 없었다. python docs에 설명된 내용으로는, 이 라이브러리는 인터프리터에서 사용하는 변수나 함수를 제어할 수 있다고 한다. sys 라이브러리에서 제공하는 다양한 함수 중, s..
