전체 글200 [Algorithm] 다익스트라(Dijkstra) 다익스트라 알고리즘이란? 다이나믹 프로그래밍(DP,Dynamic Programming)을 활용한 대표적인 최단 경로 탐색 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 다익스트라의 구현 해당 정점까지의 최단 거리를 저장 정점을 방문했는 지 저장 2024. 1. 5. [Algorithm] BFS(Breadth-first search,너비 우선 탐색) BFS란? 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 두 노드사이의 최단경로를 탐색할때 활용하기 좋은 방식이다. 주로 queue을 사용하여 구현한다. BFS의 특징 해당 노드 주변을 먼저 탐색 두 노드 사이의 최단거리를 찾을 때 BFS 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함 큐를 이용한 BFS 동작과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 위의 과정대로 진행하면 1 2 3 8 7 4 5 6 순으로 노드를 탐색하게 된다. 일반적인 경우 실제 수행 시간은 .. 2024. 1. 5. [Algorithm] DFS(Depth-First Search,깊이 우선 탐색) DFS란? 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 가중치가 주어지거나 특정 경로를 찾아야 할 때 DFS 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 스택을 이용한 DFS 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 .. 2024. 1. 5. [Algorithm] Greedy(그리디) 그리디란? 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 시간적으로 매우 효율적이지만 모든 순간 답이 되는 방법은 아니다. 그리디의 특징 순간의 최적해가 전체 문제의 최적해가 되어야 한다. 입력 범위가 큰 경우가 많고 문제에서 요구하는 답에 '최소', '최대'란 말이 주로 들어간다. 그리디의 성립조건 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 문제 해결 아이디어 : 두 수에 대한 연산을 수행할 때, 두 수 중에서 하나라도 .. 2024. 1. 5. [Algorithm] DP(Dynamic Programming, 동적 계획법) 동적 계획법(DP)란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 특정 범위까지의 값을 구하기 위해 이전 범위의 값을 활용하여 효율적으로 값을 얻는 기법이다. 이전 범위의 값을 저장(Memoization)함으로써 시간적, 공간적 효율 얻는다. 동적 계획법(DP)의 적용주어진 문제를 부분 문제로 나누었을 때, 부분 문제의 답을 통해 주어진 문제의 답을 도출할 수 있을 때부분 문제의 답을 여러 번 구해야 할 때즉, 한 번 계산한 값을 다시 사용해야 할 때Memorization이전에 구해둔 값을 저장해서 중복 계산을 방지이전 범위의 답을 구하면, 바로 배열에 저장해 놓자!시간과 공간면에서 모두 효율적!방법탑다운(하향식) 방식 : 큰 문제를 해결하기 위해 작은 문제 호출보텀업(상향식) .. 2024. 1. 5. [Algorithm] Backtracking(백트래킹) 백트래킹이란? 완전탐색처럼 모든 경우를 탐색하나, 중간 과정에서 조건에 맞지 않는 케이스를 가지치기하여 탐색 시간을 줄이는 기법이다. 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 백트래킹의 특징 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다. 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에 재귀를 사용하는 경우가 많다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 가지치기란? 지금의 경로가 해가 될 것 같지 않으면 그 전으로 돌아가는 것이다. 불필요한 부분을 쳐내는 것으로 되돌아간 후 다시 다른 경로를 검사한다. 백트래킹의 적용 N의 크기가 작을 때 보통 20 이하 (주로 재귀함수로 구현하기 때문) .. 2024. 1. 5. [Algorithm] Brute Force(브루트 포스) 브루트 포스란? 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 완전 탐색이라고도 한다. 예를 들어, 4자리 비밀번호 자물쇠가 있을 때 0000~9999까지 모든 수를 대입해서 푸는 것을 말한다. 브루트 포스의 특징 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%를 보장한다. 거의 완벽하게 병렬 작업이 가능하다. 문제의 복잡도에 매우 민감하여 조금만 복잡해져도 매우 비효율적이다. 브루트 포스의 종류 선형 구조 : 순차 탐색 비선형 구조 : 백트래킹, BFS, DFS 브루트 포스 구현 방법 for/while loop 사용 순열 재귀 2024. 1. 5. [Algorithm] Stack(스택) 스택이란? 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)이다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 즉, 나중에 넣은 값이 먼저 나오게 되는 것이다. 스택의 연산 (std::stack) push(element): top에 원소 추가 pop(): top에 있는 원소 삭제 top(): top에 있는 원소 반환 empty(): 스택이 비어 있을 때 true(1) 반환 size(): 스택 사이즈 반환 2024. 1. 5. [Algorithm] Sort(정렬) 정렬이란? 정렬은 어떤 데이터셋이 주어졌을 때 이를 정해진 순서대로 나열하여 재배치하는 문제이다. 종류가 많으며 그리디 문제에 쓰이는 경우가 많다. 정렬의 종류 O(n²) : Insertion sort, Selection sort, Bubble sort O(nlogn) : Quick sort, Merge sort, Heap sort 버블정렬(Bubble sort) 인접한 두 원소를 비교 왼쪽 원소>오른쪽 원소라면 swap 가장 큰 원소부터 오른쪽에 정렬됨 데이터가 하나씩 정렬되면서 비교 대상에서 제외 합병정렬(Merge sort) 분할 정복 방식으로 설계된 알고리즘 하나의 배열을 정확히 반으로 나눔 나뉜 배열들을 정렬 다시 하나의 배열로 합치기 2024. 1. 5. 이전 1 ··· 8 9 10 11 12 13 14 ··· 23 다음