알고리즘

이진 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 빠르게 찾기 위해 사용하는 효율적인 탐색 알고리즘입니다. 이진 탐색의 원리는 배열을 절반씩 나누어 검색 범위를 줄여 나가며 원하는 값을 찾는 것입니다.정렬된 배열 필요: 이진 탐색은 배열이 정

배열이나 문자열에서 특정 구간의 합이나 빈도를 빠르게 계산할 때 매우 유용합니다. 특히 다수의 쿼리를 처리하는 문제에서 시간 복잡도를 개선하는 데 큰 효과가 있습니다.원본 배열을 기반으로 누적합 배열을 만듭니다.누적합 배열i = 누적합배열i-1 + 원본배열i구간 합은

(sj%M)-(si-1%M)==0 ----> M의 배수(sj-si-1)%M==0⭐️ sj=si-1 ⭐️-----> 나머지가 같다🏷️ nC2 -----> 나머지가 같은 구간의 시작 / 종료 범위 조합 찾기

배열내 S/E 인덱스를 통해 구간의 변경하며 구간내 합을 구하는 알고리즘원본 배열 생성 -> 구하려는 값(15)의 연속된 숫자의 배열ex) {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}start / end 인덱스 위치 0으로 초기화count:1 (

정렬된 배열이나 리스트에서 두 개의 포인터를 조작하여 원하는 값을 빠르게 찾는 기법왼쪽 포인터(L), 오른쪽 포인터(R) 두 개를 사용해서 특정 조건을 만족하는 구간을 탐색함배열 양쪽 끝에서 시작 → 서로 좁혀오면서 조건을 만족하는 값을 찾는 방식예제: 정렬된 배열에서

🎯 Bound(경계 설정) > ✅ 초과값 중 최소값 > ✅ 이상값 중 최소값

✅ mid \* (mid + 1) / 2$$SUM = N\*(N+1)\\over2$$$$N^2+N = 2\*SUM$$$$ N^2 = 2\*SUM \\N+1\\approx0$$$$ N = \\sqrt{2\*SUM}$$문제 : https://www.cod

✅ 노드간 연결을 통한 최종 노드 기준 관계 재구성 → 트리 사이클 판별👌🏻→ 노드 묶음? 판별👌🏻노드의 연결노드의 최종 부모 update

✅ BFS + 우선순위 큐"비용"이 가중치로 존재하는 문제에서 많이 사용됩니다.예: 다익스트라(Dijkstra), 최소 비용 경로 탐색→ 우선순위 큐 (PriorityQueue)로 최소 비용 우선 탐색❌ BFS는 Queue를 사용합니다. -> 가중치가 없다는 전제하에

https://www.acmicpc.net/problem/1010조합을 계산할 수 있는 삼각형 형태의 배열메모이제이션 없이도 빠르게 조합을 계산 가능 ✅$$ {}{2}C{1}\+{}{2}C{2}={}{3}C{2}$$상위 숫자 = 하위의 두 숫자의 합 자신의

✅ 1단계. DP 조건 확인최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있는가?중복 하위 문제: 같은 하위 문제가 반복 발생하는가?➡️ 이 두 가지가 있으면 DP로✅ 2단계. 상태(state) 정의 👉🏻 추적 개수에 따라 차원 설정dpi, dpi, dpidir

🔹 Next Permutation문자열 또는 수열에 대해 사전순으로 다음에 오는 가장 작은 순열 구하기※ 사전순으로 가장 큰 순열은 내림차순으로 정렬된 상태입니다.cba는 abc의 사전순 가장 마지막 순열입니다.🎯 i 오름차순 ➡️ 내림차순 깨짐🎯 내림차순 i

회전 전: 기준점 (1,1) o ← (1,1) o o ← (2,1), (2,2)90도 회전 후 (🚨기준점 고정) o o o