대학교 알고리즘 강의에서 배운 내용을 정리한 글
알고리즘이란?
- 문제를 해결하기 위한 단계적인 절차
알고리즘의 특성
- 정확성: 알고리즘은 주어진 입력에 대해 올바른 해를 반환
- 수행성: 알고리즘의 각 단계는 컴퓨터에서 수행 가능
- 유한성: 알고리즘은 유한한 단계 내에 종료
- 효율성: 알고리즘은 시간과 공간 측면에서 효율적이어야 함
알고리즘의 종류
- 분할 정복 (Divide and Conquer): 문제를 작은 부분으로 나누고, 각 부분의 해결을 결합하여 전체 문제를 해결
- 그리디 (Greedy): 매 순간 가장 최선의 선택을 반복하여 최적의 해를 도출
- 동적 계획법 (Dynamic Programming): 중복되는 부분 문제를 해결해 결과를 저장하여 최적의 해를 구함
- 근사 알고리즘 (Approximation Algorithm): 최적해를 구하기 어렵거나 시간이 오래 걸릴 때 근사해를 빠르게 찾음
- 백트래킹 (Backtracking): 해를 탐색하다가 유망하지 않으면 되돌아가서 다른 경로를 탐색
- 정렬 알고리즘 (Sorting Algorithm): 데이터를 주어진 기준에 따라 순서대로 배열
- 그래프 알고리즘 (Graph Algorithm): 그래프 구조를 탐색하거나 최적 경로 등을 구함
- 기하 알고리즘 (Geometric Algorithm): 기하학적 문제를 해결하는 알고리즘
- 병렬 알고리즘 (Parallel Algorithm): 문제를 여러 부분으로 나누어 동시에 처리
- 분산 알고리즘 (Distributed Algorithm): 여러 컴퓨터에서 분산하여 실행되는 알고리즘
- 양자 알고리즘 (Quantum Algorithm): 양자 컴퓨터에서 실행되어 고전 컴퓨터보다 빠르게 문제를 해결
문제의 요구 조건
- 입력과 출력으로 명시 가능
- 알고리즘은 입력으로부터 출력을 만드는 과정을 기술하는 것
자료 구조
- 자료를 효율적으로 관리하는 방법
- 컴퓨터 분야에서 효율적으로 접근하고 수정할 수 있도록 자료를 구성 관리하는 구조
자료 구조 종류
- 단순 자료 구조: 실수, 문자, 문자열 등
- 선형 자료 구조: 선형 리스트, 연결 리스트, 스택, 큐 등
- 비선형 자료 구조: 트리, 그래프 등
- 파일 자료 구조: 디스크에 저장되는 방식에 따라 순차 파일, 직접 파일로 구분
원하는 데이터를 최소한위 시도로 찾는 방법 (이진 탐색)
- 오름차순으로 정렬된 데이터를 반으로 나눔
- 나눠진 데이터를 다시 반으로 나눔
- 원하는 데이터를 찾을 때까지 (2.) 반복
거스름돈 동전의 최소 개수를 구하는 방법
- 그리디(탐욕) 알고리즘 사용
한 붓 그리기
- 오일러 서킷 사용
미로 탈출
- 오른손 법칙 사용
동전 속에 숨긴 가벼운 가짜 동전 찾기 (분할 법칙)
- 동전을 개수로 반씩 나눔
- 저울로 두 동전 그룹의 무게를 비교
- 가벼운 동전 그룹을 다시 반으로 나눔
- 가벼운 가짜 동전을 찾을 때까지 (2. 3.) 반복
독이 든 술단지를 찾는 방법 (이진수)
- 술단지의 술을 먹고 죽거나 살거나 두 가지 경우만 존재, 1비트 정보
- "2의 n제곱 >= 술단지의 개수"를 만족하는 n명이 필요
- 예시) 술단지가 30개라면 5명 필요 (2^5 = 32)
유클리드 최대공약수 알고리즘
-
최대공약수는 2개 이상의 자연수의 공약수들 중에서 가장 큰 수
입력: a, b (a >= b >= 0)
if (b=0) return a
return Euclid(b, a mod b)
알고리즘의 효율성
- 수행 시간, 수행 메모리 공간 등을 고려
- 시간 복잡도, 공간 복잡도 등
최악 경우 분석
- 알고리즘이 처리하는 입력 중 가장 느리게 수행되는 경우 분석
- 보장된 상한 제공, 최악의 성능을 예측
평균 경우 분석
- 입력의 평균적인 경우를 가정하여 수행 시간 분석
- 확률 분포를 고려해 일반적인 성능 예측
최선 경우 분석
- 알고리즘이 가장 빠르게 수행되는 경우 분석
- 일반적으로 최고의 성능 예측
상각 분석
- 알고리즘의 평균적인 성능을 분석하며, 최악을 피하는 방법을 함께 고려
- 장기적인 성능 고려에 유용, 반복적인 작업에서의 평균 성능 예측
예시) 최악 경우 분석, 평균 경우 분석, 최선 경우 분석
- 집에서 지하철역까지 버스 타고 이동
- 버스의 배차 간격: 30분
- 버스를 기다리는 시간 (배차 간격에 포함): 5분~10분
- 버스의 이동 시간: 20분~30분
- 지하철역에서 대학교역까지 지하철 타고 이동
- 지하철의 배차 간격: 5분~10분
- 지하철을 기다리는 시간 (배차 간격에 포함): 5분~10분
- 지하철의 이동 시간: 24분
- 대학교역에서 강의실까지 이동
- 강의실까지 이동: 5분
최악 경우 분석
1. 버스를 기다리는 시간: 최대 30분
2. 버스를 타고 이동하는 시간: 최대 30분
3. 지하철을 기다리는 시간: 최대 10분
4. 지하철을 타고 이동하는 시간: 24분
5. 지하철에서 내리고 강의실까지 이동하는 시간: 5분
최악 경우 결과:
30분 + 30분 + 10분 + 24분 + 5분 = 99분
최악 경우 등교 시간: 99분
평균 경우 분석
1. 버스를 기다리는 시간: 10분 (버스 출발 시간에 맞게 등교 시작)
2. 버스를 타고 이동하는 시간: 평균 25분
3. 지하철을 기다리는 시간: 평균 7.5분
4. 지하철을 타고 이동하는 시간: 24분
5. 지하철에서 내리고 강의실까지 이동하는 시간: 5분
평균 경우 결과:
10분 + 25분 + 7.5분 + 24분 + 5분 = 71.5분
평균 경우 등교 시간: 71.5분
최선 경우 분석
1. 버스를 기다리는 시간: 0분
2. 버스를 타고 이동하는 시간: 20분
3. 지하철을 기다리는 시간: 0분
4. 지하철을 타고 이동하는 시간: 24분
5. 지하철에서 내리고 강의실까지 이동하는 시간: 5분
최선 경우 결과:
20분 + 24분 + 5분 = 49분
최선 경우 등교 시간: 49분
Big-Oh 표기 (O)
- 알고리즘의 시간 복잡도를 나타내는 수학적 표기법
- 입력 크기(n)가 증가함에 따라 수행 시간이 어떻게 증가하는지 설명, 최악의 경우에 대한 상한 제공 (예: O(n), O(log n), O(n^2) 등)
Big-Omega 표기 (Ω)
- 알고리즘의 시간 복잡도를 나타내는 수학적 표기법, 최선의 경우에 대한 하한 제공
- 입력 크기(n)가 증가할 때 알고리즘이 수행하는 최소 시간 (예: Ω(n)이라고 하면 입력 크기가 n일 때 알고리즘의 수행 시간은 n에 비례하여 증가할 수 있음을 의미)
Theta 표기 (Θ)
- 알고리즘의 시간 복잡도를 나타내는 수학적 표기법, 수행 시간의 정확한 성장 설명
- 입력 크기(n)에 대해 알고리즘의 수행 시간이 상한과 하한 모두를 제공하는 경우 사용
UML
(Unified Modeling Language) 통합 모델링 언어
- 시각화 언어
- 명세화 언어
- 구축 언어
- 문서화 언어
OOP
객체 지향 프로그래밍(Object-Oriented Programming)
- 객체 : 현실에 존재하는 모든 것을 구체적으로 표현
- 클래스 : 객체를 생성할 수 있는 툴, 그 자체만으로는 사용 불가
- 메시지 : 객체 간의 상호작용 수단, 신호
- 송신 객체 : 요청하는 객체
- 수신 객체 : 요청을 수행하는 객체
- 추상화 : 특정 측면을 강조하여 나타내는 것
- 실체화 : 추상화된 모델을 프로그래밍으로 구현
- 캡슐화 : 데이터와 메서드를 하나로 묶어 외부에서 접근을 제한하여 객체의 내부 구현을 숨기는 것
- 상속 : 프로그램을 쉽게 확장할 수 있게 도와주는 수단, 객체 지향 패러다임에서만 구현 가능, 정보를 공개, 재사용하는 개념
- 다형성 : 같은 이름의 함수가 존재하지만 동작은 다르게 수행하는 것
- 추상 클래스 : 메서드는 있으나 메서드의 처리 내용은 없음, 상속을 통해 메서드가 구현
- 인터페이스 : 상수와 추상 메서드만 가짐, 다중 상속의 기능 제공 (정의만 하고, 구현은 상속받은 클래스에서 함) (예: 전원 플러그, 전기 제공만 하고 전기 활용은 각 기기에서)
모델링
- 모델링 : 시스템을 구축할 떄 개발자가 고민, 결정하는 모든 활동, 구현 단계 이전의 요구사항 정의, 분석, 설계 등에서 하는 활동
- 부처 방법론 : 시스템 구축을 위한 요구사항 분석과 설계에 초점을 맞춘 구조적 모델링 방법론
- 아콥슨의 OOSE : 객체 지향적 접근을 통해 시스템을 유스케이스로 모델링하는 방법론
- 함바의 OMT : 객체의 속성, 행위, 관계를 기반으로 시스템을 분석, 설계하는 객체 지향 모델링 기법
- 람보의 BOO : 객체지향 분석, 설계 및 구현을 위한 통합 방법론으로, 시스템의 요구사항을 객체 기반으로 정의하고 이를 구조화하는 방법을 제공
- 모델 : 모델링의 결과
사물
- 정적 사물 : 모델의 물리적 요소를 표현하는 명사
- 클래스 : 객체를 생성하기 위한 청사진, 속성과 메서드를 정의
- 인터페이스 : 객체 간의 상호작용을 정의하는 규칙, 메서드 시그니처만 포함
- 통신 : 객체 간의 메시지 전달 방법, 상호작용을 가능하게 함
- 컴포넌트 : 시스템을 구성하는 독립적인 모듈, 재사용 가능한 기능 제공
- 패키지 : 관련 클래스를 그룹화하여 관리하는 단위, 네임스페이스 제공
- 노드 : 실행할 때 존재하는 물리적 요소 (예: 서버)
- 동적 사물 : 모델의 동적인 부분을 동사로 표시
- 교류 : 객체 간의 상태 변화나 정보 전달을 나타내는 행동
- 유스케이스 : 시스템이 수행하는 활동들을 순차적으로 표시
- 상태 머신 : 외부 이벤트에 의한 객체의 상태와 변화 순서를 기술
- 주해 사물 : 모델링에 참여하지 않음 (예: 주석)
관계
- 의존 관계 : 두 사물 간의 의미적 관계, 점선으로 표시
- 연관 관계 : 객체 사이의 연결 관계, 지속적으로 유지 (이름, 역할), 실선으로 표시, 다중성
- 일반화 관계 : 일반화된 사물과 좀 더 특수화된 사물의 관계
- 실체화 관계 : 한 객체가 다른 객체에게 오퍼레이션을 수행하도록 하는 관계
다이어그램
- 클래스 : 객체의 구조와 행동을 정의하는 다이어그램
- 컴포넌트 : 시스템의 모듈 간 관계를 표현하는 다이어그램
- 배치 : 시스템의 물리적 구성 요소와 그 관계를 나타내는 다이어그램
- 패키지 : 관련 클래스 및 컴포넌트를 그룹화하여 표현하는 다이어그램
- 유스케이스 : 시스템과 사용자 간 상호작용을 설명하는 다이어그램
- 순차 : 객체 간의 메시지 흐름과 상호작용을 시간 순서에 따라 표현하는 다이어그램
- 통신 : 객체 간의 상호작용과 관계를 나타내는 다이어그램
- 활동 : 프로세스나 작업 흐름을 나타내는 다이어그램
- 상태 : 객체의 상태와 상태 전이를 설명하는 다이어그램
UML 뷰
- 유스케이스 뷰 (요구사항 뷰) : 요구사항을 보여주는 관점
- 설계 뷰 : 시스템 내부의 크랠스의 컴포넌트를 파악해 기술
- 프로세스 뷰 : 설계 뷰와 마찬가지로 시스템 내부의 구조에 중점을 두고 기술
- 구현 뷰 : 구현 모듈과 그들의 관계, 파일 의존 관계
- 배치 뷰 : 통신 방법에 중점을 둠
UML뷰 참고 이미지
활동 다이어그램의 표현
- 활동 및 전이 : 작업의 수행과 그 사이의 흐름을 나타냄
- 분기 : 특정 조건에 따라 흐름이 여러 갈래로 나누어지는 지점
- 동기화 막대 : 병렬로 진행되는 활동의 시작과 끝을 나타내는 요소
- 신호 : 다른 활동이나 객체 간의 정보를 전달하는 방법
- 구획면 : 활동을 그룹화하여 명확하게 표현하는 영역
- 용도 : 시스템의 프로세스 흐름을 시각적으로 모델링하여 이해를 돕는 기능
분할 정복 알고리즘
주어진 문제의 입력을 분할하여 문제를 해결하는 알고리즘
- 더이상 분해되지 않는 부분 문제
- 각 부분 문제를 해결한 부분해를 취합하여 전체 문제 해결
합병 정렬 알고리즘
입력이 2개로 분할, 부분 문제의 크기는 전체 문제의 1/2
분할 정렬 알고리즘으로 분류가능한 퀵 정렬과 합 정렬보다 효율적일 수 있음
퀵 정렬 알고리즘
피벗이라 일컫는 숫자(원소)를 기준으로 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 이동하여 완전히 정렬하는 알고리즘
- 기준이 되는 피벗은 왼쪽, 오른쪽 어디에도 속하지 않음
- 퀵정렬의 시간 복잡도는 어떤 숫자를 피봇으로 고르냐에 달림
- 최악 경우 시간 복잡도 = O(n^2)
- 최선 경우 시간 복잡도 = O(nLog2n)
- 평균 경우도 = O(nLog2n)
- 퀵정렬은 그 크기가 클수록 효율적이고, 크기가 작을 때는 삽입 정렬이 효율적임
선택 문제 알고리즘
n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 알고리즘
- 퀵 정렬은 주어진 숫자를 완전히 정렬
[7, 2, 1, 6, 8, 5, 3, 4] -> [1, 2, 3, 4, 5, 6, 7, 8] - 선택 문제는 k번째로 작은 숫자를 찾기 위해 k번째 숫자가 정렬된 위치에 도달하면 정렬 종료
[7, 2, 1, 6, 8, 5, 3, 4] (k = 5) -> [1, 2, 3, 4, 5, 6, 7, 8]
다섯 번째 위치에 있는 수가 확인되면 정렬 종료
최근접 점의 쌍 찾기
2차원 평면에 n개의 점이 입력으로 주어질 때 가장 가까운 점끼리의 거리를 찾는다
- 분할 정복을 이용하면 효율적으로 풀 수 있음 (점들을 반으로 나눠서 찾음)
그리디 알고리즘
- 최적화 문제를 해결하는 알고리즘
- 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림
거스름돈 동전의 최소 개수 구하기
- 가격 단위가 큰 순서대로 최대 개수를 계산하여 더함
- 근시안적 특성 때문에 500원짜리를 계산할 때 다른 동전의 개수를 고려하지 않음
최소 신장 트리
- 주어진 가중치 그래프에서 사이클 없이 모든 정점을 연결하는 트리 중에서 가중치 합이 가장 작은 트리를 구하는 방법
크루스칼 알고리즘
- 사이클을 만들지 않는 경우에만 간선을 선택하여 트리를 형성
- n개의 트리들이 합쳐져 1개가 됨
프림 알고리즘
- 트리를 점점 확장해 나가는 방식
- 1개의 트리들이 모여 n개가 됨
다익스트라 알고리즘
- 가장 짧은 경로를 구하는 데 사용
- 가중치가 음수가 아닌 그래프에서 동작하며, 그리디 알고리즘 사용
- 하나의 시작 정점에서 모든 정점까지의 최단 경로를 구할 때 사용 됨
부분 배낭 문제
- 물건의 가치와 무게를 따져 최대한의 가치를 배낭 안에 넣는 문제
- 가치 대비 무게의 비율을 따져 비율이 높은 것부터 배낭 안에 넣음
집합 커버 문제
- 가장 많은 원소를 덮는 부분 집합을 선택
- 선택한 부분 집합의 원소를 전체 집합에서 제거
- 남은 원소 중 가장 많은 원소를 덮는 부분 집합을 다시 선택
- 전체 집합이 덮일 때까지 반복
작업 스케쥴링 문제
- 작업과 해당 기한, 이익 파악
- 기한이 가까운 순서로 작업 정렬
- 가장 높은 이익을 우선으로 하여 작업 선택
- 작업을 기한 내에 스케줄링하고, 스케줄이 가득 차면 다음 작업 생략
- 최종적으로 최대 이익 계산
허프만 압축 문제
- 각 문자의 빈도수를 기반으로 우선순위 큐 만듦
- 큐에서 가장 낮은 빈도의 두 노드 선택
- 선택한 두 노드를 합쳐 새로운 노드 생성, 이를 다시 큐 추가
- 큐의 노드가 하나 남을 때까지 2-3 단계 반복
- 최종적으로 남은 노드가 허프만 트리의 루트가 됨
- 각 문자의 경로를 통해 허프만 코드 생성
안녕하세요