본문 바로가기

알고리즘36

[Algorithm] 카데인 알고리즘 (Kadane's Algorithm) 카데인 알고리즘 (Kadane's Algorithm) 카데인 알고리즘은 DP (Dynamic Programing)의 기법중 하나인데 DP를 간단하게 설명하자면 다음과 같다. Dynamic Programing : 하나의 큰 문제를 풀기위해 그 문제를 작은 문제들로 나눠 풀어나간 후, 결국 하나의 큰 문제를 풀어내는 방법이다. 카데인 알고리즘은 최대 부분합 문제를 풀때 주로 사용된다. 최대 부분합 문제 Arr = [-2,1,-3,4,-1,2,1,-5,4]; 다음과 같은 배열이 주어질 때 위의 순서를 유지하고, 연속적이면서 가장 큰 합을 가지는 부분배열은 다음과 같다. [4, -1, 2, 1] -> 합 : 6 Arr[4] = -1 를 마지막 원소로 갖는 부분 합과, Arr[5] = 2를 마지막 원소로 갖는 부.. 2023. 3. 20.
[Algorithm] 완전 탐색과 종류 (Brute Force Search) 완전 탐색, Brute Force Search 란? 완전 탐색과 브루트 포스의 이름에서 유추할 수 있듯이 이 알고리즘의 방법은 발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법이다. 이 알고리즘의 대표적인 장점은 모두 확인하기 때문에 100%의 확률로 정답만을 출력한다는 것이다. 하지만 확실하게 확인하는 만큼 시간이 오래 걸리는 탐색기법이다. 💡 Brute : 무식한, 짐승 같은 + Force : 힘 - 무식하게 풀기 완전 탐색의 종류 구조로 나누어보면 선형 구조를 전체적으로 탐색하는 방법인 순차 탐색과 비선형 구조를 전체적으로 탐색하는 방법인 DFS / BFS가 대표적인 탐색 방법이다. 1. 브루트 포스 (Brute Force) 브루트 포스는 반복문과 조건문을 사용하여 가능.. 2023. 3. 20.
[Algorithm] Tail Recursion (꼬리 재귀) 재귀 함수 재귀 함수는 '기저 사례(base case)'와 '재귀적 관계(recurrence relation)'만 알면 정말 간단하게 구현할 수 있다. 그리고 보통 코드가 짧아서 가독성도 좋다. 쪼개지지 않는 가장 작업들을 가리켜 재귀 호출의 기저 사례(base case) 자기 자신과 관계를 맺는 형식을 재귀적 관계(recurrence relation) 하지만 장점이 있으면 단점도 있는 법이다. 재귀 호출을 할 때마다 콜 스택에 새로운 프레임이 쌓이고, 각 프레임은 지역 변수나 인수를 저장하기 위해 메모리를 사용한다. 이게 보통은 문제가 되지 않지만, 만약 각 프레임에서 기가바이트 단위의 데이터를 받아 처리해야 하는 경우에는 문제가 심각해질 수도 있다. 혹은 콜 스택이 너무 깊어지면 스택 공간이 가득차 .. 2023. 3. 19.
[Algorithm] Disjoint Set의 표현: Union-Find (합집합 찾기) Disjoint Set (서로소 집합) 'Disjoint set'는 공통 원소가 없는 부분 집합들이다. 어떤 교양 대면 수업에 여러 학과 사람들이 모여있다고 해보자. 이때 교수님이 갑자기 같은 과 사람들끼리 조를 만들라고 한다. 그럼 학생들은 이리 저리 돌아다니다가 같은 과 사람을 찾으면 팀을 이뤄 같이 움직이게 될 것이다. 그리고 팀끼리도 같은 과인 것을 확인하면 두 팀은 합쳐진다. 만들어진 조들은 공통 원소가 없는 부분 집합들, disjoint set이 된다. 이 상황을 자료구조로 표현한 것이, 즉, disjoint set에 대한 정보를 저장하고 조작하는 자료 구조가 'Union-Find'다. Union-Find 알고리즘 (합집합 찾기) 대표적인 그래프 알고리즘으로 합집합 찾기라고도 불리며, 서로소 .. 2023. 3. 17.
[Algorithm] DFS (깊이 우선 탐색. Depth-first search) 그래프와 완전탐색 자료구조에서 말하는 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계가 있는 경우 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 정점(vertex)라고 표현하고 하나의 선은 간선(edge)라고 표현한다. 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이고 이를 완전탐색이라 부르기도 한다. 모든 정점 탐색 방법에는 여러 가지가 있다. 그 중 DFS가 있다. 위 그림과 같은 그래프가 있다고 가정하겠다. 이 그래프를 어떤 방법으로 완전 탐색하냐에 따라 방문하는 순서가 달라진다. DFS(Depth-First Search) 깊이 우선 탐색 루트.. 2023. 3. 13.
[Algorithm] 완전 탐색 - 백트래킹(Backtracking), 깊이 우선 탐색(DFS. Depth-first search) 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가, 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다. - 나무 위키 - 백트래킹(Backtracking) 비선형으로 구성된 자료 구조를 깊이.. 2023. 3. 13.
[Algorithm] BFS (너비 우선 탐색. Breadth-first search) 그래프와 완전탐색 자료구조에서 말하는 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계가 있는 경우 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 정점(vertex)라고 표현하고 하나의 선은 간선(edge)라고 표현한다. 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이고 이를 완전탐색이라 부르기도 한다. 모든 정점 탐색 방법에는 여러 가지가 있다. 그 중 BFS가 있다. 위 그림과 같은 그래프가 있다고 가정하겠다. 이 그래프를 어떤 방법으로 완전 탐색하냐에 따라 방문하는 순서가 달라진다. BFS(Breadth-First Search) 너비 우선 탐색 .. 2023. 3. 13.
[Algorithm] 완전 탐색 - 브루트 포스(brute force), 너비 우선 탐색(BFS. Breadth-first search) 브루트 포스(brute force) brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth.. 2023. 3. 13.
[Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘(Greedy Algorithm) Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알.. 2023. 3. 13.
[Algorithm] 비트마스크 (BitMask) 비트(Bit)란? 컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1) 2진법을 생각하면 편하다. 우리가 흔히 사용하는 10진수를 2진수로 바꾸면? 9(10진수) → 1001(2진수) 비트마스크 (BitMask) 정수의 이진수 표현으로 자료를 표현하는 기법을 '비트마스크'라고 부른다. 예를 들어 그래프에 정점 0, 1, 2, 3 있다고 해보자. 이 그래프를 탐색할 때 DFS로 순회하든, BFS로 순회하든 보통 visited 배열을 둬서 방문한 노드인지 아닌지 확인한다. 정점 0을 방문했다면 배열 [1, 0, 0, 0]로 표현할 수 있다. 이때 배열 대신 비트마스크를 사용할 수도 있다. 비트마스크를 사용하면 정점 0을 방문한 것을 0001로 표현할 수 있다. 2와 3을 추가적으로 방문하게 된다면 1101로 .. 2023. 3. 13.

티스토리툴바