반응형 알고리즘 & 자료구조5 깊이 우선 탐색 vs 너비 우선 탐색 Intro 현재 'do it! 알고리즘 코딩 테스트' 책으로 공부 중인데 그래프 탐색 문제만 나오면 해당 문제가 깊이 우선탐색을 해야 하는지 너비 우선 탐색을 해야 하는지 자꾸만 헷갈린다. 다 풀고 답을 확인해보면 너비 우선으로 풀었어야 할 문제를 깊이 우선으로 푸는 바람에 시간초과가 난다거나, 너비 우선으로 풀어서 답이 도출되지 않아 확인해 보니 깊이우선으로 풀었어야 한다거나...(이건 그냥 내가 잘못 푼 듯ㅎ) 공부가 덜 됐구나 생각이 들어서 오늘은 깊이 우선 탐색과 너비 우선 탐색을 비교하고, 어떤 문제에 어떠한 탐색 방식을 사용해야 하는지 알아보려 한다. 깊이 우선 탐색(Depth-First Search, DFS) 깊이 우선 탐색이란 선택된 첫 노드를 시작으로 다음 분기로 넘어가기 전에 해당 분기.. 2024. 2. 2. java LinkedList 인덱스의 의미 Intro 예전에 공부할 때는 그저 외우는 수준에서 그쳤는데, 오늘은 CS를 준비하면서 그 원리가 궁금해졌다. 그 원리를 파헤쳐 보자우! ArrayList vs LinkedList ArrayList의 경우는 메모리에 저장될 때 연속적으로 저장되고, LinkedList의 경우 메모리에 불연속적으로 저장되나 해당 데이터와 다음 데이터를 가리키는 포인터가 저장되는 노드의 형태로 저장이 된다. 또한 ArrayList는 데이터의 중간 삽입 또는 중간의 데이터를 삭제할 경우 LinkedList에 비해 속도가 느리다. 반면 LinkedList의 경우 해당 노드들이 가리키는 포인터의 값들만 변경하면 되기때문에 ArrayList에 비해 데이터의 중간 삽입 또는 중간 데이터들의 삭제가 더 용이하다고 한다. LinkedLi.. 2023. 12. 7. 알고리즘 이론 (퀵 정렬 ~ 기수정렬) 퀵 정렬 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘 기준값, 투 포인터 사용 시간 복잡도 O(nlogn) worst case = n^2 병합 정렬(merge sort) 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합함 시간 복잡도 O(nlogn) 한 섹션 안에서 n개의 수를 정렬하는 횟수 = n 섹션 수 = n/2/2/2… → logn 기수 정렬(radix sort) 데이터의 자릿수를 비교함 시간 복잡도 O(kn) → 여기서 k는 데이터의 자릿수 10개의 큐를 이용 (10진수인 데이터에 의해) 시간 복잡도가 가장 좋지만 구현하기가 비교적 복잡함 2023. 10. 3. 자료구조 이론 Big-O 표기법 worst case와 average case의 시간복잡도가 비슷한경우가 많기때문에 worst case의 알고리즘의 시간복잡도를 나타내기도함 시간복잡도의 최고차수로 표현됨 (상수 제외함) O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1) Best case 가장 낮은 시간 복잡도 Average case 시간복잡도의 평균값 Worst case 가장 높은 시간 복잡도 8 bit (2^3) → 1byte 1024byte (2^10) → 1KB 1024KB (2^10) → 1MB 하나하나의 바이트마다 주소값을 갖는다 메모리 할당 int → 4byte char → 1byte 2023. 10. 2. 알고리즘 이론 (시간복잡도 ~ 삽입정렬) ✅시간 복잡도알고리즘 선택의 기준이 됨 시간 복잡도를 줄이는 방법알맞은 알고리즘 사용비효율적인 로직 찾아서 효율적으로 리팩토링 (ex)다중 for문) ✅배열과 LinkedList배열은 인덱스가 있기 때문에 값에 접근하는 속도가 리스트에 비해 빠르다.리스트는 포인터로 연결되어있기 때문에 데이터를 삽입하거나 삭제하는 연산 속도가 배열보다 빠르다.크기 변화가 없는 데이터를 다룰때는 배열, 크기가 변하기 쉬운 데이터를 다룰때는 리스트리스트는 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다. ✅구간 합합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 S를 만드는 공식S[i] = S[i-1] + A[i] 구간 합을 구하는 공식i~j까지의 합 → S[j] - S[i.. 2023. 9. 27. 이전 1 다음 반응형
