목록개발지식/자료구조 (3)

마이의 개발 블로그

[자료구조] 우선순위 큐 (priority queue) - 백준 1715번

배경 백준 1715번: 카드 정렬하기(그리디 알고리즘) 문제를 ArrayList로 풀다가 시간 초과가 뜨길래 문제를 해결하던 중 우선순위 큐를 적용해야만 한다는 걸 알게되었다. 처음에는 List 클래스의 sort() 메서드 사용 시 오름차순 정렬을 했기 때문에 연산이 완료된 값을 삭제할 때 배열이 전체 이동되어 시간이 많이 소요되는 거라고 생각했다. 그래서 내림차순 정렬로 바꾸고, ArrayList의 끝부분에서 삽입 삭제 시에 배열의 전체 복사나 이동이 없게끔 코드를 변경했는데, 여전히 시간초과가 뜨길래 결국 다른 사람들의 풀이를 검색할 수 밖에 없었다. //ArrayList를 사용한 예시 - 시간초과 while(list.size() > 1) { list.sort(Comparator.reverseOrde..
개발지식/자료구조 2022. 2. 5. 21:58
[자료구조] ArrayList와 LinkedList 비교 (자바 컬렉션 프레임워크)

배경 - 자바 컬렉션 프레임워크의 컬렉션데이터 그룹 3가지 : List, Set, Map - List 인터페이스 구현 클래스 4가지: ArrayList, LinkedList, Stack, Vector - 여기서 대표적으로 많이 사용되는 ArrayList와 LinkedList를 비교하고자 함 List 인터페이스 공통점 - 값의 중복을 허용하며 저장순서가 유지된다는 공통점이 있음 ArrayList - 기존 Vector 클래스를 개선한 클래스로, 구현원리와 기능은 동일하나 가급적 ArrayList를 사용하는 것이 좋음 - Object 타입으로 선언되어 모든 종류의 객체가 사용가능함 - 이름에서도 알 수 있듯 배열과 유사한 구조를 가지며, 내용 추가/삭제/정렬 등의 메서드를 제공함 - 데이터의 추가와 읽기에는 ..
개발지식/자료구조 2022. 2. 3. 23:53
[자료구조] 배열(array)과 리스트(list)

배열 (array) - 다수의 데이터를 하나의 이름으로 묶어 관리하기 위한 자료구조로 인덱스와 값으로 구성됨 - 인덱스를 통해 데이터에 접근함 (random access 가능) - 논리적 저장 순서와 물리적 저장 순서가 일치함 (연속적 메모리 공간 차지) - 정적 할당으로 크기 변경이 불가능함 (삽입, 삭제시에도 빈 공간은 유지됨) 리스트 (list) - 메모리 공간 활용이 제한적인 배열의 단점을 극복하기 위해 만들어진 자료구조 - 포인터를 통해 데이터에 접근함 (포인터를 위한 추가 메모리 공간 필요) - 논리적 저장 순서와 물리적 저장순서가 다름 (불연속적 메모리 공간 차지) - 동적 할당으로 크기가 가변적임 (삽입, 삭제시 메모리 재할당) 배열과 리스트 비교 (속도 기준) 작업 탐색 삽입 및 삭제 속..
개발지식/자료구조 2022. 1. 26. 21:23
이전 Prev 1 Next 다음