자료구조
💡 자료구조란?
- 자료를 효율적으로 CRUD하기 위한 구조를 말합니다.
- 자료구조를 잘 사용하면 시간과 공간을 절약할 수 있습니다.
선형 자료구조
💡 선형 자료구조
특징 : 데이터가 1 : 1 관계로 들어가 있다.
종류 : 배열, 리스트, 스택/큐, 해시테이블
특징 | 자바 컬렉션 | 속도 or 차이점 | |
배열 | - 인덱스를 통해 바로 접근 가능 - 중간에 데이터를 삽입/삭제하기 어려움 - 배열의 크기를 선언 시 지정 |
ArrayList | - add : O(1)/O(n) - get : O(1) - contains : O(n) - remove : O(1)/O(n) |
리스트 | - 노드에 데이터와 포인터가 존재 - 인덱스가 없어 head부터 순차 접근 - 중간에 데이터를 삽입/삭제하기 쉬움 - 크기를 선언 시 지정하지 않아도 됨 |
LinkedList | - add : O(1) - get : O(n) - contains : O(n) - remove : O(1) |
스택 | - 후입 선출 (나중에 들어온게 먼저 나간다) - top / bottom - push, pop, peek |
Stack | - push : O(1) - peek : O(1) - size : O(1) - pop : O(1) |
큐 | - 선입 선출 (먼저 들어온게 먼저 나간다) - front / rear - enqueue(offer), dequeue(poll) |
LinekedList | - offer : O(1) - peak : O(1) - size : O(1) - poll : O(1) |
데큐 | = double-ended queue, stack + queue - 양쪽에서 삽입 삭제가 가능 - front / rear - add(offer), remove(poll) - addFirst, addLast, removeFirst, removeLast - Stack, Queue와 달리 idx를 통해 임의 원소에 접근 가능 - 중간 위치에 데이터를 삽입, 삭제가 어렵다 |
ArrayDequeue | - offer : O(1) - peak : O(1) - size : O(1) - poll : O(1) |
해시테이블 | - 해싱 함수를 통해 키 -> 해시로 변환한다 - key + value - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다 (시간복잡도 : 평균 O(1), 최악 O(n)) - 보안성이 높다 (Key와 Hash간의 연관성X) - 데이터 캐싱에 자주 사용된다. - 중복 제거에 유리하다. |
HashTable, HashMap* LinkedHashMap TreeMap |
- Map : key + value가 엔트리로 저장 - HashMap : 저장순서X, 정렬X - LinkedHashMap : 저장순서O, 정렬X - TreeMap : 저장순서X, 정렬O |
* HashTable은 Thread-safe(O) - 멀티 쓰레드 환경 아니면 성능은 ↓, key에 Null 값 허용(x), Enum(O), 보조해시(x)
HashMap은 Thread-safe(x), key에 Null값 허용(O), Enum(x), 보조해시(O) - 해시 충돌이 적어, 성능 높음
HashTable | HashMap | |
Thread-safe | O | X |
Key에 Null허용 | X | O |
Enum | O | X |
보조해시 | X | O |
💡 문제 풀이
제목 | 풀이 후 정리 |
숫자의 합 구하기 | 단순 반복문 사용 |
평균 구하기 | 단순 반복문 + 단순 평균 공식 사용 |
일차원 구간합 | 일차원 배열에서 특정 범위의 합계를 여러 번 구해야할 때 구간합을 사용하면 속도를 빠르게 할 수 있다. |
이차원 구간합 | 중복 for문으로 1열과 1행의 일차원 구간합을 구하고, 2 열 2 행부터 양 대각선의 합계에서 그 사이의 합계를 빼주면 2차원 범위 합을 구할 수 있다. |
투 포인터 - 연속된 자연수 | 두 개의 포인터를 사용하여 연속된 수들의 합이 특정 수가 나타나는지 여부를 확인하도록 한다. while문을 통해 마치 이진탐색을 하듯 합계가 크면 포인터 간격을 줄이고, 합계가 작으면 포인터 간격을 늘리도록 한다. |
투 포인터 - 주몽의 명령 | 숫자가 붙은 여러 개의 재료 중에서 2개의 재료를 사용해 갑옷을 만드는 문제로, 한 번의 정렬과 투 포인터를 사용하여 문제를 풀이했다. 마찬가지로 while문을 통해 이진탐색을 하듯 풀었으며 이번에는 양 끝에 포인터를 두고 두 수의 합계가 크면 우측 포인터를 좌측으로, 합계가 작으면 좌측 포인터를 우측으로 이동하면서 문제를 풀었다. |
투 포인터 - 좋은수 구하기 | for문 안에 while문을 사용한 것으로 주몽의 명령에서 한 단계 더 나간 상태이다. 사실상 시간 복잡도를 계산할 수 있는지 보는 문제였다. |
이 외에 슬라이딩 윈도우, 스택과 큐 문제를 풀이했다.
[ 출처 ]
- 부트캠프에서 배운 강의 내용을 토대로, [Do it! 알고리즘 코딩 테스트] 를 보고 요약한 내용입니다.
- 저작권 이슈가 있으면 얘기해주세요.
'자료구조, 알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
2. 자료구조 - 선형자료구조 - 큐 (0) | 2023.01.21 |
---|---|
1. 코딩 테스트 준비하기 - 시간 복잡도와 논리 오류 잡기 (0) | 2023.01.20 |