깊이 우선 탐색(DFS) 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 알고리즘. 주로 스택 혹은 재귀함수를 사용합니다. 특징 메모리 사용이 적음 목표 노드가 깊은 단계에 있을 때 유리 모든 노드를 방문하고자 할 때 적합합니다. 사용 사례 미로 찾기 위상 정렬 사이클 탐지 예시 코드 import java.uti...

투 포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.

좌표 압축(Coordinate Compression) 수의 범위가 매우 큰 상태에서 수의 값과 상관 없이 숫자 간의 대소관계만 알면 될 때 이용하는 알고리즘이다. 기본적으로 해당 알고리즘은 정렬, 이분 탐색을 이용한다. STEP 1 : 입력받은 배열과 별도의 배열을 하나 선언한다. 이때 별도의 배열을 압축 배열이라고 명명한다. 압축 배열에는 ...

동적 프로그래밍(Dynamic Programming) 기법 정의 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 방법의 핵심은 중복되는 계산을 피하고 결과를 저장하여 재사용함으로써 효율성을 높이는 것입니다. 특징 최적 부분 구조(Optimal S...

슬라이딩 윈도우 기법 정의 슬라이딩 윈도우는 일정 크기의 ‘윈도우’를 데이터 위에서 이동시키면서 문제를 해결하는 방법. 주로 배열이나 문자열과 같은 선형 데이터 구조에서 사용됩니다. 특징 고정 크기의 윈도우를 사용합니다. 윈도우를 한 칸씩 이동시키며 데이터를 처리합니다. 이전 윈도우의 계산 결과를 활용하여 효율성을 높입니다. 적용...

조합론적 접근 정의 조합론적 접근이란 주어진 문제를 더 작은 부분 문제로 나누고, 이를 조합하여 전체 문제의 해답을 찾는 방법입니다. 이는 복잡한 시스템이나 구조를 더 단순한 구성 요소로 분해하고 분석하는 것을 포함합니다. 특징 열거 : 가능한 모든 경우의 수를 체계적으로 나열합니다. 계수 : 특정 조건을 만족하는 경우의 수를 세는 것에 ...

ABC 210 D - National Railway 【문제 개요】 타카하시왕국은 H행 W열의 칸으로 표시됩니다. 북쪽으로부터 i행째, 서쪽에서부터 j열째의 칸은 (i, j)로 표시됩니다.(1 ≤ i ≤ H, 1 ≤ j ≤ W) 이번에 타카하시 왕국의 국민으로부터 교통의 편리성을 위해 철도의 건설을 요구하는 목소리가 다수 전해졌고, 국왕의 타카하시군은...

ABC 209 D - Collision 【문제 개요】 타카하시왕국은 N개의 마을과 N - 1개의 도로로 이루어져 있어, 마을에는 1부터 N까지의 번호가 붙어 있습니다. 또, i(1 ≤ i ≤ N-1)번째 도로는 마을 aᵢ과 bᵢ를 쌍방향으로 연결되어 있어, 모든 도시는 도로를 통해 서로 연결되어 있습니다. 도로는 모두 같은 길이입니다 당신은 다음과 ...

ABC 216 C - Many Balls 【문제 개요】 비어있는 상자가 있습니다. 타카하시군은 아래의 작업을 원하는 만큼 수행할 수 있습니다. 작업 A : 상자 안에 볼을 1개 추가한다 작업 B : 상자 안의 볼의 수를 2배로 한다. 합계 120회 이내에 상자 안의 볼의 수를 정확히 N개로 하는 방법을 구하시오. 또한, 주어진 제약으로 반드...

ABC 215 C - One More aab aba baa 【문제 개요】 문자열 S의 각 문자를 나열하여 만들 수 있는 문자열을 사전순으로 모두 열거했을때 앞에서부터 K번째에 오는 문자열을 구하시오. 각 문자를 나열하여 만들 수 있는 문자열이란? 문자열 A가 문자열 B의 각 문자를 나열하여 만들 수 있는 문자열이다 란, 임의의 문자가 문자열 A...