태그: 자료구조
16편
-
배열과 연결 리스트: 메모리 구조, 연산별 시간 복잡도, 코딩 테스트 활용
배열과 연결 리스트가 메모리에 놓이는 방식 때문에 인덱스 접근, 중간 삽입·삭제의 비용이 어떻게 달라지는지 설명하고, 투 포인터·슬라이딩 윈도우로 배열 회전, 중복 제거, k번째 큰 수 같은 문제를 Python과 C++로 풉니다.
-
트리 자료구조: 이진 트리, 이진 탐색 트리(BST), 전위·중위·후위 순회
루트·자식·높이 같은 트리 용어부터 전위·중위·후위·레벨 순회, 이진 탐색 트리의 삽입과 검색까지 Python으로 구현하고, 트리 높이, 대칭 트리, 최소 공통 조상(LCA) 문제를 재귀로 푸는 방법을 보여 줍니다.
-
자료구조 입문: 배열·리스트·스택·큐·트리·그래프의 특징과 고르는 기준
배열, 연결 리스트, 스택, 큐, 트리, 그래프, 해시 테이블이 각각 어떤 연산에 빠르고 어떤 연산에 느린지 시간 복잡도로 비교합니다. 브라우저의 최근 방문 페이지 기능을 예로 들어 요구사항에서 자료구조를 고르는 과정을 보여줍니다.
-
언어별 자료구조 비교: C++, Python, Java, JavaScript 표준 컬렉션
C++ vector, Python list, Java ArrayList, JavaScript Array처럼 이름이 비슷한 컬렉션이 내부 구현과 성능에서 어떻게 다른지 배열, 연결 리스트, 맵, 셋 순으로 비교하고 언어별로 알맞은 자료구조 선택 기준을 제시합니다.
-
코딩 테스트 준비 전략: 알고리즘 학습 순서와 시험장 실전 팁
투 포인터·슬라이딩 윈도우·이진 탐색·그래프 탐색부터 DP·그리디·최단경로·위상정렬·트라이까지 개념과 실수 포인트를 풀어 쓰고, 자료구조·패턴·시간 배분·언어 선택으로 이어지는 코딩 테스트 준비 글입니다.
-
AVL 트리 구현: 균형 인수, LL·RR·LR·RL 회전, 삽입과 Red-Black 트리 비교
정렬된 값을 차례로 넣으면 일반 이진 탐색 트리가 한쪽으로 기울어 O(n)이 되는 문제를 AVL 트리가 균형 인수와 회전으로 해결하는 과정을 보여줍니다. LL·RR·LR·RL 회전, 삽입 구현 코드, Red-Black 트리와의 비교를 다룹니다.
-
Python list vs tuple vs set: 성능·가변성 차이와 선택 기준
Python list, tuple, set을 가변성, in 검색과 추가·삭제 성능, 메모리 사용량 기준으로 비교하고, set 인덱싱이나 list를 딕셔너리 키로 쓰는 실수, named tuple과 set 연산 활용, 상황별 선택 플로우를 설명합니다.
-
C++ struct vs class: 기본 접근 제어, POD, C 호환성의 차이
C++에서 struct와 class의 문법상 차이는 멤버와 상속의 기본 접근 지정자뿐입니다. 그런데도 데이터 묶음에는 struct, 불변식을 지키는 캡슐화에는 class를 쓰는 관례가 왜 생겼는지, POD 조건과 C 호환, memcpy 가능 여부까지 설명합니다.
-
스택과 큐: LIFO·FIFO 구현과 괄호 검사·BFS 같은 코딩 테스트 활용
스택(LIFO)과 큐(FIFO)를 Python list·deque와 C++ STL로 구현해 보고, 괄호 검사, 스택 두 개로 큐 만들기, 다음 큰 수, BFS 문제를 풀면서 list.pop(0)이 느린 이유와 C++ pop()이 값을 반환하지 않는 이유도 짚습니다.
-
해시 테이블: O(1) 탐색 원리, 충돌 처리, 코딩 테스트 활용 패턴
해시 함수와 체이닝·개방 주소법 충돌 처리, 부하율 관리가 평균 O(1) 탐색을 만드는 원리를 설명하고, Python dict·Counter·defaultdict로 Two Sum, 완주하지 못한 선수, 베스트앨범, 그룹 애너그램 문제를 풉니다.
-
그래프 자료구조: 인접 리스트와 인접 행렬, 그래프 탐색 기초
인접 리스트와 인접 행렬의 메모리·탐색 비용 차이를 비교하고, BFS·DFS로 연결 요소 개수, 사이클 감지, 위상 정렬을 구현합니다. 친구 추천, 작업 의존성 해결, 미로 최단 경로 같은 실제 적용 예도 함께 다룹니다.
-
알고리즘 시리즈 목차 | 자료구조부터 DP·그리디까지 코딩 테스트 학습 순서
배열·스택·해시 테이블 같은 자료구조부터 정렬, 이진 탐색, BFS/DFS, DP, 그리디, 투 포인터, 슬라이딩 윈도우까지 알고리즘 시리즈 17편을 난이도 순으로 묶고, 입문·중급·집중 대비별 학습 경로를 제시합니다.
-
C++ queue와 stack: 컨테이너 어댑터 사용법과 BFS·DFS 활용
C++ STL의 stack·queue·priority_queue 사용법과 내부 동작 원리를 비교하고, DFS·BFS·작업 스케줄링 실전 예제와 커스텀 비교자 설정 등 흔한 컴파일 에러 해결법을 정리합니다.
-
C++로 자료구조 직접 구현하기: 연결 리스트·이진 탐색 트리·해시 테이블·스택·큐
C++로 연결 리스트, 이진 탐색 트리, 해시 테이블, 스택, 큐를 직접 구현하며 노드 연결과 삽입·삭제가 내부에서 어떻게 일어나는지 설명하고, LRU 캐시와 인접 리스트 그래프 예제로 응용합니다.
-
C++로 O(1) LRU 캐시 만들기: unordered_map + list, splice, 흔한 반복자 실수
unordered_map에 list 반복자를 저장하고 splice로 노드를 앞으로 옮겨 get과 put을 모두 O(1)로 처리하는 LRU 캐시를 C++ 템플릿으로 구현합니다. 용량 초과 시 eviction 순서와 용량 0 같은 경계 조건도 다룹니다.
-
C++ 자료구조 구현 실습: 해시테이블, 트라이 자동완성, O(1) LRU 캐시, Skip List 성능 비교
std::unordered_map만으로 부족할 때 직접 만드는 자료구조입니다. 체이닝과 개방 주소법 해시테이블, 자동완성용 트라이, O(1) LRU 캐시, Skip List를 구현하고 rehash 반복자 무효화 같은 함정을 함께 다룹니다.