데이터 분석 기술 블로그

1. 부분 집합의 합2. 순열

1. 백트래킹백트래킹 (Backtracking) 기법은 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법입니다.백트래킹 기법은 최적화 (optimization) 문제와 결정 (decision) 문제를 해결할 수 있습니다.결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제입니다.미로 찾기n-Queen 문제Map coloring부분 집합의 합(Subset Sum) 문제 등백트래킹과 깊이 우선탐색과의 차이어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄입니다. (Prunning 가지치기)깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를..

지난 시간에 했던 스택 - 계산기 1 (2024.06.01 - [알고리즘] - 스택 -계산기 1)의 연장선입니다.1. step2. 후위 표기법의 수식을 스택을 이용하여 계산피연산자를 만나면 스택에 push 합니다.연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop 하여 연산하고, 연산결과를 다시 스택에 psuh 합니다.수식이 끝나면, 마지막으로 스택을 pop하여 출력합니다.

1. 계산기 1문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계식의 값을 계산할 수 있습니다.문자열 수식 계산의 일반적 방법step1. 중위 표기법의 수식을 후위 표기법으로 변경합니다. (스택 이용)step2. 후위 표기법의 수식을 스택을 이용하여 계산합니다.2. step1. 중위표기식의 후위표기식 변환 방법 1수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현합니다.각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킵니다.괄호를 제거합니다.3. step1. 중위 표기법에서 후위 표기법으로의 변환 알고리즘(스택 이용) 2입력받은 중위 표기식에서 토큰을 읽습니다.토큰이 피연산자이면 토큰을 출력합니다.토큰이 연산자(괄호 포함) 일 때, 이 토큰이 스택의 top에 저장되어 있는 연산..

1. DFS(깊이우선탐색)비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요합니다.두 가지 방법으로는 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)이 있습니다.시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법입니다.가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용합니다.2. DFS 알고리즘 순서1) 시작 정점 v를 결정하여 방문합니다..

1. DP(Dynamic Programming)동적 계획 (Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘입니다.동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘입니다. 2. 피보나치 수 DP 적용피보나치 수는 부분 문제의 답으로부터본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있습니다.1) 문제를 부분 문제로 분할합다.Fibonacci(n) 함수는 Fibonacci(n-1)과 Fibonacci(n-2)의 합Fibonacci(n-1)은 Fibonacci(n-2)와 Fibonacci(n-3)의 합..

1. 재귀호출의 문제점이전의 설명한 재귀호출 (2024.05.26 - [백엔드] - 재귀호출)의 문제점은 엄청난 중복 호출이 존재합니다.2. Memoization메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술입니다. 동적 계획법의 핵심이 되는 기술입니다.'memoization'은 글자 그대로 해석하면 '메모리에 넣기(to put in memory)'라는 의미이며 ' 기억되어야 할 것'이라는 뜻의 라틴어 memorandum에서 파생되었다. 흔히 '기억하기', '암기하기'라는 뜻의 memorization과 혼동하지만, 정확한 단어는 memoization이다. 동사형은 memoize이다..

1. 재귀호출자기 자신을 호출하여 순환 수행되는 것입니다.함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있습니다.재귀 호출의 예) factorialn에 대한 factorial : 1부터 n까지의 모든 자연수를 곱하여 구하는 연산입니다마지막에 구한 하위 값을 이용하여 상위값을 구하는 작업을 반복합니다.0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라고 합니다.0, 1, 1, 2, 3, 5, 8, 13피보나치수열의 i번 째 값을 계산하는 함수 F를 정의하면 다음과 같습니다.F0 = 0, F1 = 1Fi = Fi-1 + Fi-2 for i ≥ 2위의 정의로부터 피보나치 수열의 i번째 항..