[인프런 워밍업 클럽 CS 2기] 1주차 발자국 - 자료구조/알고리즘
[ Section 1. 개요 ]
1. 자료구조와 알고리즘이란?
프로그램은 자료구조와 알고리즘으로 이루어진다.
프로그램 작성 시 적절한 자료구조를 선택하여 데이터를 저장하고, 자료구조에 맞는 알고리즘을 사용해 데이터를 가공하여 원하는 결과를 도출한다.
1) 자료구조
자료구조란?
데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타낸다.
단순한 자료구조 : 변수, 배열
자료구조에 따라 처리방법이 달라지며 데이터의 변경시 코드가 더 단순해질 수도 있다.
2) 알고리즘
알고리즘이란?
어떤 문제를 해결하기 위한 확실한 방법
데이터가 어떤 자료구조를 하고 있는지에 따라 알고리즘이 달라진다.
알고리즘은 자료구조에 많은 영향을 받는다.
한가지 자료구조에 대해서도 여러가지 알고리즘이 있을 수 있다.
2. 시간복잡도
1) 시간복잡도
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간의 효율성을 나타내는 척도를 말한다.
알고리즘의 성능을 평가할 때 처리 속도를 중요한 기준으로 사용하지만, 컴퓨터의 사양에 따라 실제 속도는 달라질 수 있다.
따라서, 실제 시간을 측정하는 것보다 알고리즘에서 성능에 영향을 미치는 핵심 연산을 기반으로 실행 시간을 예측하는 방식으로 시간복잡도를 평가한다.
2) 시간복잡도 평가시 점근 표기법(Asymptotic Notation)의 사용
3가지 종류의 표기법이 사용된다.
Big-Ω, Big-O, Big-Θ
표기법중 Big-O와 Big-Θ를 주로 사용하며, 가장 많이 사용되는것은 Big-O 이다.
1) 빅 오메가 표기법 (Big-Ω, Big-Omega Notation, Ω)
최선의 경우를 나타내는 표기법
2) 빅 오 표기법 (Big-O, Big-O Notation, O)
최악의 경우를 나타내는 표기법
3) 빅 세타 표기법 (Big-Θ, Big-Theta Notation, Θ)
평균적인 경우 또는 정확한 시간 복잡도를 나타낸다.
3) 시간복잡도 분류
(1) 선형시간 알고리즘 O(n)
입력량이 많아지는 경우 계산량이 증가하므로
O(n)의 알고리즘은 선형시간 알고리즘이라고 부른다.
(2) 상수시간 알고리즘 O(1)
입력량의 크기에 상관없이 상수의 시간이 걸린다는 의미로 계산량이 꼭 한 번일 필요는 없다.
4) 빅 오(Big-O) 표기법의 특징
빅 오(Big-O) 표기법은 입력의 크기에 따라 알고리즘의 계산량이 어떻게 변하는지를 나타내는 척도를 제공한다.
빅 오(Big-O) 표기법에서는 성능에 가장 큰 영향을 미치는 항만 표기한다.
ex)
n**²** + 2n + 100이라는 성능을 가진 알고리즘의 빅 오 표기법은O(n**²**)이다.
빅 오(Big-O) 표기법에서 상수는 성능에 큰 영향을 미치지 않으므로 제거한다.
ex)
3n**²** + 100n성능의 알고리즘을 빅 오 표기법으로 나타내면O(n**²**)이다.
[ Section 2. 자료구조 ]
1. 배열
(1) 배열의 특징
일반적으로 프로그래밍 언어에서 배열을 선언할 때 크기를 지정해야 하며, 운영체제는 크기에 맞는 연속된 메모리 공간을 할당한다.
운영체제는 배열의 시작 주소만 기억하며, 인덱스를 이용해
O(1)의 성능으로 데이터를 참조할 수 있다.배열을 읽기/쓰기 와 같은 참조에서 빠른 성능을 보인다.
배열의 크기를 확장할 수 없기 때문에 데이터 추가/제거 시 성능 저하가 발생한다.
배열을 확장하려면 새로운 메모리 공간을 할당하고 기존 데이터를 복사해야 함.
배열을 미리 크게 선언하거나 사용하지 않는 공간이 있을 경우 메모리 공간이 낭비될 수 있다.
(2) 배열의 장단점
장점 : 인덱스 접근에서 빠른 성능(
O(1))을 제공한다.단점 : 크기를 미리 정해야 하며, 삽입/삭제가 비효율적이고, 메모리 낭비 가능성이 있다.
2. 연결 리스트 (Linked List)
연결 리스트 (Linked List)
연결 리스트는 노드(Node)라는 것을 만들어서 수행한다.
첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다.
(1) 장점
배열처럼 초기 크기를 알아야 하는 단점이 없다
빈 메모리 공간 아무 곳에 데이터를 생성하고 연결만 해주면 됨
데이터 삽입시 다음 가리키는 노드만 바꿔주면 되기 때문에 배열보다 작업이 간단함
(2) 단점
데이터를 찾을때 연속된 노드를 순회하여 데이터를 참조해야 함
연결 리스트에서 데이터 참조는
O(n)의 성능
3. 스택 (Stack)
스택은 마지막에 삽입된 데이터가 먼저 제거(LIFO, Last In First Out)되는 구조를 가진다.
데이터의 삽입과 제거는 항상 맨 앞(head/top)에서만 이루어진다.
스택은 LIFO 규칙만 충족하면 어떤 자료구조로도 구현할 수 있다.
FILO (First In Last Out)
먼저 들어간 데이터가 나중에 나오는 규칙
4. 큐 (Queue)
먼저 들어온 데이터가 먼저 나가는(FIFO, First In First Out) 구조를 가진다.
데이터의 삽입은 tail(rear)에서, 제거는 head(front)에서 이루어진다.
FIFO (First In First Out)
먼저 들어간 데이터가 먼저 나오는 규칙
운영체제에서 FIFO 스케줄링이 사용된다.
운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 꺼내어 처리한다.
5. 덱 (Deq)
데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조
덱을 이용하여 스택과 큐를 전부 구현할 수도 있다.
덱 (Deq)의 추상 자료형
printAll -
모든 데이터 출력
addFirst -
head에 데이터 삽입하는 함수
removeFirst -
head에서 데이터 제거하는 함수
addLast -
tail에 데이터 삽입하는 함수
removeLast -
tail에서 데이터 제거하는 함수
isEmpty -
리스트가 비었는지를 알려주는 함수
6. 해시테이블 (Hash Table)
Key를 Hash 함수를 통해 특정 위치에 매핑하여 데이터를 저장하는 자료구조이다.
해시와 테이블이 결합된 형태로, 해시 함수를 사용하여 테이블의 인덱스를 생성한다.
프로그래밍 언어에 따라 다양한 이름으로 불린다.
예 : 해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)
데이터 읽기, 삽입, 수정, 삭제를 평균적으로
O(1)의 성능으로 처리할 수 있다.
해시 테이블에서의 충돌 (Collision)
여러 Key가 동일한 Hash 값으로 매핑될 경우 충돌이 발생한다.
해시 테이블의 장단점
(1) 장점
빠른 데이터 읽기, 삽입, 삭제 성능을 제공한다.
(2) 단점
공간의 효율성이 떨어질 수 잇다.
미리 할당해야 하는 메모리 공간이 많다.
해시 함수에 따라 메모리 낭비가 발생할 수 있다.
해시 함수의 품질에 따라 성능에 큰 영향을 미치므로 좋은 해시 함수의 구현이 필수적이다.
7. 셋 (Set)
데이터의 중복을 허용하지 않는 자료구조
중복되지 않는 값 저장시 유용함
해시 테이블을 이용하기 때문에 해시 셋(Hash Set) 이라고도 불리며 쉽게 구현 가능
해시 테이블의 value 값은 사용하지 않고 key 만 사용해서 구현한다.
key 가 key 임과 동시에 데이터로 사용됨
셋 (Set)의 추상자료형
add(data) - 셋에 데이터를 추가하는 기능
매개변수로 전달되는 data는 key이자 데이터
isContain(data) - 셋에 해당 데이터가 있는지 체크하는 기능
해당 데이터가 셋에 있다면 true, 없다면 false를 리턴한다.
remove(data) - 셋에 데이터를 제거하는 기능
제거할 data를 매개변수로 전달하며 해시 테이블에서 해당 key를 제거
clear() - 셋을 비우는 기능
isEmpty() - 셋이 비었는지 검사하는 기능
printAll() - 테스트를 위해 셋의 모든 데이터를 출력하는 기능
답변 0