유니온 파인드(또는 Disjoint Set Union, DSU)는 서로소 집합(Disjoint Set)을 다룰 때 사용하는 자료구조다. 주로 무방향 그래프의 사이클 판별이나 크루스칼 알고리즘을 활용한 최소 신장 트리(MST) 문제에서 자주 사용된다. 1. 유니온 파인드의 핵심 아이디어여러 개의 원소가 있을 때, 이들을 서로소 집합(즉, 겹치지 않는 집합)으로 분리하여 관리한다.두 원소가 같은 집합에 속하는지 확인하거나, 두 집합을 합치는 연산을 지원한다.대표적으로 사용하는 연산은 아래 두 가지다:find(x) : 원소 x가 속한 집합의 루트(대표값)를 찾는다.union(x, y) : 원소 x, y가 속한 두 집합을 하나로 합친다. 2. 기본 구현 # 부모 테이블 초기화parent = [i for i in..

1. 슬라이딩 윈도우란?슬라이딩 윈도우(Sliding Window) 알고리즘은 고정된 크기 또는 가변 길이의 부분 구간(subarray) 을 배열이나 문자열에서 연속적으로 이동시키면서 특정 값을 계산하는 기법입니다.이름 그대로 "창문(window)"을 왼쪽에서 오른쪽으로 조금씩 밀면서 처리한다는 의미로,매번 전체 범위를 새로 계산하지 않고 이전 결과를 재활용하여 효율적으로 처리할 수 있습니다. 2. 언제 사용하는가?슬라이딩 윈도우는 다음과 같은 경우에 주로 사용됩니다:고정 길이 구간의 최댓값, 최솟값, 합 등을 구하는 문제가변 길이 구간에서 어떤 조건을 만족하는 최소/최대 구간 찾기문자열에서 중복 문자 없는 가장 긴 부분 문자열 찾기일정 범위 내에서 조건이 유지되는 구간 탐색 3. 슬라이딩 윈도우 동작..

1. 투 포인터란?투 포인터(Two Pointer) 알고리즘은 배열이나 리스트에서 두 개의 인덱스(포인터)를 사용하여 문제를 해결하는 기법입니다.특히 정렬된 배열에서 특정 조건(합, 구간, 중복 제거 등)을 만족하는 값을 효율적으로 찾을 때 자주 사용됩니다.두 개의 포인터를 적절히 이동시키면서 탐색 범위를 조절하고, 불필요한 연산을 줄여 시간 복잡도를 줄이는 것이 핵심입니다. 2. 투 포인터는 언제 사용하는가?투 포인터 알고리즘은 다음과 같은 상황에서 유용하게 사용됩니다.두 수의 합을 구하는 문제 (예: 두 수의 합이 M인 쌍의 개수)연속된 구간을 탐색하는 문제 (예: 부분합, 최소 길이 구간)슬라이딩 윈도우처럼 범위를 옮겨가며 탐색하는 문제중복 제거 혹은 정렬된 배열 병합문자열이나 배열에서 부분 문자열..

문제 링크https://www.acmicpc.net/problem/13144문제길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.입력첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000) 두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.출력조건을 만족하는 경우의 수를 출력한다.풀이골드치고는 굉장히 쉬운 문제 단순하게 생각하면 모든 수열을 만들어 해당 수열에 중복 여부가 있는지를 판별하면 된다. 하지만 모든 수열에 대해서 중복 여부를 판별하기에는 시간이 굉장히 오래걸릴 것이다. 따라서 우리는 수열을 만들 때부터, 이미..

1. 완전탐색(Brute Force)이란?완전탐색(Brute Force)은 가능한 모든 경우의 수를 하나하나 전부 시도해보며 정답을 찾는 알고리즘 기법입니다. 특정 조건을 만족하는 정답을 찾기 위해 문제 공간 전체를 탐색하며, 경우에 따라선 매우 많은 연산이 필요할 수 있지만, 구현이 단순하다는 장점이 있습니다.쉽게 말해, 답이 될 수 있는 모든 후보를 만들어보고 그중 정답 조건을 만족하는 것을 찾는 방법입니다. 정확한 해를 보장하며, 복잡한 최적화보다는 조건을 만족하는 답이 있는지만 찾는 문제에 주로 사용됩니다. 2. 완전탐색은 언제 사용하는가?완전탐색은 시간복잡도가 크기 때문에 다음과 같은 상황에서 주로 사용됩니다:입력의 크기 N이 작을 때 (일반적으로 N 최적의 해를 구할 필요 없이 가능한 해 하나..

문제 링크https://www.acmicpc.net/problem/15686문제크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리..

문제 링크https://www.acmicpc.net/problem/3190문제'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는..

1. 개념 및 정의그리디 알고리즘(Greedy Algorithm)은 문제를 해결할 때 매 순간 가장 최선이라고 생각되는 선택을 하는 방법입니다.탐욕적 접근이라는 이름처럼, 국소적으로 최적의 선택을 반복하면서 전체 최적해(Global Optimum)에 도달하려고 합니다.이 방식은 계산 속도가 빠르고 구현이 간단하다는 장점이 있지만, 항상 정답을 보장하지는 않습니다.따라서, 문제를 그리디로 풀 수 있는 조건을 만족하는지 사전에 확인하는 것이 중요합니다. 2. 사용 조건 (그리디 알고리즘을 적용할 수 있는 경우)그리디 알고리즘이 적용되기 위해서는 다음 두 가지 조건이 필요합니다.① 탐욕 선택 속성 (Greedy Choice Property): 현재의 최선의 선택이 이후의 선택에 영향을 주지 않으며, 이 선택이..

문제 링크https://www.acmicpc.net/problem/1700문제기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 키보드 헤어드라이기 핸드폰 충전기 디지털 카메라 충전기 키보드 헤어드라이기 키보드,..

문제 링크https://www.acmicpc.net/problem/11501문제홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안한다. 홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다. 예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두..