문제 1
[SB] [알고리즘과 자료 구조] File I/O의 주요 클래스들과 그 특징을 설명하고, 자료구조와 결합하여 사용하는 방법에 대해 설명하시오.
내 답변:
File: 파일/디렉토리 경로 자체를 표현, 존재 여부, 생성, 삭제 조작
Files: 정적 메서드로 파일 CRUD를 하는 클래스
Paths: 경로를 표현하는데 사용하는 클래스
FileReader/FileWriterr: 문자 기반 입출력 스트림
BufferReader/BufferWriter: 문자 스트림을 버퍼 단위로 끊어서 입출력하는 클래스
FileInputStream/FileOutputStream: 바이트 기반 입출력 스트림
자료구조와 결합하여 사용하는 방법(List 사용):
// User implements Serializable
try (FileInputStream fis = new FileInputStream("users.ser");
ObjectInputStream ois = new ObjectInputStream(fis);) {
users = (List<User>) ois.readObject();
}문제 해설:
File I/O의 주요 클래스로는 FileReader, BufferedReader, FileWriter, BufferedWriter가 있습니다. FileReader와 FileWriter는 문자 단위로 파일을 읽고 쓰는 기본적인 스트림 클래스이며, BufferedReader와 BufferedWriter는 이들을 감싸서 버퍼링 기능을 제공하는 보조 스트림 클래스입니다.
BufferedReader와 BufferedWriter는 내부적으로 버퍼를 사용하여 I/O 성능을 향상시킵니다. BufferedReader는 readLine() 메서드로 한 줄씩 읽을 수 있고, BufferedWriter는 버퍼링을 통해 출력 성능을 개선합니다.
자료구조와 File I/O를 결합할 때는, 예를 들어 ArrayList에 저장된 데이터를 파일에 저장할 때 BufferedWriter를 사용하여 각 요소를 순차적으로 파일에 쓸 수 있습니다. 반대로 파일에서 데이터를 읽어올 때는 BufferedReader로 한 줄씩 읽어 자료구조에 저장할 수 있습니다. 이를 통해 프로그램 종료 후에도 데이터를 영구적으로 보존하고, 다음 실행 시 복원할 수 있습니다.
문제 2
[SB] [알고리즘과 자료 구조] 제네릭의 개념과 컬렉션 프레임워크에서의 활용에 대해 설명하시오.
내 답변:
Generic이란 사용할 타입을 외부에서 결정할 수 있는 자바 문법입니다. T, U, V, E 등의 한 문자로 보통 표현하며 메서드나 클래스를 여러 타입에 대응하여 작성할 수 있기 때문에 다형성을 높입니다. T extends ClassName으로 상한타입을 제한하고 Supplier 메서드로만 사용할 수도 있고 T super ClassName으로 하한타입을 제한하고 Consumer 메서드로만 사용할 수 있습니다.
컬렉션 프레임워크에서 활용:
예를 들어 java.util.collections에서 List를 정의한다고 했을 때
public interface List<E> {
public void add(E element) {}
}이런 식으로 E에 어떤 타입이 오더라도 내부 배열에 해당 타입을 할당하여 사용할 수 있게 합니다.
문제 해설:
제네릭은 클래스나 메서드가 다양한 데이터 타입에 대해 동작할 수 있도록 일반화하는 기능입니다. 컴파일 시점에 타입을 체크하여 타입 안정성을 보장하고, 불필요한 타입 캐스팅을 줄여 코드의 재사용성을 높입니다.
제네릭은 컴파일 시점에서 타입을 체크함으로써 런타임 에러를 방지합니다. 예를 들어, List<String>으로 선언된 리스트에 정수를 추가하려고 하면 컴파일 오류가 발생하여 잠재적인 오류를 사전에 방지할 수 있습니다.
컬렉션 프레임워크에서는 List, Set, Map<K,V>와 같이 제네릭을 활용합니다. 예를 들어, List는 정수만을 저장할 수 있는 리스트를 생성하고, Map<String, Student>는 문자열 키와 Student 객체 값을 가지는 맵을 생성합니다. 이를 통해 컬렉션에 저장되는 데이터의 타입을 명확히 하고, 타입 관련 오류를 컴파일 단계에서 잡아낼 수 있습니다.
문제 3
[SB] [알고리즘과 자료 구조] Big O 표기법의 개념과 필요성에 대해 설명하고, 일상생활의 예시를 들어 O(1), O(n), O(log n), O(n^2)을 비교하여 설명하세요.
내 답변:
Big O 표기법이란 알고리즘이 얼마나 오래 걸리는지 표현하는 시간복잡도를 표기하는 하나의 방법으로, input 값 n의 크기에 따라 n이 충분히 클 경우 가장 미분값이 큰 단항식만 계수를 제거하고 표현합니다. 시간 복잡도는 보통 input의 값이 클 경우 문제가 되는 경우가 많고, 프로그래밍 특성상 제어할 수 없는 변수가 많기 때문에 가장 영향력이 큰 단항식만으로 알고리즘을 비교하기 위해 Big O 표기법을 사용합니다.
일상생활 예시(북카페):
O(1): 에어컨을 키는 행위. 손님 수에 상관 없이 상수의 시간이 걸립니다.
O(n): 웨이팅 시간. 손님 수에 비례하여 선형적으로 증가합니다. n < 테이블 수인 경우 웨이팅 시간이 0이지만 Big O 표기법에서 n이 충분히 클 경우만 고려합니다. 1인당 테이블 사용 시간이 다르긴 하지만 n이 충분히 클 경우 계수는 테이블 사용 시간의 평균으로 수렴할 것입니다.
O(log n): 책이 정렬된 책장에서 책을 찾는 행위. 정렬 되었기 때문에 양 끝의 중앙값만 추적하다보면 찾고자 하는 책을 찾을 수 있습니다. (log n / log 2) n: 책의 갯수
O(n^2): 손님의 주문을 받고 해당 테이블 번호를 찾아서 가져다 주는 행위. 손님이 n명이면 주문이 n개이고, 테이블 번호의 갯수도 n개이기 때문에 n * n의 시간 복잡도를 갖는다. 테이블 번호를 훑는 속도가 빠르더라도 n에 비례하기 때문에 O(n^2)이다.
문제 해설:
Big O 표기법은 알고리즘의 성능을 나타내는 방법으로, 알고리즘이 얼마나 빠르고 효율적인지를 수치화한 것입니다. 입력 크기가 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 예측할 수 있게 해주므로, 효율적인 프로그램 설계에 필수적입니다.
O(1)은 상수 시간으로, 입력 크기와 상관없이 항상 동일한 시간이 소요됩니다. 예를 들어, 도서관에서 도서 위치 시스템을 통해 특정 책의 위치를 즉시 찾는 경우입니다. 책이 몇 권이 있든 상관없이 동일한 시간이 걸립니다.
O(n)은 선형 시간으로, 입력 크기에 비례하여 시간이 증가합니다. 예를 들어, 정리되지 않은 책장에서 특정 책을 찾기 위해 한 권씩 순차적으로 확인해야 하는 경우입니다. 책이 많아질수록 찾는 시간이 비례하여 증가합니다.
O(log n)은 로그 시간으로, 입력이 커질수록 시간이 천천히 증가합니다. 예를 들어, 도서관에서 분류번호순으로 정렬된 책장에서 책을 찾을 때, 중간 지점부터 시작해서 찾고자 하는 책이 앞쪽에 있는지 뒤쪽에 있는지 판단하며 범위를 반씩 좁혀가는 경우입니다.
O(n^2)은 이차 시간으로, 입력 크기의 제곱만큼 시간이 증가합니다. 예를 들어, 도서관의 모든 책과 다른 도서관의 모든 책을 한 권씩 비교하여 중복 도서를 찾는 경우입니다. 각 도서관의 책 수가 n권이라면, 총 n x n번의 비교가 필요하므로 책의 수가 증가할수록 비교 시간이 제곱으로 증가합니다.
문제 4
[SB] [알고리즘과 자료 구조] 시간 복잡도와 공간 복잡도의 차이를 설명하고, O(n^2)의 특징과 실제 알고리즘에서의 예시를 들어 설명하시오. 또한 이를 개선할 수 있는 방법에 대해 서술하세요.
내 답변:
시간 복잡도는 알고리즘 수행 시간을 의미하고 공간 복잡도는 알고리즘이 사용하는 메모리 크기를 의미한다.
O(n^2)의 시간복잡도의 특징은 n개의 요소를 가진 배열을 순회하면서 반복문 안에서 다시 n개의 요소를 순회할 때 보통 측정된다. O(nlog n)보다 느리고 O(n^3)보다 빠르다.
O(n^2)의 공간복잡도를 가진 알고리즘은 거의 없다.
예시:
선택 정렬, 삽입 정렬, 버블 정렬처럼 단순한 정렬 알고리즘에서 O(n^2)의 시간복잡도가 사용된다.
병합 정렬처럼 절반씩 계속 쪼개서 정렬을 정복하고 합치는 방법을 사용하면 n번의 순회 안에서 n번의 순회를 하는게 아니라 n번의 순회 안에서 (logn / log2)번 순회하기 때문에 O(nlog n)의 시간복잡도로 개선할 수 있다.
문제 해설:
시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 나타내며, 입력이 많아질 때 처리 시간이 어떻게 증가하는지를 분석합니다. 반면 공간 복잡도는 알고리즘이 실행되면서 사용하는 메모리 양을 의미하며, 얼마나 많은 추가 메모리가 필요한지를 나타냅니다.
O(n^2)는 이차 시간 복잡도로, 입력 크기의 제곱만큼 시간이 소요됩니다. 대표적인 예시로 중첩된 반복문이 있습니다. 예를 들어, 학생들이 서로 인사를 하는 상황처럼, 각 학생이 다른 모든 학생과 인사를 해야 하는 경우 학생 수가 늘어날수록 인사 횟수가 제곱으로 증가합니다.
O(n^2) 알고리즘의 개선 방법으로는 다음과 같은 것들이 있습니다:
불필요한 반복 제거 (예: 이미 처리한 데이터는 다시 처리하지 않기)
효율적인 자료구조 활용 (예: HashMap을 사용하여 검색 시간 단축)
분할 정복 방식 적용 (예: O(n log n)의 병합 정렬 활용)
문제 5
[SB] [알고리즘과 자료 구조] ArrayList와 LinkedList의 데이터 삽입/삭제/검색 작업에서의 시간 복잡도 차이가 발생하는 이유를 설명하세요.
내 답변:
ArrayList는 동적 배열이지만 내부적으로는 Java의 Array(배열)를 사용하며, Array는 index i에 대한 탐색의 시간 복잡도가 O(1)이기 때문에(배열의 0번 인덱스부터 순서대로 저장되어 있기 때문) ArrayList 역시 index i에 대한 탐색의 시간 복잡도가 O(1)이다.
반면에 LinkedList는 Node들끼리 연결된 형태로 구현된 형태라 인덱스를 알아도 바로 접근할 수 없다. LinkedList는 이중연결배열으로 node는 prev node, next node, value의 정보만 담고 있기 때문에 first node에서 next node를 순차적으로 검색하거나 last node에서 prev node를 순차적으로 검색해야 하기 때문에 index i에 대한 탐색의 시간 복잡도는 O(n)이다. 대신 처음과 끝 index에 대한 탐색의 시간 복잡도는 O(1)이다.
단, index i로 검색하는게 아닌 value를 찾는 검색(contains)의 경우 n개의 노드를 순서대로 순회해야하기 때문에 ArrayList, LinkedList 모두 O(n)의 시간 복잡도를 갖는다.
ArrayList의 데이터 삽입 시간 복잡도는 맨 마지막에 삽입할 경우 O(1)이고(만약 배열 크기의 threshold를 넘으면 더 큰 배열로 복사하기 때문에 그 때만 O(n)이다. 이것은 가끔 일어난다.) 중간이나 처음에 삽입할 경우 O(n)이다. 삽입하고 그 뒤의 index에 해당하는 요소들을 한 칸씩 뒤로 밀어야하기 때문이다.
LinkedList의 데이터 삽입 시간 복잡도는 O(1)이다. 3개의 노드의 prev-next 관계만 다시 정해주면 되기 때문이다. 하지만 index i에 접근하는데 O(n)이 걸리기 때문에 결국 중간에 삽입하려면 접근(O(n)) + 삽입(O(1))이기 때문에 O(n)이 걸리는건 매한가지다. 대신 첫 노드와 끝 노드에 삽입은 O(1)이다.
삭제의 경우도 같은 이유로 삽입과 같은 시간 복잡도를 갖는다.(ArrayList, LinkedList 모두)
참고로 singly linked list는 맨 끝 삭제가 O(n)인데 LinkedList는 doubly linked list라서 prev 정보가 tail에 담겨져 있기 때문에 tail의 prev에 바로 접근할 수 있어 맨 끝 삭제가 O(1)이 된다는 장점이 있다.
대신 노드의 필드(prev)가 1개 늘어난다.
index로 접근할 일이 많다면 ArrayList, 스택처럼 맨 앞에 삽입/ 삭제가 잦을 경우 LinkedList(혹은 ArrayDeque)를 사용하면 된다.
삽입/삭제 작업에서 LinkedList는 접근하는데 O(n)이 드는것이고 ArrayList는 요소들을 한칸씩 미는데 O(n)이 드는것이므로 같은 O(n)이지만 상황에 따라 둘 중 하나가 더 빠른 환경이 있을것이다.
문제 해설:
ArrayList는 연속된 메모리 공간에 데이터를 저장하는 자료구조로, 특정 위치의 데이터를 찾는 것은 O(1)이지만, 중간에 데이터를 삽입하거나 삭제할 때는 O(n)이 소요됩니다. 이는 데이터 삽입/삭제 시 다른 모든 요소들을 이동시켜야 하기 때문입니다.
LinkedList는 각 노드가 다음 노드를 참조하는 구조로, 중간에 데이터를 삽입하거나 삭제하는 것은 O(1)이지만, 특정 데이터를 찾는 것은 O(n)이 소요됩니다. 이는 원하는 위치까지 순차적으로 이동해야 하기 때문입니다.
