자료구조와 알고리즘/알고리즘3 [알고리즘] - 투 포인터 (Two Pointer) 👉 투 포인터란? ▪ 어떤 값을 가리키는 두 개의 변수(포인터)를 의미한다. ▪ 주로 1차원 배열에서 순차적으로 접근할 때 사용되며, 연속합, 부분합 등에 사용된다. ▪ 두 개의 포인터 배치 방법 - 같은 방향에서 시작 - 서로 다른 방향에서 시작 (양 끝) ▪ 중첩 for문에서의 개선된 시간복잡도 : 매 루프마다 1칸씩만 이동해서 전체 순회를 마침으로, O(N^2)문제를 O(N) 시간복잡도로 해결할 수 있다. 👉 투 포인터를 써야하는 경우 ▪ 입력으로 들어오는 데이터의 크기가 매우 큰 경우 (ex. 100,000,000) ▪ 다중 for문으로 구현이 가능해 보이지만 대략적인 시간 복잡도가 매우 큰 수치로 보일 경우 👉 투 포인터 vs DP (동적 계획법) ▪ 투 포인터로 풀리는 문제여도, 입력값의 크기.. 2023. 12. 21. [알고리즘] - 이진 탐색(Binary Search) 🚩이진 탐색이란 ? 오름차순으로 정렬된 리스트에서 특정 값을 빠르게 탐색하는 방법 🔎탐색 방법 1. 찾고자 하는 값(타깃 값)과 데이터의 중앙에 있는 값을 비교한다. 2 - 1. 타깃 값이 더 작으면 데이터의 왼쪽 부분에서 이진 탐색을 진행한다. 2 - 2. 타깃 값이 더 크면 데이터의 오른쪽 부분에서 이진 탐색을 진행한다. 3. 타깃 값을 찾았다면 탐색을 종료한다. 🔮 시간 복잡도 매 실행 마다 데이터의 탐색 범위가 2분의 1씩 줄기 때문에 O(logN)의 시간복잡도를 가진다. 🚩이진 탐색 구현 방법 ☑ 이진 탐색은 배열에서 탐색을 하는 방법이다. ⚙️ 1. 반복문 - left - 0, right - 배열 길이 - 1 로 시작, 중앙 값 비교를 통한 인덱스 갱신으로 타깃 값까지 도달 public sta.. 2023. 12. 19. [알고리즘] - 분할 정복 (Divide and Conquer) 분할 정복 ( Divide & Conquer ) ✏ 큰 문제를 작은 부분 문제로 나누어서 해결하는 방법 ex. 합병 정렬, 퀵 정렬, 이진 검색 etc. ✏ 분할 정복의 장/단점 - 큰 문제에서 작은 문제로, 문제를 나눔으로써 어려운 문제를 해결할 수 있다. - 서로 영향이 없는 데이터 간에 분할(병렬 처리)해서 처리할 수 있다. - 동일 코드 재귀 호출로 인한 오버헤드가 발생할 수 있다. - 스택 오버플로우, 과도한 메모리 사용을 초래하게 된다. 🚩 분할 정복 문제 풀이 단계 1. 분할 (Divide) : 문제를 하나 이상의 작은 부분들로 나눈다. 2. 정복 (Conquer) : 각각의 부분 문제들을 해결한다, 정복해 나간다. 3. 결합 (Combine) : 각 부분들의 해답을 통합하여 원래 문제의 답.. 2023. 12. 16. 이전 1 다음
