1. 슬라이딩 윈도우(Sliding Window) 하나의 윈도우(특정 범위)를 만들어 그 윈도우를 움직이면서 우리가 원하는 값을 찾아내는 알고리즘으로 O(n^2)인 시간복잡도를 O(n)으로 줄일 수 있다. 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 위의 문제를 풀어보면서 슬라이딩 윈도우에 대해 알아보자 문제 찬솔이는 블로그를 시작한 지 벌써 N일이 지났다. 요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기..
1. 투 포인터 알고리즘이란 리스트나 배열에 순차적으로 접근하여 두 개의 포인터를 가지고 목표로 하는 값을 찾아내는 알고리즘 O(n)의 시간 복잡도를 가진다. 참고 : https://butter-shower.tistory.com/226 2. 문제를 보면서 알고리즘을 살펴보자. 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착..
1. 최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리를 말한다. 2. 특징 그래프는 사이클을 포함하지 않는다.(사이클이 포함되면 가중치의 합이 최소가 될 수 없기 때문) N개의 노드가 있을 경우, 최소 신장 트리를 구성하는 에지의 개수는 N-1개이다. 에지 리스트의 형태로 데이터를 담는다. 사이클을 확인하는 로직은 유니온 파인드 내부에 구현해야 한다. 3. 알고리즘 로직 1) 데이터를 그래프로 구현 및 유니온 파인드 배열 초기화 그래프는 인접 리스트가 아닌 에지 리스트로 구현한다. 유니온 파인드 배열은 사이클 처리를 위함 2) 그래프를 가중치 기준으로 정렬 가중치를 기준으로 오름차순 정렬한다. 위의 표를 기준으로 봤을 때 에지는 6, 3, 5, 2, 1..
1. 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제로, 가중치 그래프에서 간선의 가중치의 합이 최소가 되게 하는 경로를 찾는 것이 목적이다. 1) 단일 출발(single-source) 그래프 내 특정 노드에서 출발하여, 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제이다. 2) 단일 도착(single-destination) 모든 노드들로부터 출발하여, 그래프 내 특정 노드로 도착하는 가장 짧은 경로를 찾는 문제이다. 3) 단일 쌍(single-pair) 주어진 노드 u, v간 최단 경로를 찾는 문제이다. 4) 전체 쌍(all-pair) 그래프 내 모든 노드 쌍에 대한 최단 경로를 찾는 문제이다. 2. 최단 경로 알고리즘의 종류 다익스트라(Dijkstra) 벨만포드(bel..
1. 플로이드 워셜이란 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘이다. 2. 특징 음수 가중치 에지가 있어도 알고리즘 수행이 가능하다. 동적 계획법의 원리를 이용하여 알고리즘에 접근한다. 그래프를 인접 행렬로 표현한다. 3. 핵심 원리 A노드에서 B노드까지 최단 경로를 구했을 때, 최단 경로 위에 K노드가 존재한다고 하면, 그것을 이루는 부분 경로 역시 최단 경로다. '최단 경로 위에 K노드가 존재한다고 하면, 그것을 이루는 부분 경로 역시 최단 경로다.'라는 말이 무슨 뜻이냐면 위와 같은 그래프가 있을 때, 노드1에서 노드 5로 가는 최단 거리는 1 -> 2 -> 4 -> 5로 가는 경로가 최단 경로이다. 이러한 결과를 얻었을 때, 1 -> 2, 2 -> 4, 혹은 1 -> 4로 가는 경로..
1. 벨만-포드 알고리즘이란 그래프에서 최단 거리를 구하는 알고리즘 2. 특징 음수 가중치 에지가 있어도 로직이 수행이 가능하다. 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다. 3. 알고리즘 로직 1) 주어진 데이터를 Edge리스트로 그래프로 구현한 후, 거리 배열의 값을 업데이트한다. Edge를 중심으로 동작하기 때문에 그래프를 Edge리스트로 구현한다. 최단 경로 배열은 출발노드는 0, 나머지는 무한대(99,999,999 혹은 INF)로 초기화한다. 출발 노드가 방문한 적 없는 노드일 때는 값을 업데이트 하지 않는다. if(출발 노드의 거리 배열의 값 + Edge 가중치
1. 다익스트라(Dijkstra)란 그래프에서 최단거리를 구하는 알고리즘이다. 모든 간 양수이어야 한다. 출발 노드와 도착 노드간의 최단거리를 구하는 것이 아니라 출발 노드와 나머지 노드간의 최단 거리를 표현하는 것. 2. 알고리즘 로직 다익스트라는 단일 출발 문제에 해당한다. 다익스트라 알고리즘은 BFS와 유사하다. 1) 주어진 데이터를 그래프로 구현하기 시간 복잡도를 고려하여 인접 행렬보다는 인접 리스트로 구현하는 것이 좋다. 인접 리스트에 연결된 배열은 (노드, 가중치)와 같은 형태로 구현을 한다. 2) 최단 거리 배열 초기화하기 최단 거리 배열을 생성하고, 출발 노드는 0, 나머지는 무한(99,999,999, "INF"라고 표현)으로 초기화한다. 우선 순위 큐에 출발 노드와 거리를 먼저 넣는다. ..
1. 위상 정렬이란 사이클이 없는 방향 그래프에서 노드간의 순서를 찾는 알고리즘이다. 순서가 정해져 있는 작업을 차례로 수행할 때, 그 순서를 결정하기 위해 사용하는 알고리즘이다. 사이클이 존재하면 노드간의 순서를 명확히 할 수 없기 때문에 위상 정렬을 적용할 수 없다. 늘 같은 정렬 결과를 보장하지 않는다. 2. 위상 정렬의 흐름 진입 차수(in-degree) : 자기 자신을 가리키는 간선의 개수 위와 같은 그래프가 주어졌을 때, 1) 진입 차수 배열을 생성한다. * 여기서 보면 노드1의 경우 0, 2와 3의 경우 1,4와 5의 경우 2가 된다. 2) 진입 차수 배열에서 값이 0인 노드를 큐에 저장한다. 3) 큐에서 poll한 노드를 결과 리스트에 추가하고, poll한 노드가 가리키는 노드들의 진입 차..
