이번 포스트에서는 앞서 살펴봤던 투포인터와 아주 유사한 슬라이딩 윈도우에 대해 살펴보자.https://soeasyalgo.tistory.com/47 투포인터이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다. 특별하게 코드가 복잡soeasyalgo.tistory.com 슬라이딩 윈도우(Sliding Window) 알고리즘 문제 살펴보기먼저 Sliding Window를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자.https://www.acmicpc.net/problem/21921 21921번: 블로그첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 ..

이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다.  특별하게 코드가 복잡하지도 않고 쉽게 이해할 수 있는데 왕왕 써먹을데가 많은 알고리즘 중 하나이다. 투 포인터(Two Pointer) 알고리즘  문제 살펴보기먼저 Tow Pointer를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자.https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어..

이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자.위상정렬 알고리즘 문제제시https://www.acmicpc.net/problem/14567  위상정렬 알고리즘이란?위상정렬(位相整列:  Topological Sorting)이란 노드 간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다.대부분의 위상 정렬 문제들은 선-후 관계에 위배되지 않는 경우 중 하나를 출력하는 문제들이다.그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(di..

이번에는 최단 경로의 마지막 알고리즘인 플로이드 워셜 알고리즘에 대해서 살펴보자. 플로이드 워셜 알고리즘 플로이드 워셜의 특징이제까지 다익스트라와 벨만포드 알고리즘을 이용한 최단 경로를 구해봤다. 한 점에서 모든 점까지의 최단 거리를 구할 수 있었고 여차하면 음의 간선까지 처리할 수 있었는데 또 필요한 최단 거리 알고리즘이 있을까?있으니까 여기서 글을 쓰고 있다. ㅎ이번에 알아볼 알고리즘은 플로이드 워셜 알고리즘이다. 플로이드는 이전까지의 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단거리를 구하기 위한 알고리즘이다.물론 다익스트라, 벨만포드의 모든 정점을 출발점으로 해서 N번 돌리면 모든 정점에서의 최단거리를 구할 수 있다. 하지만 플로이드 워셜은 대체로 다익스트라, 벨만포드를 N번 돌릴 때보다 빠..

이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다.벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최단 거..

이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.! 다익스트라 알고리즘이란?다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결국 각 정점까지의 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다.다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다.S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시..

이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자.만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장 짧..

BJ G2 1655 가운데를 말해요 문제링크 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/BOnNK-NiPIs 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지..