생각하는 감쟈

이분 탐색 - 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 떄 까지 탐색하는 알고리즘 - 조건 : 반드시 오름차순으로 정렬된 상태에서 시작해야 한다 Olog(N) 반복문과 재귀 두 가지 방법을 사용할 수 있다 target : 찾고자 하는 값 data : 오름차순으로 정렬된 list start : data의 처음값 인덱스 end : data의 마지막 값 인덱스 mid : start, end 의 중간 인덱스 자료의 중갑 값(Mid) 차고자 하는 값인지 겁사 아니라며면 대소 관계를 비교하는 start, end 값 이동 동일 연산 반복 (재귀로 구현 가능) 자료의 중간 값이 찾고자 하는 값인지 비교 mid값이 target과 다트라면 대소관계를 비교하여 탐색 범위를 좁히고, tqrge..

백트래킹 - 해를 찾는 도중 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 방법 - 최적화 문제와 결정 문제를 푸는 방법 - DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 끔 구현가능 백 트래킹 vs DFS 백 트래킹 - 불필요한 탐색을 하지 않음 DFS - 모든 경우의 수를 탐색 빅오 표기법 - 런타임과 메모리 사용을 최소화 방법 O(1) constant time : for문 없이 바로 O(log n) log time : 이중 탐색 O(n) linear time : for문 O(n log n) log linear time : ..

그래프는 노드와 링크로 구성되어 있다. 깊이 우선 탐색(dfs, depth-first search) - 깊은 부분을 우선적으로 탐색하는 알고리즘 - 탐색 할때 특정한 경로를타고 밑바닥까지 내려간 후 막다른 길에 도착하면 다시 돌아와 다른 경로를 탐색 - 스택 자료구조 (FILO) 1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 2. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단함 3. 검색 속도 자체는 너비 우선 탐색에 비해서 느림 너비 우선 탐색 (bfs, breadth-first search) - 최대한 넓게 이동한 다음 ,더 이상 갈 수 없을 때 아래로 이 - 가까운 노드부터 탐색하는 알고리즘 - 큐 자료구조를 이용하여 표현 된다 브루트 포스 브루트 포스는 완전 탐색 알고리즘 - 가능한..

자료구조 (stack, queue, deque) Stack LIFO(Last In First Out) / FILO(First In Last Out) 한 쪽만 뚫여있는 구조 pop() : 스택에서 가장 위에 있는 항목을 제거 push(Item) : Item 하나를 스택의 가장 윗 부분에 추가 peek () : 스택의 가장 위에 있는 항목을 반환 isEmpty() : 스택이 비어 있을 때 true를 반환 IsFul() : 스택이 가능 가 있는지 확인 getSize() : 스택에 있는 요소 수를 변환 사용 용어 : top, bottom, push, pop Queue FIFO(First In First Out) 양쪽이 뚫려있는 구조 - 한쪽은 데이터 삽입 한쪽은 데이터 추출만 진행 enQueue() : 큐에 끝..