본문 바로가기

전체 글69

[Java] - ArrayList 기본 사용법 ArrayList란?ArrayList란 자바의 컬렉션 프레임워크에서 가장 많이 사용되는 클래스 중 하나이다. List 인터페이스를 구현한 클래스로서, 데이터의 순서가 고려되며, 중복이 가능하다.  자바에서 일반적인 배열을 선언할 때 int[] arr = {1, 2, 3}; 과 같이 선언하는데, 이 경우 코드는 간결하지만, 정적으로 메모리를 할당했기 때문에 배열의 크기가 고정되어 있다. 하지만 ArrayList는 동적으로 메모리를 할당한 배열로, 데이터를 추가하거나 삭제할 때마다 내부에서 배열의 크기를 조절한다. 일반 배열과 마찬가지로 인덱스를 통하여 데이터에 접근이 가능하다. 1. 헤더파일import java.util.ArrayList;ArrayList를 선언하기 위해서는 java.util.ArrayLi.. 2024. 7. 10.
[Java] - 컬렉션(Collection) 이란? 1. 컬렉션 프레임워크(Collection Framework) 란?여러 데이터들을 효율적으로 다루기 위한 자료구조들을 클래스로 구현해놓은 집합을 말한다. C++의 STL (Standard Template Library)와 비슷한 개념이라고 보면 된다.  컬렉션의 장점을 배열로 예시를 들어보자면,일반적인 배열은 정적으로 메모리를 할당하기 때문에, 배열의 크기가 고정되어 추가적인 공간이 필요할 경우 문제가 발생할 수 있다. 하지만 컬렉션의 클래스를 이용하면 메모리를 동적으로 할당할 수 있다. List와 Set 인터페이스는 Collection 인터페이스를 상속받는 반면 Map 인터페이스는 구조상의 차이 (key와 value의 쌍을 가지고 있는 구조)로 별도로 정의된다.2. 컬렉션의 종류위 그림에서 볼 수 있듯.. 2024. 7. 4.
[알고리즘] - 쉘 정렬 (Shell-sort) 1. 쉘 정렬(Shell-Sort)이란? 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다. → 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다. → 쉘 정렬은 삽입 정렬을 보완한 방법! 쉘 정렬의 시간 복잡도는 아직까지도 정확하게.. 2024. 4. 14.
[알고리즘] - 삽입 정렬 (Insertion-sort) 1. 삽입 정렬(Insertion Sort)이란? 선택한 원소를 현재 정렬된 배열 범위 내의 적절한 위치에 삽입하는 방법이다. 구현하기 쉬운 알고리즘이지만, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 삽입 정렬의 수행 방식 삽입 정렬 과정 ① 현재 index의 원소를 선택한다. ② 정렬된 부분 내에서, 현재 선택한 원소가 들어갈 적절한 삽입 위치를 찾는다. ③ 삽입 위치부터 끝까지 데이터를 한 칸씩 뒤로 민다. ④ 삽입 위치에 현재 선택한 원소를 삽입한다. ⑤ index를 1 증가시키고, 다시 ①부터 반복한다. (index가 배열의 크기만큼 커질때까지 반복) 다시 말해, 인덱스를 증가시켜 가면서 배열의 원소를 선택하고, 선택한 원소를 정렬된 범위 내의 적절한 위.. 2024. 4. 9.
[알고리즘] - 선택 정렬 (Selection Sort) 1. 선택 정렬(Selection Sort)이란? 정렬되지 않은 데이터 중에서 최솟값을 찾아 맨 앞 원소와 위치를 교환시키는 방법 제자리 알고리즘 (in-place algorithm) 에 해당한다. 제자리 알고리즘 (in-place algorithm)이란? 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법을 말한다. 알고리즘은 간단하나, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 선택 정렬의 수행 방식 선택 정렬 과정 ① 정렬할 범위 안에서 최솟값을 찾는다. (내림차순인 경우 최댓값을 찾으면 된다.) ② 정렬할 부분 중 가장 앞에 있는 데이터와, ①에서 구한 데이터를 swap한다. ③ 정렬할 범위는 1 감소한다. → (맨 앞 데.. 2024. 4. 9.
[알고리즘] - 버블 정렬 (bubble sort) 1. 버블 정렬(bubble sort)이란? 인접한 데이터끼리 비교, swap 연산을 수행하여 정렬하는 방법 버블 정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 알고리즘은 간단하나, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 버블 정렬의 수행 방식 버블 정렬의 수행 과정 ① 정렬할 범위의 앞부분부터 인접한 두 원소의 값을 비교한다. ② 앞 원소가 더 크다면 swap한다. / 뒤 원소가 더 크다면 continue ③ 정렬할 범위의 끝부분까지 반복한다. => 반복이 끝나면 정렬할 범위는 1 감소, 정렬된 범위는 1 증가한다. ④ 새로운 정렬할 범위를 얻었다. 다시 ①부터 반복한다. 3. 버블 정렬 구현 (C++) #include using name.. 2024. 2. 13.

티스토리툴바