알고리즘

📌LIS 알고리즘 이란? 최장 증가 부분 수열 - `(LIS : Longest Increasing Subsequence)` 동적 계획법 알고리즘을 응용한 알고리즘 입니다. >❓ 어떤 임의의 수열이 주어졌을때 가장 긴 증가하는 부분수열의 길이는 얼마인가? 를 구하는 알고리즘입니다. 예를들어 다음과 같은 수열이 있다고 가정할때 `3 5 7 9 2 ...

1. 기본 배낭문제 12865 : 평범한 배낭 > dp 2차원배열 응용 > dp 1차원 배열 응용 2. 동전문제 9084 : 동전 > 동전이 K원이 여러종류 주어질때 중복사용을 허용하면서 W원으로 만들수 있는 모든 경우의 수 2294 : 동전 2 > 동전 N원이 종류별로 있을때 중복을 사용해서 K원을 만들수 있는 최소한의 동전 사용 개수 3...

📌 LCS 알고리즘 이란? 최장 공통 부분 수열 $LCS$ - `Longest Common Subsequenc` 동적 계획법을 응용한 알고리즘 입니다. > ❓ 어떤 임의의 수열이 주어졌을때 수열 모두의 가장 긴 공통 부분수열의 길이는 얼마인가? 예를들어보면 ACAYKP CAPCAK 이라는 두 문자열 수열이 있습니다. 이때 가장 긴 공통 부분 수...

📌누적합 알고리즘 이란? 누적합 알고리즘 - $Prefix$ $sum$ > ❓ i~j 번째까지 배열의 총 합은 얼마인가? 문제에서 특정한 배열이 주어졌을때 특정 구간의 연속한 값들의 합을 빠르게 구하는 알고리즘 입니다. 예시를 들어보겠습니다. $[1,2,3

📌 이분탐색이란? 이분 탐색 - $Binary$ $Search$ > ❓ 배열에 특정 값이 어디에 있는가? 배열이 주어졌을때 원하는 값이 있는지 , 있다면 어디에 위치하는지 찾는 알고리즘 입니다. 만약 아래와 같은 배열이 있다고 해봅시다. $[5,2,7,6,9,4]$ 여기서 4 라는 값은 한눈에 찾을 수 있습니다. 하지만 만약에 배열의 길이가...

📌 투 포인터 알고리즘 이란? 투 포인터 알고리즘 - $Two$ $Pointer$ > ❓ 배열에서 어떤 수를 골라서 K 를 만들 수 있는가? 문제에서 특정한 배열이 주어졌을때 두 수의 합,어떤 부분 합이 특정값이 만족하는지 찾는 알고리즘 입니다. 간단하게 이분탐색에서 사용하는 `Start 와 End` 라는 포인터를 각각 하나씩 가지고 `Start ...

📌 슬라이딩 윈도우란? 슬라이딩 윈도우 - $Sliding$ $Window$ >📌 구간의 길이가 M일때 특정한 조건을 만족하는가? 배열이 주어졌을때 문제에서 주어지는 구간의 크기에서 특정조건을 만족하는 경우를 찾는 알고리즘이다. 슬라이딩 윈도우는 투 포인터와 아주 유사하기 때문에 투 포인터를 먼저 공부하고 슬라이딩 윈도우를 공부하는것을 추천하다. ...

📌 배낭 문제란? 배낭문제 , 냅색 문제 - $Knapscak$ $Problem$ >📌 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 방법이 무엇인가?

📌 그래프 - Graph 그래프에는 사실 아주 다양한 형태가 존재합니다. 우리가 일반적으로 사용하는 리스트가 그래프일수도있고 이번에 배울 트리 또한 그래프의 하나입니다. 트리를 배우기 전에 그래프가 무엇인지 자세히 알아보겠습니다. 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 📕무방향 그래프 - Undirected ...

📌 유니온 파인드 - $Union$ $Find$ 또는 상호 베타적 집합 , 분리집합 , $Disjoint$ $Set$ 이라고 부르는 자료구조 입니다. 유니온 파인드의 목적은 두 노드가 같은 집합에 속하는가? 를 찾는 것입니다. 그리고 총 2가지 연산을 수행합니다. Union : 노드를 합칩니다. Find : 서로다른 노드가 같은 집합인지 판별합니다...

📌 최소 스패닝 트리 , 최소 신장 트리 - $MST$ ( $Minimum$ $Spanning$ $Tree$ ) 시작하기에 앞서 먼저 트리의 개념을 다시 살펴봅시다. 트리란 사이클이 없는 양방향 그래프 입니다. 그렇다면 최소 스패닝 트리란 무엇일까요? 최소 스패닝 트리란 트리를 구성하면서 모든 정점을 연결하되 , 가중치의 합이 최소가 되는 트리를 의...

📌 다익스트라 - Dijkstra 다익스트라는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 최소 스패닝 트리에 사용되는 프림알고리즘과 매우 유사하기 때문에 프림알고리즘을 알고 있다면 이해가 쉬울껍니다. 물론 처음 다익스트라를 이해하는데 코드 하나하나를 순차적으로 보는것도 좋은 방법이지만 직관적으로 ...

DinicMaxflow 에 return flow 하면 최대유량 구할수있음.Graph 클래스에 size 는 없어도 됨.

두부장수 장홍준 3 - 14424(https://www.acmicpc.net/problem/14424\\)

2042 : 구간 합 구하기

백준 13510 트리와 쿼리 1

다이나믹 프로그래밍이란 하나의 큰 문제를 여러개의 부분문제로 분할한뒤 , 이전값을 활용하여 문제를 해결하는 기법입니다.1,2,3더하기 시리즈 문제를 통해서 2차원 dp 에 대해 자세히 알아봅시다.📌 1, 2, 3 더하기 1문제링크image정수 N 을 1,2,3 의 합