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..

문제 설명 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.) 예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면 A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5) A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21..

문제 설명 String형 배열 seoul의 element중 Kim의 위치 x를 찾아, 김서방은 x에 있다는 String을 반환하는 함수, solution을 완성하세요. seoul에 Kim은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다. 제한 조건 seoul은 길이 1 이상, 1000 이하인 배열입니다. seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다. Kim은 반드시 seoul 안에 포함되어 있습니다. 입출력 예 seoul return ["Jane","Kim"] "김서방은 1에 있다" Solution index( ) : S.index(sub[, start[, end]]) -> int >>> a = "abcdefghiz" >>> a.index('z') 9 >>> a = [ 10..

문제 설명 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 (최소값) (최대값)형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 1 2 3 4라면 1 4를 리턴하고, -1 -2 -3 -4라면 -4 -1을 리턴하면 됩니다. 제한 조건 s에는 둘 이상의 정수가 공백으로 구분되어 있습니다. 입출력 예 S return "1 2 3 4" "1 4" "-1 -2 -3 -4" "-4 -1" "-1 -1" "-1 -1" Solution 1. map( ) : map(func, *iterables) --> map object >>> list( map( lambda a : a*10 , [1, 2, 3, 4] ) ) [10, 20, ..