개발자 취업의 수문장 코딩테스트 통과하기

190906 이민예

발표자 : 김경록 (뷰티풀프로그래밍 백엔드 개발자)

spring boot / python / node.js / aws / 작가 / 유튜버 (크롤링) / 건물주 - 강남역 원룸

문제는 알고리즘을 구현하는 문제임.

다이내믹 프로그래밍을 알아야 풀수 있는 문제 : 이전에 연산 했던 값을 기록해 놓고, 다음 연산 할 때 참고하여 연산 횟수를 줄이는 방법

[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] : 그리드를 그릴수 없다. 4*4 행렬을 이렇게 초기화 해놓고 시작한다.

앞에 2개만 알면, 현재 값을 구할 수 있다. 재귀를 사용하여 구할 수 있다.

def fib(n): if n <= 1: return n return fib(n-1)+fib(n-2) -> 하지만 많이 느리다.

따라서, 메모 하는 방법으로 구한다. 따라서 전수조사를 해야하는 프로그래밍 문제가 나오면, 다이내믹 프로그래밍으로 어떻게 풀어야 하나 고민해야한다.

seq1= ABCDCBA / seq2 = DCABDC

주어진 두 문장에서 겹치는 문자중 가장 긴 문자의 길이 (subsequence : 순서는 같되, 띄어써도 됨.)

전수조사를 한다. 1글자인 것, 2글자인것, 3글자인것, 4글자인것, 5글자인것, 6글자인것 / 하지만 글자가 많아질수록 시간이 많이 증가한다. 1000개의 글자와 800개의 글자를 비교하는 경우 등, 로컬에서 수정한 내역과 깃에서 받은 내역을 비교하는 경우
다이내믹프로그래밍 기법을 쓴다 :

Last updated 4 years ago