본문 바로가기

🔎 Algorithm/📝 개념 정리5

[개념 정리] 투 포인터 최근 알고리즘을 풀면서 시간 초과와 예외처리로 인해 상당히 애를 먹었던 문제가 있다. 해당 문제의 다른 풀이를 찾아보니 투 포인터 알고리즘을 통해 간단하게 구현할 수 있다는 점을 알았고 이에 대해 정리해보고자 한다. 투 포인터 알고리즘은 하나의 배열에서 두 개의 인덱스 포인터를 조작하는 알고리즘을 의미한다. 문제를 예시로 들어서 설명하면 다음과 같다. 백준 - 2467. 용액 이 문제에서 0과 가장 가까운 거리의 합을 가지는 두 원소를 구하는 방법은 먼저 O(N^2)의 시간복잡도를 가지는 방법이 존재한다. 하지만 문제처럼 N의 크기가 O(N^2)으로 해결할 수 없는 경우에 투 포인터 알고리즘을 사용하면 O(N)에 해당 값을 구할 수 있다. (이 문제는 정렬이 필요하기 때문에 전체 문제의 시간복잡도는 O(.. 2021. 4. 1.

[개념 정리] 최단 거리 알고리즘 - 다익스트라 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 - 플로이드-와샬 저번 글에서는 4번 유형을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보았습니다. 이번 글에서는 2번 유형을 해결할 수 있는 다익스트라 알고리즘에 대해서 알아보겠습니다. 다익스트라 알고리즘은 간단하게 설명하면 시작 정점에서 거리가 최소인 정점을 선택해 .. 2021. 3. 22.

[개념 정리] 최단거리 알고리즘 - 플로이드 와샬 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 이 중 4번을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보고자 합니다. 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 모든 정점간의 최단경로를 구하는 알고리즘입니다. 앞으로의 설명에서 사용될 그래프는 다음과 같은 가중치를 가지고 있습니다. 초기 가중치 값을 저장하는 .. 2021. 3. 16.

[개념정리] 스위핑 알고리즘 스위핑 알고리즘이란 특정 기준에 따라 정렬된 순서대로 문제를 처리하는 방법이다. 스위핑 알고리즘을 사용해야하는 문제들의 특징은 러프한 방법 (일반적으로 O(N^2)의 시간복잡도를 갖는 방법)으로는 해결이 불가능하며, DP를 사용하기에는 메모이제이션 해야할 수가 너무 많은 경우가 일반적이다. 스위핑 알고리즘으로 문제를 풀 경우, 해당 시간 복잡도는 정렬에서 발생하는 O(NlogN)안에서 해결된다. 백준 - 8982. 사냥꾼 일반적인 방법으로 풀게되면 O(N*M)의 시간복잡도를 가지게 되고 시간초과가 발생한다. 그렇다고 좌표에 대한 정보를 기억할 수도 없기 때문에 스위핑 알고리즘을 통해 해결해야 한다. 먼저, 사대와 동물을 모두 x축 순서로 정렬하고 동물을 기준으로 사냥이 가능한지 확인한다. 확인 과정은 동.. 2021. 2. 26.

[개념 정리] 순열, 조합, 부분집합 이번 글에서는 모든 경우의 수를 탐색하는 완전탐색 기법에서 순열과 조합 그리고 부분집합에 대한 구현 방법을 정리해보고자 합니다. 순열 순열은 N개의 원소 중에서 R개의 원소를 통해 순서를 가진 부분집합을 만드는 경우의 수입니다. 순열은 재귀 함수를 통해 모든 경우의 수를 구할 수 있습니다. 재귀함수를 사용하게 되면 이번 순서의 원소를 사용하는지 체크하는 과정이 필요한데, 이 과정은 boolean 배열을 통해 체크하거나 비트 마스킹을 통해 구현할 수 있습니다. Boolean 배열 사용 permutationByBoolean(0); static void permutationByBoolean(int cnt) { if (cnt == N) { printPermutation(); return; } for (int i.. 2021. 2. 19.

이전 1 다음

티스토리툴바