Q1) ArrayList와 LinkedList의 차이점은 무엇인가요?A1) ArrayList와 LinkedList는 모두 자바에서 리스트를 구현하는 데 사용하는 클래스입니다. ArrayList는 배열을 이용해 리스트를 구현하므로 인덱스를 기반으로 리스트의 요소에 빠르게 접근할 수 있습니다. 하지만 요소를 추가하거나 삭제하는 경우 배열 크기를 변경해야 해서 시간이 많이 소요됩니다. 반면, LinkedList는 연결 리스트로 구현해서 요소의 삽입과 삭제가 빠릅니다. 하지만 특정 요소에 접근할 때 순차적으로 접근하므로 배열보다 시간이 많이 소요된다는 단점이 있습니다. Q2) 자바에서 추상 클래스와 인터페이스의 차이점은 무엇인가요?A2) 자바의 추상 클래스와 인터페이스는 추상화를 위한 개념입니다. 하지만 추상 ..
분류 전체보기
Q1) 객체 지향 프로그래밍의 특징은 무엇인가요?A1) 객체 지향 프로그래밍은 객체 중심의 프로그래밍으로 상속, 캡슐화, 추상화, 다형성이라는 네 가지 특징이 있습니다. 상속은 기존 클래스를 기반으로 새로운 클래스를 정의하는 것을 의미합니다. 캡슐화는 객체 네부에 직접 접근하지 않고 공개된 인터페이스를 통해서만 객체에 접근해 조작하도록 하는 것입니다. 추상화는 객체의 공통적인 특성을 추출하는 것으로, 변수 또는 메서드를 하나로 묶어 단순화하는 것입니다. 마지막으로 다형성은 동일한 인터페이스에 대해 다른 기능을 제공하는 것을 의미합니다. Q2) 오버라이딩과 오버로딩의 차이점은 무엇인가요?A2) 오버라이딩은 상속받은 부모 클래스의 메서드를 재정의하는 것으로, 자식 클래스에서 부모 클래스에 있는 메서드와 동일..
정렬 알고리즘① 비교 기반 정렬 알고리즘 종류특징평균 시간 복잡도버블 정렬인접한 두 수를 비교해 정렬O(n^2)선택 정렬정렬되지 않은 배열에서 최솟값을 선택해 정렬삽입 정렬정렬된 배열에 탐색 중인 요소 삽입합병 정렬분할 정복 기반 알고리즘, 배열을 1 이하 크기로 분할한 후 합병 과정에서 정렬O(n log n)퀵 정렬분할 정복 기반 알고리즘, 피봇을 선택해 피봇보다 작은 수의 배열과 피봇보다 큰 수의 배열로 분할하며 정렬, 피봇에 따라 시간 복잡도가 달라질 수 있음힙 정렬힙 기반 정렬 알고리즘, 최대 힙을 이용해 오름차순 정렬 & 최소 힙을 이용해 내림차순 정렬② 비교 기반이 아닌 정렬 알고리즘 종류특징기수 정렬낮은 자릿수부터 높은 자릿수까지 정렬자릿수에 올 수 있는 숫자별로 각각 큐를 생성해 각 자릿수..
1. 다익스트라 알고리즘 : 간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘-> 시작 정점을 설정하고, 방문 가능하면서 비용이 가장 적게 드는 정점에 방문해 비용을 갱신, 우선순위 큐를 사용하면 시간 복잡도 면에서 효율적일 수 있음 2. 벨만-포드 알고리즘: 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로, 간선의 가중치가 음수인 경우에도 적용할 수 있음 but 음의 사이클이 있으면 최소 비용이 무한하게 줄어들어서 알고리즘을 적용할 수 없음-> (정점 개수) -1 만큼 모든 간선을 탐색해야 함
최소 신장 트리(MST): 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리 1. 프림 알고리즘: 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성 -> 가중치가 가장 작은 간선으로 연결된 정점을 트리에 추가하면서 최소 신장 트리를 생성 2. 크루스칼 알고리즘: 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성하는 방식 -> 가중치의 오름차순으로 간선을 정렬하는 알고리즘과, 사이클의 생성 여부를 판단하는 union-find 알고리즘을 함께 사용함흩어져 있는 여러 트리(노드)를 가중치가 작은 간선으로 연결해 하나의 최소 신장 트리를 생성
1. 버블 정렬: 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬 -> 배열의 뒤에서부터 정렬됨배열의 n번째 요소를 정렬하기 위해 n(n-1)/2만큼 연산을 수행하며, O(n^2)의 시간 복잡도 소요됨. 정렬 수행이 비교적 느리지만 별도의 메모리 공간이 필요하지 않음 2. 선택 정렬: 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시킴배열의 n번째 요소를 정렬하기 위해 n(n-1)/2만큼 연산을 수행하며, O(n^2)의 시간 복잡도 소요됨. 정렬 수행이 비교적 느리지만 별도의 메모리 공간이 필요하지 않음. 하지만 구현이 비교적 간단함. 3. 삽입 정렬: 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식배열의 n번째 요소를 정렬하기 위해 n(..
1. 선형 자료구조① 데이터가 연속적으로 나열되는 자료구조② 종류- 배열: 정해진 크기만큼의 데이터가 일렬로 저장되는 정적 자료구조- 연결 리스트: 크기가 정해져 있지 않은 동적 자료구조, 노드로 구성됨- 스택: 마지막에 들어온 데이터가 먼저 나가는 구조(LIFO)- 큐: 먼저 들어온 데이터가 먼저 나가는 구조(FIFO)- 덱: 자료구조의 양쪽 끝에서 데이터 추가와 삭제가 모두 가능한 구조 2. 비선형 자료구조① 하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는 자료구조② 그래프, 트리, 우선순위, 큐, 힙, 해시 테이블이 해당함 3. 그래프① 데이터를 포함하는 정점과 정점을 잇는 간선으로 구성② 사이클을 가질 수 있음③ 탐색 방법: BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 4. 트리① 그래..
우선순위 큐: 우선순위가 높은 데이터가 먼저 나오는 자료구조 *우선순위 큐의 구현 방식에 따른 시간 복잡도 (n: 노드 수)구현 방법삽입삭제배열O(1)O(n)연결 리스트O(1)O(n)배열O(n)O(1)연결 리스트O(n)O(1)힙O(log n)O(log n) 힙: 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조- 최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리- 최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리 해시 테이블: 하나의 key에 대해 하나의 value을 저장하는 형태의 자료 구조 -> 평균적으로 O(1)의 시간 복잡도를 갖음해시 충돌: 서로 다른 키에 대해 같은 해시가 도출되는 것 ① 체이닝: 해시 충돌이 발생하면 ..
