빙응의 공부 블로그

📝개요 슬라이딩 윈도우 알고리즘에 대해 알아보자 📝슬라이딩 윈도우의 핵심 이론 일단 배열에서 K개씩 더하는 것 중에서 큰걸 찾는 문제가 있다고 생각해보자..57-414-325 기본적으로 생각 안하고 풀 수 있는 것은 O(N*K)인 브루트포스를 생각할 것이다.for(int i = 0; i   해당 아이디어는 아래와 같은 중복된 연산을 해야하기에 효율성이 떨어진다. 슬라이딩 윈도우의 핵심아이디어는윈도우를 지정해서 이동하면서 계산하는 것이다. 위 사진처럼 윈도우의 범위 K를 더하고 이동할 때마다 윈도우 범위에서 벗어난 수를 빼주면 된다.   📝 추천 문제 12847번: 꿀 아르바이트문제윤호는 퍼주기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.각 날마다 일의 차이때문에 일마..

📝개요 그래프 거리 알고리즘에 대해 알아보자📝다익스트라다익스트라 알고리즘은 최단 거리를 구하는 알고리즘이다.주요 특징은 다음과 같다.기능특징시간복잡도출발 노드의 모든 노드 간의 최단 거리 탐색에지는 모두 양수O(ElogV) 📝 다익스트라 핵심 이론총 5단계로 알아보자.1. 인접 리스트로 그래프 구현하기다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 클것을 대비해서 인접 리스트로 구현하는 것이 좋다.그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결 V = Integer.parseInt(st.nextToken()); // 정점의 개수 E = Integer.parseInt(st.nextTo..

📝개요DP의 기본 조합에 대해 알아보자!!📝조합 조합은 주어진 요소들 중에서 특정 개수만큼을 선택하는 문제를 말한다.조합은 수학적 원리를 기반으로 다양한 알고리즘적 접근 방식을 통해 해결한다!!조합조합은 주어진 집에서 순서와 상관없이 특정 개수의 원소를 선택하는 방법이다.예를 들어, 집합 {1,2,3}에서 2개를 선택하는 조합은 {1, 2}, {1, 3}, {2, 3}이다.조합의 수주어진 집합의 원소의 수가 N일때, 그 중에서 K개를 선택하는 경우의 수는 C(N,K)라 표기한다.📌순열과의 차이?조합의 수는 순열의 계산식과 매우 유사하나 1가지 다른 특징이있다.분모에 K!를 곱한다.이는 조합의 특징에 있다. 조합은 순서 상관없이 경우의 수를 구하기 때문에 K!를 이용해서 중복되는 것들을 제거한다.!!..

특수한 상황에서 쓰는 0-1 BFS 알고리즘에 대해 알아보자 📝 0-1 BFS?0-1 BFS는 가중치가 0 또는 1인 그래프에서 최단 경로를 찾기 위해 사용하는 알고리즘을 말한다.일반적으로 BFS는 각 이동에서 동일한 가중치를 가지나, 0-1 BFS는 0또는 1의 가중치를 다르게 처리한다.이 알고리즘은 데크를 이용해서 가중치가 0인 간선을 데크 앞에, 가중치가 1인 간선을 데크 뒤에 추가하는 방식으로 구현한다. 특징해당 알고리즘은 문제의 가중치가 0 또는 1로 다르게 처리할 때 사용한다.Deque(데크)를 사용하여 구현하며 가중치가 0인 것을 데크 앞에, 가중치가 1인 것을 데크 뒤에 둔다.특수한 상황(가중치가 0, 1)인 상황에서 다익스트라보다 효율적으로 작동한다. 📝 0-1 BFS 자세히 이해해보..

플로이드 워셜은 그래프에서 최단 거리를 구하는 알고리즘이다.최단 거리 문제는 다익스트라, 벨만포드, 플로이드 워셜이 있다.기능특징시간복잡도모든 노드 간에 최단 경로 탐색음수 가중치 에지가 있어도 수행가능동적 계획법의 원리를 이용해 알고리즘에 접근O(V^3)시간복잡도가 매우 높은 편으로 V가 크면 안 쓰는 것이 좋다.  V가 200개 정도면 된다.  📝 핵심 이론플로이드 워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때 최단경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 즉, 1~5까지의 최단 경로를 구했을 때 인접 노드가 아닌 1~4까지의 최단 경로도 1~5경로와 같다.대신 출발과 인접하지 않는 조건이다.(전체의 최..

📝 개요탐색 알고리즘 깊이 우선 탐색과 너비 우선 탐색, 이진 탐색에 대해 알아보자📝 깊이 우선 탐색(DFS)깊이 우선 탐색은 무엇일까?DFS는 그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여최대 깊이까지 탐색을 마친 후 다음 분기로 이동하는 것을 말한다. 기능특징시간복잡도(노드 = V, 엣지 = E)그래프 완전 탐색재귀 함수로 구현스택 자료구조 이용O(V + E) 깊이 우선 탐색의 핵심 이론DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용한다. 깊이 우선 탐색 응용단절점 찾기단절선 찾기사이클 차기위상 정렬📌 DFS 사용해보기1. DFS를 시작할 노드를 정..