✏️ 알고리즘 개요알고리즘 문제를 풀다보면 특정 수열에서 i번째 원소를 기준으로 왼쪽 혹은 오른쪽 원소들에 대해 최대값을 구해야하는 경우가 종종 있다. 아래와 같이 단순하게 왼쪽, 오른쪽 원소들에 대해 반복문을 통해 최대값을 구하는 것을 생각해볼 수 있다.int[] arr = new int[]{5,9,6,2,1,4,5,6,8,10,4};for(int i=0; i=0; j--) { leftMaxValue = Math.max(leftMaxValue, arr[j]); } //오른쪽 최대값 int rightMaxValue = 0; for(int j=i+1; j 그러나 수열의 길이가 매우 길어지고, 찾아야하는 원소의 개수가 많아질수록 위와 같은 반복문은 매우 긴 시간복잡도를 가지..

여느 날처럼 에줍사 스터디를 진행하다가 그래프 탐색 문제에 대해 논의를 하던 중 나머지 스터디원들은 BFS로 접근을 했지만, 혼자 다익스트라로 접근을 했던 적이 있습니다. "왜 다익스트라를 떠올렸을까?"라는 생각을 한 결과, 다음과 같은 잘못된 기저가 깔려있다는 것을 알 수 있었습니다.시간복잡도 : Dijkstra BFS 또한 완전탐색으로 최단 거리를 찾는데 시간이 오래 걸릴 것이라 생각함알고리즘 특성 차이이번 회고를 통해 아래와 같이 잘못된 정보들을 바로잡으려합니다.추상적인 시간복잡도두 알고리즘의 동작 방식조건에 따른 수행 방식 BFS와 Dijkstra에 대한 정리는 이전에 정리해 두었던 글이 있으니 참조용으로 링크만 올려두겠습니다.https://infinitecode.tistory.com/13 [알고..

알고리즘 스터디는 작년부터 시작해서 다양한 스터디에 참여하고, 주도하면서 꾸준하게 진행하고 있는 것중에 하나입니다.첫 스터디부터 어떤 방식으로 하는게 좋을지, 인원은 어느정도가 적당한지, 수준은 어떻게 고려해야할지 많은 고민을 했고, 시행착오를 거쳐왔었습니다. 최근에 진행하고있는 알고리즘 스터디 '에러줍는 4인방'에서 스터디를 진행하면서 방식이 되게 좋고, 많이 성장하고 있다는 걸 느껴 알고리즘 스터디에 대한 하나의 가이드라인 느낌으로 정리해보려합니다.처음 시작SSAFY 수료 이후 코딩테스트 대비를 위한 스터디로 시작했었습니다.알고리즘을 좋아하고 꾸준히 할 수 있는 사람들을 모으다보니 4명 구성으로 시작하게 됐어요.함께 모여서 어떻게 진행할지 얘기를 하다보니 다음과 같은 공통점이 보이더라구요.1. 시간을..

Union-Find?분리 집합이라고도 불리는 유니온 파인드는 그래프 형태의 자료구조에서 정점들의 연결 정보를 알고 싶을 때 사용하는 알고리즘입니다.분리 집합이라고 불리는 이유는 서로 연결된 정점들을 각각의 집합으로 만들기 때문입니다. DFS(BFS) VS Union Find그래프 형태의 자료에서 연결 정보를 알고 싶을 때 DFS, BFS 탐색을 통해서도 알 수 있습니다.그러나 서로 다른 모든 정점의 연결정보를 구하려면 시간이 오래 걸릴 수 밖에 없습니다.10만개의 정점이 있고, 모든 정점이 서로 연결되있을수도 있다면 두 정점의 연결관계를 탐색하는데 최대 10만번의 탐색이 이루어질 수 있기 때문입니다.또한 이러한 연결관계 탐색이 N번 필요하다면 O(N^2)의 시간이 필요합니다. Union Find를 사용하..