728x90 넓고 얕은 자료구조 & 알고리즘/자료구조론12 자바로 공부하는 배열과 리스트 📌 배열(Array) 동일한 데이터 타입의 요소들을 순차적으로 저장하는 자료구조이다. 배열은 고정된 크기를 가지고 있다. 인덱스를 사용하여 요소에 접근할 수 있다. 자바에서는 배열을 선언할 때 크기를 지정하거나, 동적으로 크기를 조정할 수 없다. 요소를 추가하거나 삭제하기 위해서는 새로운 배열을 생성하고 기존의 요소를 복사해야 한다. 배열은 메모리 상에 연속적으로 할당되므로 인덱스를 통한 접근이 매우 빠르다. 또한 크기가 고정되어 있기 때문에 요소의 위치를 바로 계산하여 접근할 수 있다. ⌨️ 자바에서의 Array public static void main(String[] args) { String[] strArr = new String[5]; // 초기 배열 크기 5로 설정, 설정하지 않으면 에러 발생.. 2023. 10. 30. 스택(stack) & 큐(Queue) 1분 요약 정리 스택(stack) 삽입과 삭제가 한 쪽 끝에서만 이루어지는 데이터 구조이다. 가장 먼저 들어간 데이터가 가장 마지막에 나오는 후입 선출(LIFO, Last In First Out) 방식이다. 삽입/삭제의 복잡도는 O(1)이다. 활용 재귀 알고리즘을 사용할 때 유용하다. 재귀적으로 함수를 호출 할 때, 데이터를 스택에 넣었다가, 재귀 함수를 빠져나올 때 스택에 넣어둔 데이터를 빼는 방식을 사용할 수 있기 때문이다. 웹 브라우저 방문 기록 실행 취소 큐(Queue) 한 쪽에서는 삽입이, 다른 한 쪽에서는 삭제가 이루어진다. 가장 먼저 들어간 데이터가 가장 먼저 삭제되는 선입선출(FIFO, First In First Out) 방식이다. 삽입 연산(enQueue)이 이루어지는 곳을 리어(rear), 삭제 연산(.. 2023. 3. 4. 자료구조의 경계 조건 경계 조건(Boundary Conditions) 어떤 자료 구조든 경계 조건에서 문제가 생기지 않을지 고려해서 설계해야한다. 자료 구조가 비어있는 경우 자료 구조에 단 하나의 요소만 들어있는 경우 자료 구조의 첫번째 요소를 제거하거나 추가하는 경우 자료 구조의 마지막 요소를 제거하거나 추가하는 경우 자료 구조의 중간 부분을 처리하는 경우 출처 : 네이버 부스트 코스 - 자바로 구현하고 배우는 자료구조 2023. 2. 22. 시간복잡도(Time Complexity) 1분 요약 정리 코드를 짤 때 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마나 걸리는가를 계산하여 가장 효율적인 알고리즘을 만드는 것을 말한다. 항상 입력값으로 0 이상의 수를 입력받는다. 음의 입력값은 시간복잡도를 고려할 때 말이 되지 않는다. 따라서 시간복잡도는 항상 0보다 크다고 가정한다. 함수는 더 많은 입력값이 있을 때 더 많은 작업을 필요로 한다. 시간 복잡도에서는 모든 상수를 삭제한다. ex) 3n, 5n, 50n 복잡도란 존재하지 않는다. 오로지 n만이 존재한다. 알고리즘에서 1보다 작은 지점은 고려하지 않는다. n이 아주 클 때의 경우를 고려한다. 다양한 차수 항을 가지고 있는 함수가 있을 때 낮은 차수의 항과 상수는 고려하지 않는다. 오직 제일 큰 차수의 항만이 알고리즘의 시간 복잡도에 .. 2023. 2. 6. 검색 알고리즘(Search Algorithm) 검색 알고리즘에 대하여 데이터를 검색만 한다면 계산 시간이 가장 짧은 것을 선택하는 것이 좋다. 그러나 검색뿐만 아니라 데이터를 추가하거나 삭제하는 작업까지 수행해야 한다면 검색 이외의 작업에 소용되는 비용까지 종합적으로 고려하여 알고리즘을 선택해야 한다. 고려 대상에는 목적, 용도, 실행 속도, 자료 구조 등이 있다. 데이터 추가 비용이 많이 든다는 의미 배열 데이터의 중간에 새로운 데이터를 삽입하는 경우, 새로운 데이터가 들어가는 자리 이후의 데이터는 전부 한 칸씩 밀어내야 하는데 이 경우 데이터의 추가 비용이 많이 들게 된다. 선형 검색(linear search), 순차 검색(sequential search) 요소가 직선 모양을 늘어서 있어 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로.. 2022. 9. 27. 완전 탐색 알고리즘(Brutal-Force Algorithm) 완전 탐색 알고리즘(Brutal-Force Algorithm) 무차별적으로 대입하는 방법을 나타내는 알고리즘이다. 즉 모든 가능성을 시도하여 문제를 해결한다. 따라서 데이터 크기가 커질수록 비효율적이다. 완전 탐색 알고리즘을 사용하는 경우 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 완전 탐색 알고리즘의 한계 문제의 복잡도에 매우 민감하다. 문제가 복잡해질수록 기하급수적으로 많은 자원(시간, 컴퓨팅 자원)을 필요로 하게 된다. 완전 탐색 알고리즘을 활용하는 알고리즘 순차 검색 알고리즘(Sequential Search) 문열 매칭 알고리즘(Brutal-Force String Matching) 선택 정렬 알고리즘 버블 정.. 2022. 9. 27. 탐욕 알고리즘(Greedy) 탐욕 알고리즘(Greedy) 선택의 순간에 당장 눈앞에 보이는 최적의 상황을 선택하여 최종 해답에 도달하는 방법이다. 탐욕 알고리즘이 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 탐욕 알고리즘의 단계 선택 절차(Selection Procedure) : 현재 상태에서 최적의 해답을 선택한다. 적절성 검사(Feasiblility Check) : 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 반복 탐욕 알고리즘의 조건 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적.. 2022. 9. 27. 선형 리스트(Linear List)와 연결 리스트(Linked List) 선형 리스트(linear list) 데이터가 배열처럼 연속하는 공간에 저장되어 순서를 갖는다. 연결 리스트(linked list) 각각의 데이터 안에 다음 데이터에 대한 정보가 저장되어 있어 서로 연결된다. 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애는 방식으로 구현한다. Linked List의 구조 배열 연속된 메모리 주소값 안에 데이터를 넣는 구조로 위치를 바꾸려면 데이터가 전체적으로 이동해야 한다. 연결 리스트 흩어져 있는 공간에 노드들의 연결로 이루어져 있다. 각 노드는 다음 노드를 가리키며, 연속된 메모리 주소가 아니기 때문에 직접 주소 값을 가지도 있어야 다음 노드로 접근이 가능하다. 마지막 노드는 새 노드가 추가되기 전까지 null을 가리킨다. 연결 리스.. 2022. 9. 27. 이전 1 2 다음 728x90
