데이터 분석 기술 블로그

스택 (선형)LIFO방식으로 작동하는 후입 선출 자료구조push() → 요소 삽입 O(1)pop() → 요소 제거 O(1)peek() → 가장 위의 요소 확인 O(1)재귀 함수 호출 스택, 괄호 검사 등에 활용사용 예제: 웹 뒤로 가기 / 앞으로 가기

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

1. 분할 정복 알고리즘설계 전분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눕니다.정복(Conquer) : 나눈 작은 문제를 각각 해결합니다.통합(Combine) : (필요하다면) 해결된 해답을 모읍니다.2. 퀵 정렬주어진 배열을 두 개로 분할하고, 각각을 정렬합니다.합병정렬과 비슷다른 점 1 : 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것 오른편에 위치시킵니다.다른 점 2 : 각 부분 정렬이 끝난 후, 합병정렬은 "합병"이란 후처리 작업이 필요하나, 퀵정렬은 필요로 하지 않습니다. 퀵정렬의 최악의 시간 복잡도는 O(n2)로, 합병정렬에 비해 좋지 못합니다.그런데, 왜 "빠른" 정렬이라고..

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를 결정하여 방문합니다..