본문 바로가기

🔎 Algorithm21

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

[백준] 1799. 비숍 문제 풀이 처음에 생각했던 방법은 완전 탐색을 통해 최대 수를 찾는 방법이었다. 중간에 가지치기를 통해 시간을 줄일 수 있겠지만 n의 최대값이 100이고 (모든 점에 대해 놓는 경우/ 놓지 않는 경우) * (놓을 수 있는지 판단하기 위해 양 대각선을 탐색하는 경우)를 하게 되면 O(2^n * n)이기 때문에 시간초과가 발생할 것 같아서 다른 방법을 생각해봤다. 생각한 방법은 N-Queens에서 모든 행렬을 저장하지 않고 해당 idx에는 하나의 값만 올 수 있도록 한다면 시간을 줄일 수 있다는 생각을 했고 데이터를 어떻게 묶어야 할지 고민을 해봤다. N-Queens에서 queen은 가로,세로를 갈 수 있었고 이로 인해 하나의 행에 퀸을 놓을 경우에는 같은 행에는 퀀이 존재하지 못하는 성질을 이용했었다. 이.. 2021. 3. 7.

[백준] 1967. 트리의 지름 문제 풀이 처음 시도했던 방법은 1번의 자식노드들을 시작점으로 잡아 DFS를 통해 탐색하면서 왼쪽 자식과의 거리, 오른쪽 자식과의 거리, 부모와의 거리 중에 상위 2개의 값을 골라 최대값을 갱신하는 방법으로 진행하였다. 그리고 그 최대값이 1번의 다른 줄기와 연결할 수 있는지(notCompleted), 아니면 이미 완성된 지름인지(completed) 판별하는 flag를 통해 최대 지름을 구하려고 했다. 이 방법이 잘못된 이유는 먼저 문제에서 이진 트리라는 조건이 없는데 이진트리라고 가정하고 풀었기 때문이고, 또한 위의 그래프에서 4-7 : 100 / 4-8 : 100으로 수정한 경우 왼쪽 줄기의 최대값이 200이 나와야하는데 4의 부모노드인 2가 자식이 하나밖에 없기 때문에 200 + 5로 갱신되는 문제.. 2021. 3. 6.

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

[백준] 1987. 알파벳 풀이 모든 경우의 수를 DFS로 탐색하며 이전에 방문한 알파벳인 경우 가지치기를 진행하엿다. 이 때 이전 방문 노드를 확인하는 방법으로 초기에는 ArrayList를 사용했지만 시간초과가 발생하였고 이에 대한 이유가 ArrayList의 remove 과정에서 O(N)의 시간복잡도가 발생했기 때문이라고 판단하였다. 그래서 이전 방문 알파벳을 유지하는 방식을 StringBuilder를 사용하였고 마지막 인덱스를 삭제함으로써 시간 초과를 해결하였다. 하지만 이 방법도 너무 느려서 이를 확인하는 방법으로 비트마스킹을 사용하였고 모든 경우에 distance를 비교하는 것이 아니라 유망하지 않은 경우에만 distance를 비교하도록 개선하였다. 비트마스킹으로는 현재 알파벳 - 'A'를 해줌으로써 포함 여부를 확인하였다.. 2021. 2. 19.

[백준] 3109. 빵집 풀이 DFS를 통해 탐색을 진행할 때 최대값을 찾는 경우는 대부분 모든 경우의 수를 확인해야 하기 때문에 유망하지 않은 경우 가지치기하는 백트래킹 방법을 사용할 수 없다. 하지만 이 문제는 시작 점은 가장 위에서부터 연결할 수 있는 경우에는 연결하는 경우가 최선의 방법이 되는 그리디한 접근 방식을 사용하였고 이를 통해 유망하지 않은 경우 탐색을 종료하는 경우 되돌아가는 백트래킹 방식을 사용하였다. 첫번쨰 열의 1번쨰 행부터 탐색을 진행하고, 만약 C번째 행에 도착했다면 이번 시작 위치에서의 탐색을 종료한다. 다음 위치도 동일하게 진행하는데 만약 실패한다고 하더라도 방문한 위치에 대한 체크를 되돌리지 않는다. 왜냐하면 해당 위치에서 파이프를 완성하지 못했다고 하더라도 뒤 선택지에서 해당 방향은 동일하게 실.. 2021. 2. 19.

이전 1 2 3 4 다음

티스토리툴바