1Page 노트정리 연결리스트
1 Page 노트 정리
Linked List: 개념과 시간 복잡도
개념
Linked List는 데이터 요소들이 연속적으로 저장되지 않고, 각각의 요소가 다음 요소의 주소를 가지고 있는 자료구조입니다. Linked List의 주요 특징은 다음과 같습니다:
- 노드(Node): Linked List의 기본 단위로, 데이터와 다음 노드에 대한 참조(링크)를 포함합니다.
- Head: Linked List의 시작 노드를 가리킵니다.
- Tail: Linked List의 끝 노드를 가리키며, 마지막 노드는 null을 참조합니다.
Linked List의 종류
- 단방향 연결 리스트 (Singly Linked List):
- 각 노드는 다음 노드에 대한 참조를 가집니다.
- 앞에서 뒤로 순차적으로 접근할 수 있지만, 뒤에서 앞으로의 접근은 불가능합니다.
- 양방향 연결 리스트 (Doubly Linked List):
- 각 노드는 다음 노드와 이전 노드에 대한 참조를 가집니다.
- 양방향으로 접근이 가능하여 삽입과 삭제가 더 용이합니다.
- 양방향 원형 연결 리스트 (Doubly Circular Linked List):
- 마지막 노드가 첫 노드를 참조하여 원형 구조를 형성합니다.
- 첫 노드의 이전은 마지막 노드, 마지막 노드의 다음은 첫 노드가 됩니다.
Linked List의 시간 복잡도
Linked List의 주요 연산에 대한 시간 복잡도는 다음과 같습니다:
- 삽입 (Insertion):
- 앞에 삽입 (addFirst): O(1)
- 뒤에 삽입 (addLast): O(1)
- 중간에 삽입: O(n) (특정 위치를 찾는 데 O(n), 삽입 자체는 O(1))
- 삭제 (Deletion):
- 앞에서 삭제 (removeFirst): O(1)
- 뒤에서 삭제 (removeLast): O(1)
- 중간에서 삭제: O(n) (특정 위치를 찾는 데 O(n), 삭제 자체는 O(1))
- 탐색 (Search):
- 인덱스 접근 (get): O(n) (특정 위치를 찾기 위해 순차적으로 접근)
- 값 탐색 (contains, indexOf): O(n) (특정 값을 찾기 위해 순차적으로 접근)
- 크기 확인 (size): O(1) (단, 크기를 저장하는 변수를 유지하는 경우)
Linked List의 사용 예시
import java.util.LinkedList;
import java.util.Arrays;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1); // 데이터 1을 추가
list.addFirst(2); // 데이터 2를 맨 앞에 추가
System.out.println(list); // [2, 1] 출력
list.add(1, 3); // 1번 인덱스에 데이터 3 추가
System.out.println(list); // [2, 3, 1] 출력
System.out.println(list.get(0)); // 0번 인덱스의 데이터 출력 (2)
list.addLast(5); // 데이터 5를 맨 뒤에 추가
System.out.println(list); // [2, 3, 1, 5] 출력
list.removeFirst(); // 가장 첫번째 인덱스 삭제
list.removeLast(); // 가장 마지막 인덱스 삭제
list.remove(0); // 0번 인덱스의 데이터 삭제
System.out.println(list); // [1] 출력
System.out.println(list.size()); // 리스트 크기 출력 (1)
System.out.println(list.indexOf(1)); // 데이터 1의 인덱스 출력 (0)
System.out.println(list.contains(3)); // false
System.out.println(list.contains(1)); // true
System.out.println(list.isEmpty()); // false
list.set(0, 10); // 0번 인덱스의 데이터를 10으로 변경
System.out.println(list); // [10] 출력
Object[] arr = list.toArray(); // LinkedList의 데이터를 배열에 저장
System.out.println(arr[0]); // 배열의 0번 인덱스 출력 (10)
System.out.println(Arrays.toString(arr)); // [10] 출력
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
LinkedList는 삽입과 삭제가 빈번하게 일어나는 상황에서 유용하게 사용할 수 있는 자료구조입니다.
연결 리스트 (Linked List), 이중 연결 리스트 (Doubly Linked List), 원형 연결 리스트 (Circular Linked List)
개념 정리
연결 리스트 (Linked List)
각 노드가 데이터와 다음 노드의 주소를 저장하는 구조입니다.
이중 연결 리스트 (Doubly Linked List)
각 노드가 데이터, 이전 노드의 주소, 다음 노드의 주소를 저장하는 구조입니다.
원형 연결 리스트 (Circular Linked List)
마지막 노드가 null을 가리키는 대신 처음 노드를 가리키는 구조입니다.
시간 복잡도
| 연산 | 단순 연결 리스트 (Singly Linked List) | 이중 연결 리스트 (Doubly Linked List) | 원형 연결 리스트 (Circular Linked List) |
|---|---|---|---|
| 삽입 | O(1) 앞, O(n) 중간 및 뒤 | O(1) 앞 및 뒤, O(n) 중간 | O(1) 앞 및 뒤, O(n) 중간 |
| 삭제 | O(1) 앞, O(n) 중간 및 뒤 | O(1) 앞 및 뒤, O(n) 중간 | O(1) 앞 및 뒤, O(n) 중간 |
| 탐색 | O(n) | O(n) | O(n) |
| 인덱스 접근 | O(n) | O(n) | O(n) |
| 크기 확인 | O(1) | O(1) | O(1) |
구조 및 장단점
연결 리스트 (Singly Linked List)
- 구조: 각 노드는 데이터와 다음 노드의 주소를 저장.
- 장점: 단순 구조, 메모리 효율적.
- 단점: 단방향 탐색만 가능, 특정 요소 접근 시 탐색 시간 증가.
이중 연결 리스트 (Doubly Linked List)
- 구조: 각 노드는 데이터, 이전 노드의 주소, 다음 노드의 주소를 저장.
- 장점: 양방향 탐색 가능, 노드 삽입 및 삭제 용이.
- 단점: 더 많은 메모리 사용, 구현 복잡성 증가.
원형 연결 리스트 (Circular Linked List)
- 구조: 마지막 노드가 처음 노드를 가리키는 구조.
- 장점: 연속적인 순회 가능, 단일 포인터로 머리와 꼬리 노드 추가 가능.
- 단점: 구현 복잡성 증가.
요세푸스 문제
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
이제 순서대로 K번째 사람을 제거한다.
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3
예제 출력 1
<3, 6, 2, 7, 5, 1, 4>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.IntStream;
public class BJ1158 {
public static ArrayList getJosephusPermutation(int N, int K) {
Queue queue = new LinkedList();
ArrayList result = new ArrayList();
IntStream.range(1, N + 1).forEach(x -> queue.add(x));
int cnt = 0;
while (!queue.isEmpty()) {
int data = (int)queue.remove();
cnt += 1;
if (cnt % K == 0) {
result.add(data);
} else {
queue.add(data);
}
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int n = Integer.parseInt(stringTokenizer.nextToken());
int k = Integer.parseInt(stringTokenizer.nextToken());
// Test code
ArrayList<Integer> result = getJosephusPermutation(n, k);
// 결과를 원하는 형식으로 출력하기
StringBuilder sb = new StringBuilder();
sb.append("<");
for (int i = 0; i < result.size(); i++) {
sb.append(result.get(i));
if (i < result.size() - 1) {
sb.append(", ");
}
}
sb.append(">");
System.out.println(sb.toString());
}
}
7 3
<3, 6, 2, 7, 5, 1, 4>
출처 : 백준, https://www.acmicpc.net/problem/1158
문제 설명 운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
- 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
- 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
- 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다. 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- priorities의 길이는 1 이상 100 이하입니다.
- priorities의 원소는 1 이상 9 이하의 정수입니다.
- priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
- location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
- priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.
입출력 예
| priorities | location | return |
|---|---|---|
| [2, 1, 3, 2] | 2 | 1 |
| [1, 1, 9, 1, 1, 1] | 0 | 5 |
입출력 예 설명 예제 #1
- 문제에 나온 예와 같습니다.
예제 #2
- 6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
LinkedList<Integer> ll = new LinkedList<>();
// LinkedLis로 priorities 넣기
for(int n: priorities){
ll.add(n);
}
// ll 순회
while(!ll.isEmpty()){
// max 값 찾기
int max = 0;
for(Integer n : ll){
if (n > max){
max = n;
}
}
// 0번 인덱스 조회
// 0번 인덱스 값이 max인경우,
if(ll.peek() == max){
ll.poll();
answer++;
// location이 0인 경우, 종료
// 아닌 경우, poll로 인한 재배열
// location--
if(location == 0){
break;
}else{
location--;
}
}
// 0번 인덱스 값이 max가 아닌 경우,
else{
// 맨 앞의 요소를 뒤로 보냄
ll.add(ll.poll());
// location이 0인경우,
// 다시 뒤부터 시작
// 아닌 경우, 앞으로 당김
if(location == 0){
location = ll.size()-1;
}else{
location--;
}
}
}
return answer;
}
}
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42587
Leave a comment