공부 자료/자료구조|알고리즘 (6) 썸네일형 리스트형 [자료구조/알고리즘] 깊이 우선 탐색 DFS / 너비 우선 탐색 BFS [DFS] 깊이 우선 탐색(DFS, Depth First Search) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 : 하나의 경로를 끝까지 탐색한 후 다음 경로로 넘어가 탬색을 진행 : BFS보다 탐색 시간은 오래걸리지만 모든 노드를 완전히 탐색 가능함 >> 모든 노드를 방문해야 하는 경우 사용 : BFS보다 좀 더 간단히 사용 가능함 >> 스택 또는 재귀함수로 구현함 [BFS] 너비 우선 탐색(BFS, Breathed First Search) : 그래프에서 가까운 노드를 우선적으로 탐색하는 알고리즘 : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 : 너비를 우선적으로 탐색하는 방법으로 정점 사이의 최단 경로를 찾을 때 사용 >> 최악의 경우 모든 정점을 다 살펴야 함 >.. [자료구조/알고리즘] 완전 탐색 / 이진 탐색 알고리즘 [완전 탐색 알고리즘] Brute-Force : 시행착오 방법론으로 모든 값을 대입하는 방법 완전 탐색 알고리즘(Brute-Froce Algorithm) : 무차별 대입 방법으로, 모든 가능성을 시도하여 문제를 해결하는 방법 * 공간/시간 복잡도를 고려하지 않기 때문에 Greey Algorithm이 아님 [사용 경우] (문제의 더 적절한 해결법을 찾기 전 사용함) 1) 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없는 경우 2) 문제를 해겨하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 경우 [사용 예시] 1) 순차 검색 알고리즘(Sequential Search) Ex. 배열 내 특정값 존재 여부 확인(처음부터 차례대로 검색) 2) 문열 매칭 알고리즘(Brute-Force Matching).. [자료구조/알고리즘] 탐욕 알고리즘 Greedy [탐욕 알고리즘이란?] Greedy : 탐욕스러운, 욕심 많은 Greedy Algorithm : 매 순간 최적이라고 생각하는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식 [해결 방법] 1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택 2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사 3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 과정을 반복함 [특정한 상황] - 최적의 해를 보장받기 위한 조건 1. 탐욕적 선택 속성(.. [자료구조/알고리즘] 시간복잡도 복잡도(complexity) : 알고리즘의 성능을 객관적으로 평가하는 기준 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것으로, Big-O 표기법을 이용 * 공간 복잡도 고려는 최근들어 중요성이 줄어듦 Big-O 표기법 : 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가를 고려함 1) Big-O : 최악의 경우를 고려 >> 항상 최악의 경우를 대비 2) Big-Ω : 최선의 경우를 고려 3) Big-θ : 중간의 경우를 고려 1. O(1) (constant complexity) : 입력값이 증가하더라도 시간이 늘어나지 않음 : 가장 빠른 시간 복잡도 Ex. 배열 중 인덱스 하나 리턴 (배열이 증가하더라도 리턴값이 1개이기에 복잡도가 늘어나지.. [알고리즘/자료구조] 자료구조 자료구조 : 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것 : 데이터 (문자,소리,그림,영상 등 실생활을 구성하는 모든 값으로 이를 필요에 따라 데이터의 특성을 파악하여 정리해 저장해 놓는 것이 활용에 유리함) [Stack] 스택(Stack) : 쌓다, 포개지다의 뜻으로 데이터가 쌓이는 순서대로 쌓는 자료구조 구조 : 입력과 출력이 하나의 방향으로 이루어진 제한적 접근 : LIFO(Last In First Out) 구조 특징 : 데이터는 하나씩 넣고 뺄 수 있음 : 하나의 입출력 방향을 가짐 : 먼저 들어간 데이터는 가장 나중에 나오는 후입선출 구조 [용어] 스택용 배열 stk 스택 용량 capacity ptr : 스택 포인터 IntStack : 생성자 push(int x) : 데이터를 푸쉬하.. [자료구조/알고리즘] 재귀 재귀함수 재귀 : 원래의 자리로 되돌아가거나 되돌아옴 재귀함수 : 자기 자신을 호출하는 함수 사용 조건 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 함 호출 종료 시점이 존재해야 함 (존재하지 않을 경우 무한 루프에 빠질 수 있음) 장점 여러개의 반복문을 사용하지 않아 코드가 간결해지고 수정이 용이 변수를 여러개 사용할 필요가 없음 단점 코드의 흐름을 직관적으로 파악하기 어려움 (특히, 반복이 많을수록 결과 예측이 어려워짐) 메서드를 반복 호출하며 매개변수/지역변수/변환값을 모두 저장하기 때문에 더 많은 메모리를 사용 메서드 호출 및 종료 후 복귀를 위한 컨테스트 스위칭 비용이 발생함 분석 방법 1) 상향식 분석(bottom-up analysis) : 0에서부터 시작하여 올려나감 : 아래쪽부터 쌓아 .. 이전 1 다음
