The Array Class - 이전과 연결된다.
검색
- 배열에서 검색할 때는 배열이 정렬되어 있는지 여부에 따라 적절한 메서드를 선택해야 함.
- 정렬되지 않은 배열에서 검색할 때는 전체 배열을 순회해야 하므로 성능이 떨어짐.
- 검색 메서드들은 요소를 찾지 못한 경우 예외를 발생시키지 않고 -1이나 기본값을 반환함.
이진 검색 - 좋은거
- BinarySearch 메서드는 정렬된 배열에서 빠른 검색 수행
- 요소가 비교 가능해야 함(IComparable 구현)
- 사용자 정의 비교자(IComparer) 사용 가능
선형 검색 - 안좋은거
- IndexOf/LastIndexOf: 정렬되지 않은 배열에서 특정 항목 검색
- 즉, 하나씩 순차적으로 찾는것이다.
- BinarySearch보다 안좋다.
- Find/FindLast/FindIndex/FindLastIndex/FindAll/Exists/TrueForAll: 조건자(Predicate)를 사용한 검색
string[] names = { "Rodney", "Jack", "Jill" };
// 람다식으로 "a"를 포함하는 이름 찾기
string match = Array.Find(names, n => n.Contains("a")); // "Jack" 반환
정렬
Sort 메서드
// 단일 배열 정렬
public static void Sort<T>(T[] array);
public static void Sort(Array array);
// 쌍으로 된 배열 정렬
public static void Sort<TKey,TValue>(TKey[] keys, TValue[] items);
public static void Sort(Array keys, Array items);
정렬 예시
// 단순 정렬
int[] numbers = { 3, 2, 1 };
Array.Sort(numbers); // 배열이 { 1, 2, 3 }이 됨
// 연관 배열 정렬
int[] numbers = { 3, 2, 1 };
string[] words = { "three", "two", "one" };
Array.Sort(numbers, words);
// numbers는 { 1, 2, 3 }
// words는 { "one", "two", "three" }
// 사용자 정의 정렬
int[] numbers = { 1, 2, 3, 4, 5 };
// 홀수가 먼저 오도록 정렬
Array.Sort(numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1);
// numbers는 { 1, 3, 5, 2, 4 }가 됨
요소 반전
- Reverse 메서드로 배열의 요소 순서를 반전할 수 있음
- 전체 배열 또는 지정한 범위의 요소만 반전 가능함
public static void Reverse(Array array);
public static void Reverse(Array array, int index, int length);
// 사용 예제
string[] words = { "one", "two", "three", "four" };
Array.Reverse(words);
Console.WriteLine(string.Join(", ", words)); // "four, three, two, one"
// 부분 범위만 반전
Array.Reverse(words, 1, 2); // 인덱스 1부터 2개 요소만 반전
Console.WriteLine(string.Join(", ", words)); // "four, two, three, one"
복사 메서드
- Clone: 새로운 배열로 얕은 복사를 수행함. 참조 형식의 경우 참조만 복사됨
- CopyTo: 연속된 부분 배열을 복사함. 대상 배열이 이미 존재해야 함
- Copy: CopyTo의 정적 메서드 버전으로, 소스와 대상 배열 모두를 매개변수로 받음
- ConstrainedCopy: 원자적 작업으로 복사를 수행함. 복사 중 실패하면 전체 작업이 롤백됨
- AsReadOnly: 읽기 전용 래퍼를 반환하여 요소 재할당을 방지함
// CopyTo 예제
int[] source = { 1, 2, 3, 4 };
int[] target = new int[6]; // { 0, 0, 0, 0, 0, 0 }
source.CopyTo(target, 1); // target: { 0, 1, 2, 3, 4, 0 }
// ConstrainedCopy 예제 - 타입 불일치로 인한 실패 시 롤백
object[] source2 = { 1, "two", 3 };
int[] target2 = new int[3];
try
{
Array.ConstrainedCopy(source2, 0, target2, 0, 3); // 예외 발생
}
catch
{
// target2 배열이 변경되지 않은 상태로 유지됨
}
// AsReadOnly 예제
int[] numbers = { 1, 2, 3 };
var readOnly = Array.AsReadOnly(numbers);
Console.WriteLine(readOnly[0]); // 읽기 가능
// readOnly[0] = 10; // 컴파일 에러: 쓰기 불가능
// 원본 배열은 여전히 수정 가능
numbers[0] = 10;
Console.WriteLine(readOnly[0]); // 10 출력 - 변경이 읽기 전용 뷰에도 반영됨
변환과 크기 조정
- ConvertAll: 새로운 형식의 배열로 변환하여 반환함
- Resize: 배열 크기를 조정함 (새 배열을 생성하여 참조를 변경)
// ConvertAll 예제
float[] reals = { 1.3f, 1.5f, 1.8f };
int[] wholes = Array.ConvertAll(reals, r => Convert.ToInt32(r));
// wholes 배열은 { 1, 2, 2 }
// Resize 예제
int[] numbers = { 1, 2, 3 };
Array.Resize(ref numbers, 5); // numbers는 이제 { 1, 2, 3, 0, 0 }
Array.Resize(ref numbers, 2); // numbers는 이제 { 1, 2 }
변환과 크기 조정
- ConvertAll: 새로운 형식의 배열로 변환하여 반환
- Resize: 배열 크기 조정 (새 배열 생성)
// 실수 배열을 정수 배열로 변환
float[] reals = { 1.3f, 1.5f, 1.8f };
int[] wholes = Array.ConvertAll(reals, r => Convert.ToInt32(r));
// wholes 배열은 { 1, 2, 2 }
Lists, Queues, Stacks, 그리고 Sets
컬렉션 개요
- Set : 이진 탐색을 구현한 컬렉션
- UnOrderedSet : 해쉬테이블을 구현한 컬렉션
컬렉션의 종류
- List<T>: 크기가 동적으로 조정되는 배열임
- LinkedList<T>: 이중 연결 리스트로, 삽입/삭제가 빈번할 때 유용함
- Queue<T>: 선입선출(FIFO) 자료구조임
- Stack<T>: 후입선출(LIFO) 자료구조임
- HashSet<T>: 중복을 허용하지 않는 해시 기반 컬렉션임
- SortedSet<T>: 정렬된 상태를 유지하는 중복 불허 컬렉션임
- BitArray: bool 값을 비트 단위로 압축 저장하는 컬렉션임
List<T>와 ArrayList
성능 특성
- 요소 접근: O(1) - 인덱스를 통한 직접 접근이 가능함
- 끝에 추가: O(1) - 대부분의 경우 빠름, 용량 확장이 필요할 때만 느려짐
- 중간 삽입/삭제: O(n) - 요소들을 이동해야 하므로 느림
- 검색: O(n) - 정렬되지 않은 상태에서는 선형 검색이 필요함
- 정렬된 상태에서 검색: O(log n) - 이진 검색 가능
- 선형 탐색보다는 좋다.
- 선형 탐색 : 탐색 갯수가 늘어날 수록 탐색 시간이 늘어난다.
List<T>와 ArrayList 개요
- .NET은 동적 크기의 배열을 제공하는 List<T>(제네릭)와 ArrayList(비제네릭) 클래스를 제공함
- ArrayList 사용하면 안되는 이유 : 박싱, 언박싱, 오버헤드가 일어나기 때문이다.
- ArrayList는 IList를 구현하고, List<T>는 IList와 IList<T>를 구현함
- 두 클래스 모두 내부적으로 객체 배열을 유지하며, 용량이 부족하면 더 큰 배열로 교체함
- List<T>는 T가 값 형식일 때 박싱/언박싱 오버헤드를 피할 수 있어 ArrayList보다 몇 배 더 빠름
List<T> 기본 사용 예제
var words = new List<string>();
//words.Count; //0
words.Add("melon");
words.AddRange(new[] { "banana", "plum" });
words.Insert(0, "lemon"); //IList에 있다.
words.InsertRange(0, new[] { "peach", "nashi" });
words.Remove("melon");
words.RemoveAt(3);
words.RemoveRange(0, 2);
words.RemoveAll(s => s.StartsWith("n")); //매개변수고 들어온 문자열로 시작하는 문자열을 전부 삭제하고, 결과를 true false로 반환하는 함수
Console.WriteLine(words[0]);
Console.WriteLine(words[words.Count - 1]);
foreach (string s in words)
Console.WriteLine(s);
List<string> subset = words.GetRange(1, 2);
string[] wordsArray = words.ToArray(); //새로 생성해서 반환하는것이니 서로 다른 메모리를 참조하는 것이다.
List<T> 활용 예제 - 학생 성적 관리
var students = new List<Student>();
// 학생 추가
students.Add(new Student("Kim", 85));
students.Add(new Student("Lee", 92));
students.Add(new Student("Park", 78));
// 점수가 80점 이상인 학생만 필터링
var highScoreStudents = new List<Student>();
foreach (var student in students)
{
if (student.Score >= 80)
highScoreStudents.Add(student);
}
// 점수순 정렬 (내림차순)
students.Sort((s1, s2) => s2.Score.CompareTo(s1.Score));
public class Student
{
public string Name { get; set; }
public int Score { get; set; }
public Student(string name, int score)
{
Name = name;
Score = score;
}
}
ArrayList 사용 예제
`ArrayList` al = new `ArrayList`();
al.Add("hello");
string first = (string)al[0]; // 형변환 필요
string[] strArr = (string[])al.ToArray(typeof(string));
// 다음은 컴파일은 되지만 실행시 예외 발생
int first = (int)al[0]; // 실행시 예외
LinkedList<T>
LinkedList<T> 성능 특성
- 순차 접근: O(n) - 처음부터 순차적으로 탐색해야 함
- 알고있는 정보가 시작과 끝 주소여서 탐색이 불가능하다.
- 삽입/삭제: O(1) - 노드의 참조만 변경하면 되므로 매우 빠름
- 중간 삽입 삭제가 빈번하다면 링크드 리스트가 편하다.
- 메모리 사용: 요소당 추가 참조가 필요하여 List<T>보다 더 많은 메모리 사용
LinkedList<T> 기본 사용 예제
var tune = new LinkedList<string>();
tune.AddFirst("do"); // do
tune.AddLast("so"); // do - so
tune.AddAfter(tune.First, "re"); // do - re - so
tune.AddAfter(tune.First.Next, "mi"); // do - re - mi - so
tune.AddBefore(tune.Last, "fa"); // do - re - mi - fa - so
tune.RemoveFirst(); // re - mi - fa - so
tune.RemoveLast(); // re - mi - fa
LinkedListNode<string> miNode = tune.Find("mi");
tune.Remove(miNode); // re - fa
tune.AddFirst(miNode); // mi - re - fa
foreach (string s in tune)
Console.WriteLine(s);
- After : 뒤에 삭제 혹은 앞에 삭제
- Before : 뒤에 추가 혹은 앞에 추가
- find : 노드를 반환한다.
LinkedList<T> 활용 예제 - 음악 플레이리스트
public class Song
{
public string Title { get; set; }
public string Artist { get; set; }
public TimeSpan Duration { get; set; } //TimeSpan : 기간 저장하는 데이터형
public Song(string title, string artist, TimeSpan duration)
{
Title = title;
Artist = artist;
Duration = duration;
}
public override string ToString() =>
$"{Title} - {Artist} ({Duration.Minutes}:{Duration.Seconds:D2})";
}
public class MusicPlaylist
{
private LinkedList<Song> playlist = new LinkedList<Song>();
private LinkedListNode<Song> currentSong;
// 재생목록에 곡 추가
public void AddSong(Song song)
{
playlist.AddLast(song);
if (currentSong == null)
currentSong = playlist.First;
}
// 특정 곡 앞에 새로운 곡 삽입
public bool AddBefore(string title, Song newSong)
{
var node = playlist.First;
while (node != null)
{
if (node.Value.Title == title)
{
playlist.AddBefore(node, newSong);
return true;
}
node = node.Next;
}
return false;
}
// 특정 곡 삭제
public bool RemoveSong(string title)
{
var node = playlist.First;
while (node != null)
{
if (node.Value.Title == title)
{
if (node == currentSong)
{
currentSong = node.Next ?? playlist.First;
}
playlist.Remove(node);
return true;
}
node = node.Next;
}
return false;
}
// 재생 시간이 긴 곡들 삭제
public int RemoveLongSongs(TimeSpan threshold)
{
int removedCount = 0;
var node = playlist.First;
while (node != null)
{
var nextNode = node.Next;
if (node.Value.Duration > threshold)
{
if (node == currentSong)
{
currentSong = nextNode ?? playlist.First;
}
playlist.Remove(node);
removedCount++;
}
node = nextNode; //관리가 자동이기에 순회하면서 삭제해도 문제 없다.
}
return removedCount;
}
// 재생목록 출력
public void PrintPlaylist()
{
var node = playlist.First;
while (node != null)
{
string current = (node == currentSong) ? " ▶ " : " ";
Console.WriteLine($"{current}{node.Value}");
node = node.Next;
}
}
}
Queue<T>와 Stack<T>
내부 구조와 성능
- 두 자료구조 모두 내부적으로 배열을 사용하여 구현됨
- 배열이 가득 차면 더 큰 배열을 할당하고 요소를 복사함
- Queue<T>의 Enqueue/Dequeue: 대부분의 경우 O(1)
- 사이즈 늘려야하는 경우 O(n^2)이지만 이 경우 빼고는 O(1)이다.
- 빼고 뺀 자리는 무시하고 다음 순서의 요소가 첫 요소가 된다.
- Stack<T>의 Push/Pop: 대부분의 경우 O(1)
사용 시나리오
- Queue<T>
- 작업 대기열 구현
- 버퍼 구현
- 너비 우선 탐색(BFS) 구현
- Stack<T>
- 실행 취소/다시 실행 기능 구현
- 수식 계산
- 깊이 우선 탐색(DFS) 구현
Queue<T> 개요
- 선입선출(FIFO, First-In-First-Out) 자료구조를 구현함
- 내부적으로 배열을 사용하여 구현되며 필요시 크기가 조정됨
Queue<T> 기본 예제
var q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(20);
int[] data = q.ToArray(); // 배열로 내보내기
Console.WriteLine(q.Count); // "2" 출력
Console.WriteLine(q.Peek()); // "10" 출력
Console.WriteLine(q.Dequeue()); // "10" 출력
Console.WriteLine(q.Dequeue()); // "20" 출력
Console.WriteLine(q.Dequeue()); // 예외 발생 (큐가 비어있음)
Queue<T> 활용 예제 - 프린터 대기열
var printQueue = new Queue<PrintJob>();
// 인쇄 작업 추가
printQueue.Enqueue(new PrintJob("보고서.docx", 5));
printQueue.Enqueue(new PrintJob("사진.jpg", 2));
printQueue.Enqueue(new PrintJob("청구서.pdf", 1));
// 인쇄 작업 처리
while (printQueue.Count > 0)
{
PrintJob job = printQueue.Dequeue();
Console.WriteLine($"인쇄 중: {job.DocumentName} ({job.Pages}페이지)");
Thread.Sleep(1000); // 인쇄 시간 시뮬레이션
}
public class PrintJob
{
public string DocumentName { get; set; }
public int Pages { get; set; }
public DateTime SubmitTime { get; set; }
public PrintJob(string name, int pages)
{
DocumentName = name;
Pages = pages;
SubmitTime = DateTime.Now;
}
}
Stack<T> 개요
- 후입선출(LIFO, Last-In-First-Out) 자료구조를 구현함
- Queue<T>와 마찬가지로 내부적으로 배열을 사용함
Stack<T> 기본 예제
var s = new Stack<int>();
s.Push(1); // 스택 = 1
s.Push(2); // 스택 = 1,2
s.Push(3); // 스택 = 1,2,3
Console.WriteLine(s.Count); // 3 출력
Console.WriteLine(s.Peek()); // 3 출력, 스택 = 1,2,3
Console.WriteLine(s.Pop()); // 3 출력, 스택 = 1,2
Console.WriteLine(s.Pop()); // 2 출력, 스택 = 1
Console.WriteLine(s.Pop()); // 1 출력, 스택 = 비어있음
Console.WriteLine(s.Pop()); // 예외 발생
Stack<T> 활용 예제 - 실행 취소/다시 실행
public class TextEditor
{
private Stack<string> undoStack = new Stack<string>();
private Stack<string> redoStack = new Stack<string>();
private string currentText = "";
public void Type(string text)
{
undoStack.Push(currentText);
redoStack.Clear();
currentText = text;
}
public string Undo()
{
if (undoStack.Count == 0)
return currentText;
redoStack.Push(currentText);
currentText = undoStack.Pop();
return currentText;
}
public string Redo()
{
if (redoStack.Count == 0)
return currentText;
undoStack.Push(currentText);
currentText = redoStack.Pop();
return currentText;
}
}
HashSet<T>와 SortedSet<T>
HashSet<T>와 SortedSet<T> 개요
- Contains 메서드가 해시 기반 조회를 통해 빠르게 실행됨
- 중복 요소를 저장하지 않으며 중복 추가 요청은 무시함
- 위치로 요소에 접근할 수 없음
- SortedSet<T>는 요소를 정렬된 상태로 유지하고, HashSet<T>는 정렬하지 않음
- 헤쉬테이블은 정렬이 안된다.
- 정렬된 상태 유지 : 이진 탐색 트리
- 해쉬 테이블 자료구조는 순서에 의미가 없는 자료구조다.
HashSet<T> 기본 예제
var letters = new HashSet<char>("the quick brown fox");
Console.WriteLine(letters.Contains('t')); // true
Console.WriteLine(letters.Contains('j')); // false
foreach (char c in letters)
Console.Write(c); // the quickbrownfx
// 교집합 연산
letters.IntersectWith("aeiou"); //intersect : 교집합 / IEnumerator Character 를 넣은것이다.
foreach (char c in letters)
Console.Write(c); // euio
// 차집합 연산
letters = new HashSet<char>("the quick brown fox");
letters.ExceptWith("aeiou");
foreach (char c in letters)
Console.Write(c); // th qckbrwnfx
// 대칭차집합 연산 - 같은것은 빠지고 다른것만 반환한다.
letters = new HashSet<char>("the quick brown fox");
letters.SymmetricExceptWith("the lazy brown fox");
foreach (char c in letters)
Console.Write(c); // quicklazy
HashSet<T> 활용 예제 - 방문 기록 관리
// 사용 예시
var log = new UserLog();
log.LogVisit("index.html");
log.LogVisit("download.html");
log.LogVisit("index.html"); // 중복 무시
log.LogDownload("report.pdf");
log.LogDownload("report.pdf"); // 중복 무시
log.PrintStats();
public class UserLog
{
//내가 만든 클래스를 <>안에 넣고싶다면 GetHashCode 함수를 써야한다.
private HashSet<string> visitedUrls = new HashSet<string>();
private HashSet<string> downloadedFiles = new HashSet<string>();
public void LogVisit(string url)
{
visitedUrls.Add(url); // 중복된 URL은 자동으로 무시됨
}
public void LogDownload(string filename)
{
downloadedFiles.Add(filename);
}
public void PrintStats()
{
Console.WriteLine($"방문한 고유 URL 수: {visitedUrls.Count}");
Console.WriteLine($"다운로드한 고유 파일 수: {downloadedFiles.Count}");
}
// 방문은 했지만 다운로드는 하지 않은 URL 찾기
public HashSet<string> GetUrlsWithoutDownloads()
{
HashSet<string> result = new HashSet<string>(visitedUrls);
result.ExceptWith(downloadedFiles);
return result;
}
}
SortedSet<T> 예제
var letters = new SortedSet<char>("the quick brown fox");
foreach (char c in letters)
Console.Write(c); // bcefhiknoqrtuwx
// f와 i 사이의 문자들만 가져오기
foreach (char c in letters.GetViewBetween('f', 'i'))
Console.Write(c); // fhi
- SortedSet : 정렬된 상태로 반환된다.
컬렉션 선택 가이드
- 각 컬렉션은 자신만의 특징과 장점이 있으며, 상황에 맞는 적절한 컬렉션을 선택하는 것이 중요하다:
- List<T>
- 인덱스로 빠른 접근이 필요한 경우
- 끝에서의 삽입/삭제가 주로 일어나는 경우
- 데이터를 순차적으로 자주 열거하는 경우
- LinkedList<T>
- 중간 삽입/삭제가 빈번한 경우
- 메모리 공간이 충분하고 순차적 접근이 주된 경우
- 양방향 순회가 필요한 경우
- Queue<T>
- 선입선출(FIFO) 처리가 필요한 경우
- 작업 대기열, 버퍼, 메시지 큐 등을 구현할 때
- 너비 우선 탐색(BFS) 알고리즘 구현시
- Stack<T>
- 후입선출(LIFO) 처리가 필요한 경우
- 실행 취소/다시 실행 기능 구현시
- 수식 계산, 구문 분석 등에서
- 깊이 우선 탐색(DFS) 알고리즘 구현시
- HashSet<T>
- 빈번한 탐색의 경우
- 중복 제거가 필요한 경우
- 빠른 검색이 필요한 경우
- 집합 연산(합집합, 교집합, 차집합 등)이 필요한 경우
- 요소수가 많은 경우
- SortedSet<T>
- 빈번한 탐색의 경우
- 중복 제거와 함께 정렬이 필요한 경우
- 특정 범위의 요소들을 자주 조회하는 경우
- 정렬된 상태를 유지해야 하는 경우
- 요소수가 많은 경우