MJmemento

플로이드 와샬 알고리즘이란? 양 또는 음의 에지 가중치를 갖는 방향 가중 그래프에서 각각의 정점에서 정점까지의 모든 최단 경로를 찾는 알고리즘이다. 다시, 이전의 다익스트라와 벨만포드의 경우 두 정점간의 최소 거리를 계산했다면 플로이드와샬 알고리즘은 모든 정점간의 최소 거리를 알아내는 알고리즘이다. 다른 알고리즘들과 달리 구현이 매우 쉽다. 3중 for 문을 사용하며 O(V^3)의 시간 복잡도를 갖고 있다. 그럼 작동방식은 어떠할까? 아래 그림을 잠깐 보도록 하자 인접행렬로 행과열의 값 arr[a][b] 는 a에서 b로 가는 비용이다. 일단 주어진 가중치를 인접행렬에 갱신해준다. 그렇다면 이젠 가정이 필요하다. a에서 c까지 가는 경로가 있다고 보자, 그런데 a->b->c로 가는 경로가 더 싸다면?? a..

벨만 포드 알고리즘이란? 단일 소스 꼭짓점에서 다른 모든 꼭짓점까지의 최단 경로를 계산하는 알고리즘이다. 다익스트라와 같은 문제에 대한 알고리즘보다는 느리지만, 가중치 중 일부가 음수인 그래프를 처리할 수 있기 때문에 더 다용도적이다 이 알고리즘은 알폰소 심벨(1955)이 처음 제안했지만, 대신 1958년과 1956년에 각각 발표한 리처드 벨먼과 레스터 포드 주니어의 이름을 따서 명명되었다.[2] 에드워드 F 무어는 1959년에 이 알고리즘의 변형을 발표했으며, 이러한 이유로 벨먼-포드-무어 알고리즘이라고도 불린다. 다시, 이전에 설명한 다익스트라 알고리즘과 (모든 꼭짓점까지의 최단경로를 구하기에)비슷 하지만 차이점으로는 가중치(비용)이 음수가 가능하다. 여기서 의문이 생길 수 있다. " 가중치가 음수가..

다익스트라란? 컴퓨터 과학자 에드거 데이크스트라에 의해 만들어진 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다. 즉, 다익스트라 알고리즘은 주어진 그래프에서 시작점으로부터 원하는 노드로 가기에 가장 적은 비용을 갖고 도착하는 경우를 찾는다. (최단거리,최소비용) 위에서 말한 알고리즘을 적용하는 그래프는 방향이 주어지거나 안주어진 그래프의 경우로, 둘다 사용할 수 있지만 가장 많이 사용되는건 방향을 가진 그래프안에서 사용된다. 그럼 다익스트라 알고리즘은 어떻게 작동할까? 그리디처럼 현재 주어진 노드에서 가장 적은 비용으로 갈 수 있는 노드로 움직이는 방식을 가졌다. 상세한 설명 이전에 아래 그림을 보자 우리가 가고자하는 노드로 도착하기전에 이전에 방문한 곳을 계속해서 돌다간 도착할 수 없다. 그렇기..

투 포인터란? 정렬된 배열에서 한 쌍씩 검색하는데 사용되는 쉽고 효과적인 알고리즘이다. 두개의 기준을 잡고 안에 값들에 다라 조건을 걸어, 두 기준(pointer) 들을 옮겨주는 양상이다. 정렬된 배열 A(오름차순으로 정렬됨)가 N개의 정수를 가지고, 그 합이 X와 같도록 원소 쌍(A[i], A[j])이 존재하는지 알아보고자 하는 상황에서 투 포인터를 사용할 수 있다. def isPairSum(A, N, X): for i in range(N): for j in range(N): if(i == j): continue if (A[i] + A[j] == X): return True if (A[i] + A[j] > X): break return 0 arr = [2, 3, 5, 8, 9, 10, 11] val =..

구간한 배열이란? 순차적 계산 모델에서 계산하기 위해 yi = yi - 1 + xi 공식을 사용하여, 각 출력 값을 순차적으로 계산하기 위해 사용되는 기법이다. (알고리즘이라기보단 테크닉이다) 그렇다 이해하기 힘들테니 쉽게 얘기 하겠다. 어떠한 N크기의 배열이 있다 가정하자. 해당 배열에서 어떤 부분의 배열의 합을 구하려면 반복문을 통해 합을 구할 수 있다.O(N) 그러나 이러한 계산을 O(1)로 만들 수 있다면?! 구간합 배열을 사용하자 1 2 3 4 5 6 ... 1 3 6 10 15 21 ... N +1 크기의 배열을 만들어준다. 이후 해당 인덱스들의 누적합을 N+1 크기의 배열에 채워나간다. 만약 2~4 인덱스를 가진 요소들의 부분합을 구하고싶다면? (5인덱스에속한 N+1 배열의 값) - ( 2인..

비트마스킹이란? 비트 단위로 내가 저장하고싶은 값을 보존하는 것이다. 우리가 4개의 visited 공간을 만들고 싶다면 파이썬 visited = [0] * (4) 자바 Integer[] visited = new Integer[4] 이런식으로 만들 수 있지만 더욱이 메모리를 아껴서 할당 할 수가 있다. 바로! 비트로 바꾸는 것이다 0000 을 통해 우리는 4개의 visited를 만들 수 있는 것이다. 0번째를 방문하면 0001 이후 3번째를 방문했다면 1001 이후 1번째를 방문했다면 1011 마지막으로 2번째를 방문했다면 1111이된다. 그렇다. 이게 끝이다.... 0과 1을 이용해서 우리가 원하는데이터 (visited)를 만듦으로 메모리를 최소화하는 것이다. 아직 비트에 익숙하지 않기에 나중에 다시금 ..

백트레킹이란? 특정 제약 만족 문제에 대한 해결책을 찾기 위해 사용하는 알고리즘으로, 해결책에 대한 후보를 점진적으로 접근하고, 접근하던 후보가 유효한 해결책으로 완성될 수 없다고 판단되는 즉시 바로 전에 후보로 후퇴하여 다른 후보로 접근한다. 이미지로 보면 이러하다 . 사실 미로찾기와 같다. 미로찾기하면 무슨 알고리즘이 생각나는가? 바로 DFS다. 백트레킹은 완전 탐색의 한 종류인데 DFS를 활용하여 사용할 수 있다. 이번에는 그래프를 잠깐 잊고 아래 문제를 풀어보자 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.ne..

BFS 너비 우선 탐색이란? 탐색 알고리즘 중 깊이 우선 탐색(DFS) 와 비교되는 방법으로, 가장 가까운 곳들을 먼저 탐색하고, 그 다음 거리에 있는 것들을 탐색하는 방법이다. 위에 그림을 보면 DFS와 같은 그래프지만 움직이는 양상이 다르다. 이전 DFS의 경우 왼쪽노드를 끝까지 접근했지만 이번에는 층별로 접근하는 것같이 보인다. 맞다. 층별로 이동하고 있다! BFS는 1노드(루트노드) 에서 가장 가까운 순으로 접근하고 있기 때문에 층별로 접근하고 있다고 볼 수 있다 (아래와같이). 예시로 4개의 간선으로 연결된 9노드는 다른 1노드와 3개 이하의 간선으로 연결된 노드보다 늦는게 당연하다. ( 가까운 순은 1노드와 간선의 개수니까 ) 지금 우리는 BFS와 DFS가 어떻게 다른게 접근하는지 차이점은 이..