Warm Developer

동적 프로그래밍이란? 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어 정답을 찾은 뒤, 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정을 말한다. 메모이제이션이란? 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이며 동적 계획법의 핵심이 되는 기술이다. Example # 피보나치 수열(Bottom up) def fib(n): fiblist = [ 1, 1 ] for i in range(2, n+1): fiblist.append(fiblist[i-2] + fiblist[i-1] return fiblist[-1] # 마지막 값 반환 # 피보나치 수열(Top down) def fi..

재귀함수란? 메소드 혹은 함수의 내부에서 자기 자신을 다시 호출하는 함수이다. 재귀함수를 통해 코드를 보다 간결하게 작성할 수 있으며 변수 사용을 최소화할 수 있다. 모든 재귀함수는 반복문을 통해 동일한 기능을 구현할 수 있다. 함수를 연속적으로 호출할 경우 메모리 내부 스택 프레임에 쌓이며 대표적으로 DFS를 간결하게 작성할 수 있다. def recur_fun(cnt): print('{}번째 재귀함수 호출'.format(cnt)) if cnt 더보기 1번째 재귀함수 호출 2번째 재귀함수 호출 3번째 재귀함수 호출 4번째 재귀함수 호출 5번째 재귀함수 호출 6번째 재귀함수 호출 문제 ) 주어진 data 리스트 요소들의 합으로 표현할 수 있는 숫자의 경우의 수는? 1. 반복문을 통한 완전 탐색 data =..

1. DFS ( Depth First Search ) _ 깊이 우선 탐색이란? 하나의 경우의 수에 대하여 모든 경우의 수를 조사하면서 해를 찾는 과정으로 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택(후입선출)의 자료구조 또는 재귀함수를 활용한다. 위 그래프의 경우 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5 순서대로 탐색하며 코드로 구현하면 다음과 같다. def dfs(graph, v, visited): visited[v] = True # 현재 노드를 방문 처리 print(v, end=' ') for i in graph[v]: # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 if not visited[i]: dfs(graph, i, visited) graph = [ [ ]..

탐색이란? 많은 데이터 속에서 원하는 데이터를 찾는 것 탐색의 종류 완전탐색 이분탐색 깊이우선 탐색 너비우선 탐색 문자열 탐색 KMP BM 1. 완전탐색 - 브루트 포스라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색, 효율성 관점에서 최악의 방법 1-1. 반복문 def solution(trump): for i in range(len(trump)): if trump[i] == 8 : return i return -1 1-2. 재귀함수(동적계획법, 백트래킹, 탐욕법) - 무한루프에 빠질 수 있음에 주의! def solution(trump, loc): if trump[loc] == 8 : return loc else : return solution(trump, loc+1) 2...

스택(Stack)이란? 쌓다 라는 의미를 가지며 LIFO(Last In First Out) 후입선출 구조를 가진다. 삽입 : push 삭제 : pop Python Stack 직접 구현 >>> s = [ ] >>> s.append(1) >>> s.append(5) >>> s.append(10) >>> print("my stack : ", s) my stack : [ 1, 5, 10 ] >>> print(s.pop()) 10 >>> print("my stack : ", s) my stack : [ 1, 5 ] >>> print(s[-1]) 5 >>> print("my stack : ", s) my stack : [ 1, 5 ] list.pop( ) : 리스트의 마지막 인덱스 값을 리턴 후 삭제 list[-1..