Computer Science (14) 썸네일형 리스트형 [알고리즘] 자주 사용하는 정렬 버블 정렬(Bubble Sort) 특징인접한 두 요소를 비교해 자리를 바꾸며 정렬하는 방식Loop가 끝날 때마다 가장 마지막에는 가장 큰 값 또는 가장 작은 값이 위치복잡도시간 복잡도 : O(n^2)공간 복잡도 : O(1)장점구현이 간단자료의 이동이 적음단점정렬 속도가 느리기 때문에 실무에서는 사용되지 않고 대부분 교육 목적이나 간단한 작업에만 사용삽입 정렬이나 선택 정렬과 같은 시간 복잡도를 갖지만, 평균적으로 버블 정렬의 교환 횟수가 더 많기 때문에 더 많은 시간 소비선택 정렬(Selection Sort) 특징전체 리스트에서 가장 작은(혹은 큰) 요소를 선택해 정렬하는 방식1번째부터 n번째까지 가장 작은 값을 찾아 1번째 데이터와 swap2번째부터 n번째까지 가장 작은 값을 찾아 2번째 데이터와 s.. [자료구조] 해시맵 개념과 해시 충돌 해시맵(HashMap)이란?키(Key)와 값(value) 쌍을 저장하는 자료구조각 키는 고유(unique)하며, 키를 사용하여 해당 값을 빠르게 검색 가능해싱(Hashing)HashMap의 핵심 원리키(Key)는 해싱 함수(Hashing Function)을 통해 정수값인 해시코드(HashCode)를 변환하고, 변환된 해시 코드는 Hash 배열의 각 요소인 '버킷(Bucket)'의 인덱스가 됨해시맵(HashMap) 예시각 배열의 요소를 버킷이라 함 정리키(key)가 해시 함수에 의해 해시 코드로 변환되고 해당 해시코드는 배열의 각 요소인 버킷의 인덱스 역할해당 버킷을 찾아가면 값을 삽입 및 조회 가능HashMap의 특징키 기반의 빠른 액세스 : 키를 사용하여 값을 빠르게 검색하거나 수정 가능순서를 보장하지.. [자료구조] 이진트리와 이진탐색트리 이진 트리(Binary Tree)란?모든 노드들이 둘 이하(0개, 1개, 2개)의 자식을 가진 트리이진 트리의 형태에 따라 명칭이 달라짐정 이진 트리(Full Binary Tree)각 노드가 0개 혹은 2개의 자식 노드를 가진 트리즉, 모든 노드가 자식을 완전히 가지거나 아예 가지지 않는 구조완전 이진 트리(Complete Binary Tree)마지막 레벨을 제외한 모든 노드가 가득 채워진 트리마지막 레벨의 노드는 전부 채워져 있지 않아도 되지만 노드들이 왼쪽부터 차례대로 채워져야 함이 구조는 힙(Heap) 자료구조의 조건과도 관련 있음포화 이진 트리(Perfect Binary Tree)모든 노드가 2개의 자식을 가지며(정 이진 트리) 모든 리프 노드가 같은 레벨에 위치하는 트리모든 레벨의 노드가 채워져.. [자료구조] Queue 개념 큐(Queue)란?들어온 순서대로 출력되는 First In First Out으로 FIFO(피포) 구조라고 하며 선입선출 형태의 선형 자료 구조입력과 출력이 동일한 스택과 달리 데이터가 입력되는 입구와 데이터가 출력되는 출구 총 2개의 입출구를 가짐큐의 특징선입 선출의 자료 구조기본 연산enqueue : 큐의 끝에 요소 추가dequeue : 큐의 맨 앞의 요소를 제거하고 반환peek : 큐의 맨 앞 요소를 확인하되 제거는 하지 않음큐의 front와 rearfront : 큐의 가장 앞에 있는 데이터 위치rear : 큐의 가장 마지막 위치큐 사용 시 주의 사항오버플로우(Overflow) : 고정된 크기의 큐를 사용할 경우 큐가 가득 찬 상태에 데이터 추가 시 발생언더플로우(Underflow) : 비어 있는 큐.. [자료구조] Stack 개념 스택(Stack)이란?가장 마지막에 삽입된 데이터가 가장 처음으로 출력되기 때문에 Last In First Out으로 LIFO(리포) 구조라고 하며 후입선출 형태의 선형 자료 구조데이터가 삽입되면 가장 안쪽부터 차곡차곡 쌓여, 꺼낼 때는 역순으로 꺼내지게 됨스택의 특징스택의 데이터는 top을 통해서만 접근 가능스택에 데이터를 삽입할 때는 top 위에 데이터를 추가(push)하고, top의 위치를 한칸 위로 변경스택에 데이터를 삭제할 때는 top에 위치한 데이터를 삭제(pop)하고, top의 위치를 한칸 아래로 변경스택 주의 사항스택의 데이터가 꽉 찼을 때 데이터를 삽입(push)하게 되면, 스택 오버플로우(Stack Overflow)가 발생스택이 비어있는 상태일 때 데이터를 삭제(pop)하게 되면, 스택.. [자료구조] 배열(Array) 배열(Array)이란?동일한 자료형을 하나의 묶음으로 저장하는 자료구조배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자를 인덱스(index)배열 선언 & 초기화배열을 선언할 때는 미리 공간의 갯수(길이)를 지정해야 하는데, 이는 가변적인 길이이 아니라 고정적인 길이를 가진다는 것을 의미또한 동일한 자료형을 저장하기 때문에 배열의 타입(int, String, 객체 등)을 지정배열의 시작 위치(index)는 0부터 시작하기 때문에 길이가 5라면, 0~4까지의 인덱스를 가지며 0~4를 벗어나게 되면 배열에서 가장 많이 접하는 에러인 ArrayIndexOutOfBoundsException 발생public static void main(String[] args) {.. 이전 1 2 다음
