자료구조와 알고리즘9 [코테에 많이 활용되는 기법] - 메서드 etc. 1. 아무리 봐도 로직은 맞는데 시간초과가 날 경우 생각해볼 방안 1-1. 출력 형식을 System.out.println이 아 String Builder로 가져가자. 1-2. 입력 형태를 Scanner가 아닌 BufferedReader로 가져가자. * StringBuilder에 모든 내용을 한꺼번에 넣어서 append하는 것보다 하나씩 분리해서 append를 이어붙이는 식으로 해야 속도가 더 빠르다. 2. HashSet에 add 메서드 사용 시 배열을 넣을 경우, 해당 배열의 참조변수가 들어가기 때문에 배열 간의 중복검사는 set으로 할 수 없다. 🏷️ Integer ArrayList를 int 배열로 바꾸고자 할 때 import java.util.*; public static void main(Strin.. 2024. 1. 15. [비선형 자료구조] - 균형 이진탐색트리 앞서 이진 탐색 트리는 O(logN) 이라는 시간 복잡도를 가져, 탐색 측면에서 이점이 있는데, 삽입 순서에 따라 한쪽으로 치우친 사향트리가 될 경우, O(N)의 시간 복잡도를 갖게 되어, 이점이 사라진다. 따라서 이러한 케이스에 대한 이진 탐색 트리의 단점을 보완하기 위해, 균형을 잡는 여러 방법들 중 AVL 트리에 대해 학습해보고자 한다. 이진 탐색 트리의 기본적인 특징은 여기서 참고! 🌳 균형 이진 탐색 트리란? ▪ 노드의 삽입과 삭제을 진행하면서, 균형을 자동으로 맟춰주도록 동작한다. ▪ 모든 노드의 좌우 서브 트리 높이가 2이상 차이 나지 않는 트리 ▪ 트리의 양쪽 높이 차이가 2이상 날 경우 : 삽입, 삭제, 탐색 등의 시간 복잡도 증가 ex. 사향트리 - 시간복잡도 : O(N) ▪ 종류에는 .. 2023. 12. 26. [비선형 자료구조] - 이진 탐색 트리의 특징, 삽입, 삭제, 검색 과정 앞서 트리에 대한 기본 특징은 여기서 참고 이진 트리는 트리 중에서도 최대 2개의 노드까지 가질 수 있는 트리이다. 🔎 이진 탐색 트리란? ▪ 크기 순으로 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드로 작성된 트리 ▪ 모든 트리의 구성은 위와 같은 규칙을 지키고 있으며, 중복된 키는 허용하지 않는다. - 검색 목적의 자료구조이기 떄문 ▪ 이진 탐색 트리를 순회할 경우, 중위순회 방법 사용 시, 정렬된 데이터를 얻을 수 있다. ▪ 정렬되어 있다는 특징 때문에 균형이 유지되어 있을 경우, 이진 트리에 비해 탐색이 빠르다. ▪ 균형 상태 : O(logN) ▪ 불균형 상태 : O(N) * 이진 트리 : 규칙이 없이, 정렬되지 않은채 저장된 트리 🤔 이진 탐색 트리는 왜 쓰는 걸까. ❓ ☑ 탐색 속도 향상.. 2023. 12. 26. [알고리즘] - 투 포인터 (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 2 다음
