알고리즘 스터디 1주차 정리
자료구조의 종류는 많지만 실제 자료구조를 구현하는 기술을 리스트와 Linked 리스트 두 가지가 있다. 리스트와 Linked 리스트를 활용하여 다양한 자료구조가 만들어진다.
- 리스트: 데이터들이 연속적인 공간을 할당 받아 만들어지는 구조
- 배열: 크기가 변하지 않는 리스트형 자료구조, 중간에 값을 지워도 빈칸으로 유지됨
- Array List: 크기가 변하는 자료구조, 중간의 값을 지우면 뒤의 것이 앞으로 이동
- Linked 리스트: 데이터들이 각각 공간을할당 받고 데이터 사이의 연결 고리가 만들어지는 구조
리스트형 자료구조
배열 Array
배열은 메모리의 연속된 공간에 값을 나열시키고 각 값에 인덱스를 부여해놓은 자료구조이다.
구조가 간단하기 때문에 코딩테스트에 가장 많이 사용하는 자료구조 중 하나이다.
배열은 인덱스를 사용하여 값에 바로 접근할 수 있고 선언한 자료형의 값만 저장할 수 있다.
또 배열의 길이는 고정된 값이기 때문에 배열의 길이를 늘리거나 줄일 수 없다.
배열 선언 및 생성 코드는 다음과 같다.
int[] array; //배열의 선언
int[] array = {1, 2, 3, 4, 5}; //값 목록으로 배열 생성
int[] array = new int[5]; //new 연산자로 배열 생성
위의 두 번째, 세 번째 코드 처럼 배열의 크기는 선언할 때 지정할 수 있으며 한 번 선언하며 크기를 늘리거나 줄일 수 없다.
배열의 크기가 생성될 때 고정되기 때문이다.
이는 배열이 메모리 상에 연속된 공간으로 할당된다는, 배열의 물리적인 구조로 인해 발생되는 제한이다.배열의 크기를 변경하려면 새로운 배열을 생성하고 이전 배열에서 데이터를 복사해야한다.
배열은 크기가 정적이기 때문에 크기를 동적으로 조절하기 어렵다고도 표현할 수 있겠다.
또 배열은 크기가 정적이라는 특징 때문에 값을 삽입하거나 삭제하는 과정이 번거롭다.
값을 삽이하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
예를 들어서 1, 2, 3이 저장되어 있는 배열이 있다고 생각해보자.
2를 삭제하고 싶다면 배열에서 2를 삭제한 뒤, 뒤에 있는 데이터 즉 3을 앞으로 가져와주는 작업이 필요하다.
또 만약 2가 있는 자리에 4를 삽입하고 싶다면 기존에 있던 데이터 즉 2와 3을 뒤로 미루고 남은 빈자리에 4를 삽입해야한다.
Array List
Java의 List 컬렉션
자바는 널리 알려져 있는 자료구조를 바탕으로 객체들을 효율적으로 추가, 삭제, 검색할 수 있도록 관련된 인터페이스와 클래스들을 java.util 패키지에 포함시켜 놓았다. 이를 총칭해서 컬렉션 프레임워크라고 부른다.
컬렉션 프레임워크는 몇가지 인터페이스를 통해서 다양한 컬렉션 클래스를 이용할 수 있도록 설계되어잇다. 주요 인터페이스로는 List, Set, Map이 있다.
List와 Set은 객체를 추가, 삭제, 검색하는 방법에 있어서 공통점이 있기 때문에 공통된 메소드만 따로 모아 Collection 인터페이스로 정의해두고 이것을 상속하고 있다.
Java의 List 컬렉션은 동적으로 요소가 추가되거나 제거될 수 있는 순서가 있는 요소들의 집합이다.
List 컬렉션은 객체를 인덱스로 관리하기 때문에 객체를 저장하면 인덱스가 부여되고, 인덱스로 객체를 검색, 추가, 삭제할 수 있는 등의 작업을 할 수 있다.
List는 인터페이스로 정의되어있고 구현체로는 ArrayList, Vector, LinkedList 등이 있다.
가장 큰 특징은 순서를 유지하고 저장한다는 것, 중복 저장이 가능하다는 점이다.
List에서는 메소드를 이용해 데이터 추가, 접근, 수정, 제거 등의 작업을 손쉽게 수행할 수 있다.
다음은 주요 메소드들과 그 역할이다.
- .add(E e): 데이터 추가
- .remove(Object o): 데이터 삭제
- .get(int index): 지정된 인덱스에 해당하는 데이터 반환
- .set(int index, E e): 지정된 인덱스에 해당하는 데이터 변경
- .size(): 저장된 데이터 개수 반환
- .contains(Object o): 지정된 데이터가 포함되어 있는지 확인
Array List
ArrayList는 List 컬렉션에서 가장 많이 사용하는 컬렉션이다.
ArrayList에 객체를 추가하면 내부 배열에 객체가 저장된다. 일반 배열과 차이점은 ArrayList는 길이 제한 없이 객체를 추가할 수 있다는 것이다.
배열을 기반으로 한 동적 배열 구현체라고도 표현할 수 있다.
크기가 동적으로 조절되기에 요소를 추가하거나 제거할 때 크기를 조절하여 배열보다 더 유연하게 관리할 수 있다.
List 컬렉션은 객체 자체를 저장하는 것이 아니라 객체의 번지를 저장한다. 또한 동일한 객체를 중복 저장할 수 있는데 이때는 동일한 번지가 저장되며 null 또한 저장이 가능하다.
ArrayList 생성 코드는 다음과 같다
List<E> list = new ArrayList<E>(); //E에 저장된 타입의 객체만 저장
List<E> list = new ArrayList<>(); //E에 저장된 타입의 객체만 저장
List list = new ArrayList(); //모든 타입의 객체를 저장
ArrayList 컬렉션에 객체를 추가하면 인덱스 0부터 차례대로 저장된다. 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다. 마찬가지로 특정 클래스에 객체를 삽입하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 밀려난다.
다음은 ArrayList 사용하는 예시이다.
public class Board {
private String subject;
private String content;
private String writer;
public Board(String subject, String content, String writer) {
this.subject = subject;
this.content = content;
this.writer = writer;
}
public String getSubject() {
return Subect;
}
public void set Subject(String subect) {
this.subject = subject;
}
public String getCotent() {
return Content;
}
public void setSubject(String Content) {
this.Content = Content;
}
public String getWriter() {
return Writer;
}
public void setWriter(String subect) {
this.writer = writer;
}
}public class ArrayListExample{
public static void main(String[] args) {
// ArrayList 컬렉션 생성
List<Board> list = new ArrayList<>();
// ArrayList 컬렉션에 객체 추가
list.add(new Board("제목1", "내용1", "글쓴이1"));
list.add(new Board("제목2", "내용2", "글쓴이2"));
list.add(new Board("제목3", "내용3", "글쓴이3"));
list.add(new Board("제목4", "내용4", "글쓴이4"));
list.add(new Board("제목5", "내용5", "글쓴이5"));
//저장된 총 객체 수 얻기
int size = list size();
System.out.println("총 객체 수: " + size);
System.out.println();
//특정 인덱스의 객체 가져오기
Board board = list.get(2);
System.out.println(board.getSubject + "\t" + board.getContent + "\t" + board.getWriter()};
System.out.println();
// ArrayList에 저장된 모든 객체를 하나씩 가져오기
for(int i = 0; i < list.size(); i++) {
Board b = list.get(i);
System.out.println(board.getSubject + "\t" + board.getContent + "\t" + board.getWriter()};
}
System.out.println();
//객체 삭제
//2번 인덱스를 삭제하면 3번 인덱스가 2번 인덱스로 변경됨
list.remove(2);
//다시 2번 인덱스를 삭제할 수 있음
list.remove(2);
//for-each문 형태로 저장된 모든 객체 하나씩 가져오기
for(Board board : list) {
System.out.println(board.getSubject() + "\t" + board.getContent() + "\t" + board.getWriter());
}
System.out.println();
문제에서 데이터의 크기가 정해져있다면 배열을 사용하는 것이 좋다.
또 데이터가 접근하는 경우가 많은 경우에는 인덱스를 사용하는 배열이나 ArrayList와 같은 리스트형 자료구조를 사용하는 것이 좋다.
ArrayList는 인덱스를 통해 요소에 접근하기 때문에 그 속도가 매우 빠르지만, 목록의 중간에 데이터를 추가하거나 삭제하는 경우에는 배열의 크기를 조정하고 요소를 이동시켜야하기 때문에 상대적으로 느릴 수 있다.
따라서 앞 뒤가 아닌 중간 위치에 자주 요소를 추가하거나 삭제해야하는 경우에는 LinkedList를 사용하는 것이 좋다.(크기가 변하는 데이터를 다룰 때 Linked List를 사용하는 것이 좋다.
Linked List(연결 리스트) 자료구조
연결 리스트 즉 Linked List 자료구조는 저장하는 각 데이터(기본 데이터, 배열, 구조체, 클래스)가 데이터 외에 다음과 이전의 데이터를 가리키는 정보를 가지고 있는 구조이다.
리스트는 값과 포인터를 묶은 노드라는 것으로 포인터를 연결한 자료구조이다.
자기자신의 값을 가지고 있고 다음 노드가 어떤 노드인지를 가리키는 포인터를 가지고 있다. 즉 저장된 각 데이터가 (데이터) + (다음 데이터의 포인터)인 것이다.
노드는 컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 부르는 단위다.
Linked List 생성코드는 다음과 같다.
List<E> list = new LinkedList<E>(); //E에 지정된 타입의 객체만 저장
List<E> list = new LinkedList<>(); //E에 지정된 타입의 객체만 저장
Listlist = new LinkedList(); //모든 타입의 객체를 저장
결국 Linked List는 삽입과 삭제를 할 때, 전체 데이터의 변동은 없고, 앞, 뒤의 연관된 데이터만 변동하면 된다.
그래서 Linked list는 중간에 데이터를 삽입하거나 지우는 과정을 빠르게 수행할 수 있다.
예를 들어 40과 50이라는 데이터가 포인터로 연결되어 있었다. 여기서 30이라는 데이터를 40과 50 사이에 넣고 싶다면 40이 가르키는 포인터의 위치(50)를 30으로 변경하고 30에 있는 포인터를 50으로 옮겨주면 된다.
반대로 30의 값의 삭제하려면 40이 30을 가리키고 있던 포인터를 다시 50을 가르키도록 변경하면 된다.
데이터의 위치를 이동해야만 했던 배열과 다르게 포인터만 변경해주면 되기 때문에 삽입, 삭제하는 연산 속도는 빠를 수 밖에 없다.
하지만 특정 데이터를 찾는 것은 포인터를 따라 이동해야하므로 성능이 떨어진다.(이럴 때는 배열이나, ArrayList는 사용하는게 좋다.)
Linked List는 인덱스가 없기 때문에 특정한 값에 접근하려면 Head 포인터부터 순서대로 접근해야한다.
인덱스를 사용하는 배열이나 ArrayList보다 속도가 느릴 수 밖에 없다.
데이터의 변화가 많은 상황이라면 Linked List를 사용하는 것이 효율적일 것이다.
선언할 때 크기를 별도로 지정하지 않아도 된다. 리스트의 크기는 정해져있지 않으며 크기가 변하기 쉬운 데이러를 다룰 때 적절하다.
다만 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다는 특징이 있다.
다음은 Linked List를 사용하는 예시이다.
ArrayList와 LinkedList에 10000개의 객체를 저장하는데 걸린 시간을 측정한 것.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class LinkedListExample {
public static void main(String[] args) {
//ArrayList 컬렉션 생성
List<String> list1 = new ArrayList<String>();
List<String> list2 = new LinkedList<String>();
//시작시간과 끝 시간을 저장할 변수 선언
long startTime;
long endTime;
//ArrayList 컬렉션에 저장하는 시간 측정
startTime = System.nanoTime();
for(int i = 0; i < 10000; i++) {
list1.add(0, String.valueOf(i));
}
endTime = System.nanoTime();
System.out.printf("%-17s %8d ns \n", "ArrayList 걸린 시간: ", (endTime - startTime));
//LinkedList 컬렉션에 저장하는 시간 측정
startTime = System.nanoTime();
for(int i = 0; i < 10000; i++) {
list2.add(0, String.valueOf(i));
}
endTime = System.nanoTime();
System.out.printf("%-17s %8d ns \n", "LinkedList 걸린 시간: ", (endTime - startTime));
}
}'Algorithm' 카테고리의 다른 글
| [Panda] 3. 스택과 큐 (0) | 2024.05.07 |
|---|---|
| [Panda] 2. 구간 합(Prefix Sum)과 투 포인터 알고리즘 (1) | 2024.05.06 |
| [백준] 1546번 평균 구하기 (0) | 2024.05.06 |
| [백준] 11720번 숫자의 합 (0) | 2024.05.06 |
| [Panda] 0. 알고리즘과 자료구조 (0) | 2024.05.02 |