컴퓨터 구조(Computer Architecture)
컴퓨터 시스템의 기본 구성:하드웨어, 소프트웨어(정보들이 이동하는 방향을 지정, 정보 처리의 종류를 지정, 이러한 동작들이 일어나는 시간을 지정해주는 명령(command)들의 집합으로, 시스템 소프트웨어(OS), 응용 소프트웨어(application software)가 있다.)
컴퓨터의 기본 구조:data read->processing->store
CPU(Central Processing Unit):data processing의 처리 길이에 따라 32bit, 64bit로 나뉨
Memory
-Cache Memory:CPU와 main memory간의 속도차 보정(즉 고속)
-Main Memory:반도체 기억장치 칩들로 구성, 가격 비싸고 면적 많이 차지, 휘발성, 최근에는 비휘발성 고속 액세스 메모리 SCM(Storage Class Memory)가 있음)
-Auxiliary Storage Device:저속 액세스, 저장밀도 높음, 비휘발성
I/O device:각 I/O device는 사용 data 다르고 명령어도 달라서 CPU와 직접 연결 안하고 각 I/O device별로 제어기(controller)가 있음
제어기
-상태 레지스터:I/O 장치의 현재 상태를 나타내는 비트들을 저장하는 레지스터로 준비 상태 비트, 데이터 전송확인 비트 등을 저장하는 레지스터
-데이터 레지스터:CPU와 I/O장치 사이 이동되는 데이터를 일시적으로 저장하는 레지스터, 데이터 버퍼라고도 불림
System Bus:CPU와 다른 요소들 정보 교환 통로
-Address Bus:CPU가 다른 요소들에게 주소 정보를 쏘는 통로, 일방통행
-Data Bus:CPU가 I/O장치와 데이터 전송 통로, 쌍방향
-Control Bus:제어신호선들의 집합, 일방통행, 제어신호(memory read/write, I/O read/write)
메모리 영역을 Command와 Data를 공유해서 사용 여부로 나눈 컴퓨터 구조
폰노이만 아키텍처(Von Neumann Architecture)
-하나의 메모리에 Command와 Data가 모두 저장, CPU는 한 번에 하나의 명령어만 실행가능(SISD:Single Instruction Single Data)
-명령어 처리 순서:fetch(CPU에 명령어 전달)->decode->execute->stored
-병목현상(Command읽을 때 Data못 읽음) 발생
-상대적으로 빠른 CPU의 속도를 효율적으로 사용안함
-Stored Programed 방식의 메모리 중심 구조(Stored Program:고수준 프로그래밍 언어(C 등)로 작성->컴파일->기계어 방식)
-고성능 CPU에 사용, 특히 인텔
-Cache Memory의 크기, CPU Prediction 알고리즘 등에 따라 성능 차이 큼
-저비용 소형 MCU(Micro Controller Unit, 집적 회로 안에 프로세서와 메모리, 입출력 버스 등 최소한의 컴퓨팅 요소를 내장한 초소형 컨트롤러)에 유리
하버드 아키텍처(Harvard Architecture)
-서로 다른 메모리에 Command와 Data를 각각 저장
-병목현상 없음(Command 읽기, 쓰기 병행 가능)
-하버드 마크 I의 릴레이를 사용한 극히 작은 메모리 영역으로 인한 버스 분리가 가능한 구조
-Harvard Architecture + RISC(Reduced Instruction Set Computer, ~~~)으로 성능향상
-임베디드 소형 프로세서에 사용, 특히 ARM(ARM Holdings에서 설계하는 Command set와 ISA(Instruction Set Architecture)의 총칭)계열에 사용
-2010년 이후 스마트폰이 대세->스마트폰의 CPU인 AP(Application Processor)가 확산->ARM 및 하버드 아키텍처 유명해짐
-고성능 DSP(Digital Signal Processor, 디지털 신호 처리를 위해 특별히 제작된 micro processor)개발에 유리
폰노이만 아키텍처의 문제점 해결방안
-병렬처리개념 도입(병렬처리기법(Pipeline, Super Pipeline, Super Scalar, VLIW(Very Long Instruction Word), EPIC(Explicitly Parallel Instruction Computing))
-Pipeline(한 데이터 처리 단계의 출력이 다음 단계의 입력으로 이어지는 형태로 연결된 구조, 각 단계 사이의 입출력을 중계하기 위해 버퍼가 사용될 수 있다.)
-Super Pipeline(파이프라인의 일종, 어떤 동작이 실행될 때, 그 클럭을 나누어서 다음 명령어에 대한 동작을 수행한다. 클럭이 높아짐에 따라서 나누기가 힘들어져서 잘사용안함)
(클럭(Clock):컴퓨터의 CPU 또는 디지털 회로가 일정한 속도로 작동하기 위해서는 일정한 간격으로 전기적 진동(pulse)을 공급받아야 하는데, 이 전기적 진동을 클럭이라 한다. 클럭 스피드는 Hz를 이용, 4.2GHz라 하면 초당 42억번의 사이클로 0과 1의 디지털 신호를 발생시킨다는 것을 의미, I7-7700k가 4.2GHz)
(순차회로/로직(Sequential Circuit/Logic):현재의 입력 뿐 아니라 과거의 입력 혹은 출력 값들도 함께 고려하여 현재의 출력값을 결정하는 논리회로이다, 조합회로와 기억 소자(memory element)들로 구성)
(논리회로(Logic Circuit):부울 대수(Boolean Algebra)를 이용하여 1개 이상의 논리 입력을 일정한 논리 연상에 의해 1개의 논리 출력을 얻는 회로)
(조합회로/로직(Combinational Circuit/Logic):현재 입력에만 의존하여 출력이 결정되는 논리 회로)
(기억 소자(Memory Element/Cell):기억 장치의 가장 최소 단위. 보통 한 비트를 기억할 수 있는 플립플롭이나 자기 코어, 축전기 하나를 가리킨다.)
(플립플롭(Flip-Flop) or 래치(latch):1비트의 정보를 보관, 유지할 수 있는 회로이며 순차 회로의 기본 요소이다.)
-Super Scalar(Pipeline을 여러 개 두어 명령어를 동시에 실행하는 기술, 동시에 처리(투입/완료)가 가능한 명령어 개수(N)에 따라 N-issue, N-wide, N-way super scalar로 불린다.)
-VLIW(Very Long Instruction Word, 여러 opcode 필드가 있는 긴 명령어 하나에 독립적인 연산 여러개를 정의하고 이들을 한꺼번에 내보내는 명령어 구조 집합의 종류이다.)
(opcode, operation code:연산(operation)종류를 나타내기 위한 코드, 즉 덧셈을 ADD, 제곱근을 SQR 등으로 기억에 편리하도록 기호화한 것을 가리킨다.)
-EPIC(Explicitly Parallel Instruction Computing, 사용자의 컴파일러가 소스 코드로부터 병렬성을 찾아내고 병렬처리용 기계어 코드를 생성하여 수행하는 방식, VLIW 방식에 기반을 둠)
-병렬처리개념 도입(멀티프로세서(SMP(Symmetric Multi Processor), MPP(Massively Parallel Processor))
-SMP(Symmetric Multi Processor, 두 개 이상의 프로세서가 한 개의 공유된 메모리를 사용하는 멀티 프로세서 컴퓨터 아키텍처)
-MPP(Massively Parallel Processor, 두 개 이상의 프로세서가 각각 전용의 메모리를 사용하는 멀티 프로세서 컴퓨터 아키텍처)
-Main Memory 병목 해결
-버스분리(명령어와 데이터용 버스 분리)
-CPU에 Memory Controller를 내장
-Cache Memory를 계층적으로 구성(Intel의 L1/L2/L3 캐시 구성)
-L1/L2/L3란, L은 Level을 가리키고, CPU가 L1확인하고 없으면 L2를 확인, L3는 멀티 코어 CPU에서 각 코어와 L2 캐시 사이의 버퍼역할
(L1은 Command Cache와 Data Cache로 나누어져있음, L2는 나누어져 있지 않음)
(코어:CPU에서 다이(die, 실리콘 위에 반도체 회로를 만들어서 사각형으로 잘라낸 것, CPU의 밑판)에서 Cache Memory를 제외한 회로부분)
-구조적 해결:최근에는 CPU<->Cache Memory는 하버드 아키텍처, CPU<->Main Memory는 폰노이만 아키텍처를 통해 병목현상을 개선하여 사용)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
자료구조
배열(Array)
-데이터가 많아서 그룹핑(grouping)을 해야할 필요가 있을 때 사용한다.
-배열의 구성요소
배열생성
배열의 index
value
element(index+value 합쳐서 element라 함)
-주로 사용하는 기능
-반복문
-Java에서 사용법
-생성
int[] numbers1 = new int[4];
element의 자료형, []은 배열임을 표시, 배열의 이름, = new(객체생성키워드), int[4](배열의 크기 지정
String[] strings = new String[4];
-배열에 데이터 입력
numbers1[0]=10;
numbers1[1]=20;
numbers1[2]=30;
(아무것도 입력안한 numbers1[3]에는 처음 생성시 디폴트값으로 0이 들어가있다. 만약 배열의 자료형이 객체였다면 디폴트로 null이 들어감)
-배열의 생성과 입력을 한번에 해결하기(배열의 생성시점에 배열에 들어갈 values를 이미 알 때 주로 사용)
int[] number2 = {10, 20, 30, 40};
int[] number3 = new int[]{10, 20, 30, 40};
-배열의 값을 가져오기(get)
System.out.println(number1[0]); //10이 나옴
System.out.println(numbers1[3]); //0이 나옴
-배열의 크기(size)가져오기
System.out.println(numbers1.length); //4가 나옴(element의 개수가 나옴, 값을 지정한 개수가 나오는게 아니다.)
-배열과 반복문(Iteration)
int i = 0;
while(number1.length > i){
System.out.println(number1[i]);
i++;
}
(while문의 단점은 int i = 0;과 조건문 그리고 반복문 의 i들이 멀리 떨어져있을 수 있어서 가독성이 떨어지고 중간에 버그가 있을 수 있다.)
(그럴땐 for문을 사용)
for(i=0;numbers1.length > i;i++){
System.out.println(numbers1[i]);
}
-배열의 단점
-크기가 정해져있어서, 데이터를 추가해야할 때 오류가 발생한다.
-기능이 없다.
-배열의 장점
-크기가 정해있어서, 작고 가볍고 단순하다.
-기능이 없다. 그래서 이후에 부품으로 이용되기가 좋다.
리스트(List)
중요 키워드:순서, 중복허용
array와 list
array도 순서와 중복허용 둘 다 가능하다
list가 array보다 기능이 더 많다.
array는 주소(index)가 중요
list는 A다음에 B가, B다음에 C가, 등 순서가 더 중요하다
데이터를 추가할 때의 array와 list의 차이가 두드러진다.
array는 덮어쓰기
list는 정말 추가가 가능, 기존 데이터는 한칸씩 밀려난다.
데이터를 삭제할 때는
array는 그 index의 데이터가 사라지지만 그 공간은 남아 있고 비어있게 된다
list는 그 index의 데이터가 사라짐과 공간도 사라지고, 그 이후의 element가 앞당겨오게 된다.
즉 list는 비어있는 데이터가 없다. 따라서 데이터 삭제를 한 이후에도 반복문 사용시 데이터의 유무를 판단하지 않아도 되며, 빈 데이터가 없으므로 메모리를 덜 차지하게 된다.
list의 기능
처음, 끝, 중간에 element를 추가/삭제하는 기능
모든 데이터에 접근할 수 있는 기능
데이터의 존재유무를 판단할 수 있는 기능
언어별 특징(데이터 스트럭쳐는 언어마다 다르지만, 본질적 개념을 알아야 한다.)
C에서는 list가 없다, 자신이 만들거나 다른 사람이 만든 것을 가져와서 사용함
JavaScript에서는 list가 있다.
ex)
numbers = [10, 20, 30, 40, 50];
numbers.splice(3,1); //numbers라는 array의 index 3에서부터 1개의 데이터를 삭제하라(splice)
(그러면 위에 설명한 list에서처럼 삭제하고 한칸씩 앞당겨온다. 따라서 JavaScript에서는 array가 list처럼 동작하는 부분이 있다는 것을 알 수 있다.)
Python에서는 array가 기본적으론 없고 list가 기본적으로 제공됨
ex)
numbers = [10, 20, 30, 40, 50]; //5개의 element를 갖고 있는 list
numbers.pop(3); // index 3에 해당하는 40이란 data를 삭제하고 뒤 데이터를 한칸씩 앞으로 당김
numbers[0]; //0번째 데이터에 접근 가능
(Python에서는 list가 array처럼 활용되기도 한다(number[0]보면은))
Java에서는 array와 list가 각기 다른 문법으로 제공된다.
int[] numbers = {10, 20, 30, 40, 50}; //array
ArrayList numbers = new ArrayList();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
numbers.remove(3); // 40을 제거하고 밀려서 10,20,30,50이 됨
(Java에서는 array와 list가 모두 지원)
LikedList, ArrayList, 2가지의 list를 지원한다.
ArrayList는 데이터의 추가/삭제가 느리지만 인덱스 조회는 빠르다.
LikedList는 인덱스 조회는 느리지만 데이터의 추가/삭제가 빠르다.
(따라서 개발자가 장단점을 생각해서 사용하게끔 해줌)
ArrayList는 Array를 이용하여 List를 만든다.
데이터를 추가할 때, 그 위치의 데이터의 오른쪽에 있는 모든 데이터를 오른쪽으로 1칸씩 미리 옮긴다음에 추가한다.
데이터를 삭제할 때는, 바로 삭제후 그 이후 데이터를 왼쪽으로 한칸씩 모두 옮겨주어야 한다.
index를 이용해서 데이터를 가져오기(get)가 굉장히 효율적이다.
size라는 것을 이용해서 ArrayList의 데이터의 개수(size)를 쉽게 알 수 있다.
장점:
데이터의 가져오기가 빠르다.
단점:
데이터의 추가/삭제가 오래걸린다.(비효율적이다.)
예제)(ArrayList의 생성, 데이터 추가/삭제, size, 데이터 조회, 반복문)
import java.util.ArrayList; //import를 먼저 하고 사용해야 한다. ArrayList는 java.util 패키지에 있다.
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>(); //<>이란 generic을 사용하여 ArrayList 내에 있을 데이터의 자료형을 미리 지정해서 만들 수가 있다.//
numbers.add(10); //데이터의 추가(insert)
numbers.add(20);
numbers.add(30);
numbers.add(40); //[10, 20, 30, 40]이 된다.
numbers.add(1,50); //numbers내의 index 1의 위치 오른쪽것을 모두 오른쪽으로 이동후 1의 위치에 50을 끼워넣게 된다. [10, 50, 20, 30, 40]이 나옴
numbers.remove(2); // numbers내의 index 2의 데이터를 삭제후 오른쪽 데이터를 모두 왼쪽으로 옮긴다. [10, 50, 30, 40]이 나옴
numbers.get(2); // numbers내의 index 2의 데이터를 가져온다.
numbers.size(); // numbers의 size가 나온다.
Iterator it = numbers.iterator(); // Iterator란 interface를 사용
while(it.hasNext()){
int value = (int)it.next();
if(value == 30){
it.remove();
}
System.out.println(value);
}
}
//혹은 다음 방법도 가능//
for(int value : numbers){ //numbers의 값들을 하나씩 value에 넣어 처리 가능
System.out.println(value);
}
for(int i=0; i < numbers.size(), i++){
System.out.println(numbers.get(i));
}
}
}
예제)(ArrayList의 객체 생성하기)
new->package
new->class(객체 실행을 위해, public main void체크해서)Main만들기
new->class(ArrayList)
Main.java에 들어가서
ArrayList numbers = new ArrayList(); // instance를 만듦
numbers.addLast(10); // 가장 마지막에 10을 추가
numbers.addLast(20);
numbers.addLast(30);
numbers.addLast(40);
ArrayList.java에 들어가서
public class ArrayList {
private int size = 0; // ArrayList의 size를 측정하기위해 변수 정의
private Object[] elementData = new Object[100]; //private으로 이 내부에서만 사용하게, 이해하기 쉬운 Object형을 사용, 100개의 데이터만을 수용할 수 있게 만듦, 실제 자바내 있는 collection primework?에 있는 것은 ArrayList가 크기가 유동적임//
public boolean addLast(Object element){ // 가장 마지막에 데이터를 추가할 메소드(함수)를 만들기
elementData[size] = element;
size++;
return true;
------------------------------------------------------------------------------------------------------------------------------------------------------------
다시 정리
1. 언어랑은 상관없이
2. 각 자료 구조 형태마다의 특징을 정리, 그 '구조'를 써야하는 적절한 예제를 함께 정리한다.
1. Array, 배열
배열의 구성 요소:index, value, element(index+value를 함께 element라 한다.)
사용하는 상황:반복문
장점:배열의 크기가 정해져 있어서 작고 가볍고 단순하다.
단점:배열의 크기가 정해져있어서 데이터를 추가할 때 오류가 발생한다.
2. List, 리스트
리스트는 Order가 중요하다.
-데이터를 추가할 때 Array는 덮어쓰기, List는 끼워넣기(이후 데이터는 한칸씩 밀려난다.)
-데이터를 삭제할 때 Array는 그 index의 value가 사라지지만 그 공간은 남아 있고 비어있게 된다. List는 그 index의 value가 사라짐과 함께 공간도 사라지고, 그 이후의 element가 앞당겨 온다. 따라서 List는 비어있는 데이터가 없으며 삭제를 한 이후에도 반복문 사용시 데이터의 존재유무를 판단하지 않아도 되며, 빈 데이터가 없으므로 메모리를 덜 차지하게 된다.
ArrayList
-사용하는 상황:데이터 조회(index 조회)가 자주일어나되 처음/중간/끝 등에 데이터를 추가/삭제는 자주 하지 않는 상황(전자가 빠르고 후자는 느리기때문에)
-데이터를 추가/삭제를 생각하면 나머지 우측 데이터들의 한칸씩 이동이 걸리기 때문에 ArrayList는 데이터를 추가/삭제를 자주하는 경우에는 사용을 기피
-메모리상에 데이터들이 연속적으로 붙어 있음
Linked List
-Linked List의 구성요소:HEAD+data field+link field(link field는 다음 node가 무엇인지에 대한 정보를 갖고 있음, 따라서 HEAD(첫번째 node가 무엇인지에 대한 정보를 갖고 있음)
-사용하는 상황:처음/중간/끝 등에 데이터를 추가/삭제가 자주일어나는 상황, 데이터 조회(index 조회)는 자주 하지 않는 상황
-데이터 조회할 때 메모리를 일일이 찾아 HEAD를 찾아야하기때문에 데이터 조회에는 느린 속도를 갖는다.
-데이터를 추가/삭제시 메모리상에 임의의 위치에 추가/삭제 하고 기존의 link field만 수정하는 형태이므로 데이터를 추가/삭제는 빠른편이다.(ArrayList에 비해)
-메모리상에 데이터들이 흩어져있지만 연결되어 있음(link field 정보)
Doubly Linked List
-Linked List에서 link field가 양방향으로 확장된 형태(Previous link field와 Next link field가 있는 형태)
-사용하는 상황:데이터 조회시 크기의 절반보다 큰 index를 자주 조회하는 경우이면서 데이터를 추가/삭제가 자주 있는 상황
-메모리를 Linked List보다 더 많이 사용한다.
-Linked List보다 조금 더 복잡하다
정리 1.
Array:데이터의 크기가 정해져있고 수정이 없고 가벼운 형태
ArrayList:데이터의 추가/삭제가 빈번하지 않고 조회가 주로 이뤄질 때
Linked List:데이터의 추가/삭제가 빈번하고 조회는 비교적 적게 할 때
Doubly Linked List:데이터의 추가/삭제가 빈번하면서 조회가 앞 뒤로 양방향이 자주 일어날 때
3. Stack, 스택
한쪽 끝(top)에서만 삽입(push)과 제거(pop, 정확하게는 출력하면서 제거)가 일어남, LIFO(Last-In-First-Out), 스택은 엘리베이터!, peek은 pop과 유사하지만, 출력만 하고 제거는 하지 않음
구현은 Array를 이용하거나 Linked List를 이용한다.
Array를 이용하는 경우, 스택을 위한 배열을 하나 잡고, index 값을 0으로 잡는다. index가 0이면 스택이 비어있는 것, 스택에 뭔가를 집어넣을 때는 Index의 자리에 집어넣고 index를 하나 올린다. index가 초기 배열 크기 이상이면 스택이 꽉 찬 것, 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.
사용하는 상황:
연산 구현시 stack(아래 함수의 호출 참고)
함수의 호출에 관여, 기본적으로 함수 f를 호출하면 먼저 f가 받는 인수들이 push되고 그다음 f가 리턴값을 받을 공간이 push된다. 그다음 f에 해당하는 stack frame이 할당 되고 그 stack frame내부에 f의 내부 변수들이 push된다. 이후 f에 해당하는 연산이 종료되고 f의 stack frame 내부의 값들이 빠져나오면서 최종적으로 리턴값을 받기 위한 공간으로 들어오게 된다.
f를 호출한 상황에서 다른 함수 g를 호출하는 상황을 생각하면, 스택내부에 스택이 또 쌓이는 것이다. 이 개념을 이해하면 recursion이 연산속도에서 불리한 점이 이해된다. recursion할 때마다 스택을 자꾸 쌓아서, 결국 최종값을 얻기 위해서는 쌓인 스택을 전부 다시 빼내야하기 때문이다. 따라서 recursion을 쓰기 전, recursion이 필요한지 설계를 먼저 정확히 이해하는 것이 필요하다.
4. Queue, 큐
한쪽 끝에서는 삽입/제거만 일어나고 다른쪽 끝에는 제거/삽입만 일어남
제거 되는 곳을 Front, 삽입되는 곳을 Rear라고 함, FIFO(First-In-First-Out)
배열의 양끝이 맞물린 것처럼 가정하여 구현
사용하는 상황:CPU 스케쥴링, 디스크 스케쥴링, 버퍼(buffer)로 producer, consumer 사이의 완충 역할, 트리 및 이진트리의 레벨순서(level-order) 방문(탐색) 및 그래프의 너비우선(breadth-first) 방문(탐색)
5. Tree, 트리
6. Graph, 그래프
Directed Graph, 유향그래프
Undirected Graph, 무향그래프
7. Set, 집합
알고리즘
시간 복잡도(time complexity)
실행 시간은 실행환경에 따라 달라진다.(하드웨어, 운영체제, 언어, 컴파일러 등)
따라서 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트
연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐
최악의 경우의 시간 복잡도 (worse-case analysis)
평균 시간 복잡도 (average-case analysis)
점근적 분석(Asymptotic analysis)
데이터의 개수 n->inf일 때 수행시간이 증가하는 growth rate로 시간 복잡도를 표현하는 기법
유일한 분석법도 아니고 가장 좋은 분석법도 아니지만, 상대적으로 간단하고 알고리즘의 실행환경에 비의존적이어서 많이 사용됨
가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분하다.
Ο 표기법은 upper bound를 표현
Ω 표기법은 lower bound를 표현
Θ 표기법은 upper and lower bound를 표현
이진 검색(Binary Search)와 정렬(Sort)
이진 검색
오름차순으로 미리 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
중앙값을 선택하여 target과 맞는지 비교후
맞으면 끝
중앙값>target이면 중앙값을 새로운 최댓값으로 택한다.
중앙값<target이면 중앙값을 새로운 최솟값으로 택한다.
정렬된 리스트에만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다 Ο(log_2 (n))
순차 검색과 비교하면 순차 검색은 Ο(n)으로 이진 검색이 훨씬 빠르다.
정렬
버블 정렬 혹은 거품 정렬(bubble sort)
가장 왼쪽(l)과 인접한 오른쪽(r)과 비교후 l>r이면 l<->r
이후 2번째 원소와 3번째 원소를 비교후 같은 방법
한차례 지나고나서 다시 또 한다. (다만 첫포문을 마치고나면 가장 오른쪽엔 가장 큰것이 이미 와있으므로 두번째 포문부터는 n-1까지만 하면된다.)
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)
삽입 정렬(Insertion sort)
index 1의 데이터를 0과 비교해 제자리에 둔다
index 2의 데이터를 0과 1과 비교해 제자리에 둔다.
...
index k의 데이터를 0~k-1까지의 데이터와 비교해 제자리(맞는 자리에) 둔다.
시간 복잡도가 최선/평균/최악=Ο(n)/Ο(n^2)/Ο(n^2)이다.
기타 정렬
퀵소트(quicksort)
합병(merger sort)
힙(heap sort)
등이 있다.
*code review부터 다시보고 정리
순환(Recursion)
순환(재귀함수)이란, 자기 자신을 호출하는 함수(메소드)를 가리킨다.
순환이 무한루프에 빠지지 않기 위한 조건이 있다.
적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. 이것을 base case라 한다.
recursion을 반복하다보면 결국 base case로 수렴하게 recursive case를 둬야 한다.
가능하면 암시적(implict) 매개변수를 명시적(explicit)매개변수로 표현하라.
예제)(Hello를 n번 출력하는 형태)
public class Code02 {
public static void main(String [] args) {
int n = 4;
func(n);
}
public static void func(int k) {
if (k<=0) // base case
return;
else {
System.out.println("Hello");
func(k-1); //recursive case
}
}
}
예제)(n까지의 합을 출력하는 형태)
public class Code03 {
public static void main(String [] args) {
int result = func(4);
}
public static int func(int n) {
if (n==0)
return 0;
else
return n + func(n-1);
}
}
예제)(실수 x의 n승 구하기)
public static double power(double x, int n) {
if (n==0)
return 1;
else
return x*power(x, n-1);
}
예제(피보나치 수열 구하기)
public int fibonacci(int) {
if (n<2)
return n; // f_0 =0, f_1 =1인 피보나치의 경우
else
return fibonacci(n-1) + fibonacci(n-2);
}
예제(Euclid algorithm을 이용한 최대공약수 구하는 예제)
public static double gcd(int m, int n) {
if (m<n) {
int tmp = m;
m = n;
n = tmp; // swap m and n(즉 항상 first argument가 더 크거나 같게)
}
if (m%n == 0)
return n;
else
return gcd(n, m%n);
}
예제(Euclid algorithm을 이용한 최대공약수 구하는 더 간단한 예제)
public static int gcd(int p, int q) {
if ( q==0 )
return p;
else
return gcd(q, p%q);
}
수학함수뿐 아니라 다른 많은 문제들을 순환을 이용하여 해결할 수 있다. 특히 for문, while문을 대신할 수 있다.
순환<->반복문(즉 모든 반복문도 순환으로 만들 수 있다.)
순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
하지만 함수 호출에 따른 오버해드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등), 즉 순환은 프로그래밍 실행 속도에 단점이 있긴 있다.
예제(문자열의 길이 계산)
public static int length(String str) {
if (str.equals(""))
return 0;
else
return 1 + length(str.substring(1)); // str.substring(1)이란 str의 첫번째 문자를 제거한 substring을 가리킨다.
}
예제(문자열의 출력)
public static void printChars(String str) {
if (str.length() == 0)
return;
else {
System.out.print(str.charAt(0)); // str.charAt(0)란, str의 첫 문자를 리턴하는 메소드이다.
printChars(str.substring(1));
}
}
예제(문자열을 순서를 뒤집어 프린트)
public static void printCharsReverse(String str) {
if (str.length() == 0)
return;
else {
printCharsReverse(str.substring(1));
System.out.print(str.charAt(0));
}
}
(문자열의 출력 예제와 달라진 것은 else내에 출력과 호출의 순서만 바꼈을 뿐이다.)
예제(자연수를 2진수로 변환하여 출력)
public void printInBinary(int n) {
if (n<2)
System.out.print(n);
else {
printInBinary(n/2);
System.out.print(n%2);
}
}
예제(정수 배열(Array)의 합 구하기, data[0]에서 data[n-1]까지의 합)
public static int sum(int n, int [] data) {
if (n<=0)
return 0;
else
return sum(n-1, data) + data[n-1];
}
}
암시적(implicit)매개변수를 명시적(explicit)매개변수로 바꾸어라.
예제(순차 탐색, sequential search)
int search(int [] data, int n, int target) {
for (int i=0; i<n ; i++)
if (data[i]==target)
return i;
return -1;
}
(여기서 n은 명시적인데, search의 시작 인덱스인 0은 암시적 매개변수이다. 하지만 순환을 사용시 시작인덱스도 명시적으로 하자.)
예제(순차 탐색, 매개변수의 명시화)
int search(int [] data, int begin, int end, int target) {
if (begin > end)
return -1;
else if (target==data[begin])
return begin;
else
return search(data, begin+1, end, target);
}
(이렇게 시작 index를 begin으로 명시화하자. search(data, begin, end, target)으로하면 begin index부터 end index까지 target이 있는지 확인)
예제(최대값 찾기)
int findMax(int [] data, int begin, int end) {
if (begin==end)
return data[begin];
else
return Math.max(data[begin], findMaxt(data, begin+1, end));
}
예제(이진 검색, binary search)
public static int binarySearch(String[] items, String target, int begin, int end) {
if (begin>end)
return -1;
else {
int middle = (begin+end)/2;
int compResult = target.compareTo(items[middle]); // string 비교시 자바에서는 compareTo를 사용한다. target이 items[middle]보다 크면 양수, 작으면 음수, 같으면 0을 return한다. //
if (compResult == 0)
return middle;
else if (compResult < 0)
return binarySearch(items, target, begin, middle-1);
else
return binarySearch(items, target, middle+1, end);
}
}
예제(미로찾기)
Recursive한 생각
현재 위치에서 출구까지 가는 경로가 있으려면
1) 현재 위치가 출구이거나 혹은
2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
예제(미로찾기의 슈도코드1)
boolean findpath(x,y)
if (x,y) is the exit
return true;
else
mark (x,y) as a visited cell; //visited cell개념을 넣지 않으면 무한 루프에 빠질 수 있다.
for each neighbouring cell (x',y') of (x,y) do
if (x',y') is on the pathway and not visited
if findpath(x',y')
return true;
return false;
예제(미로찾기의 슈도코드2)
boolean findpath(x,y)
if (x,y) is either on the wall or a visited cell
return false;
else if (x,y) is the exit
return true;
else
mark (x,y) as a visited cell;
for each neighbouring cell (x',y') of (x,y) do
if findpath(x',y')
return true;
return false;
예제(미로찾기의 실제 자바 코드)
public class Maze {
private static int N=8;
private static int [][] maze = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 0, 1, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 0, 1, 0, 0},
};
private static final int PATHWAY_COLOUR = 0; // white
private static final int WALL_COLOUR = 1; // blue
private static final int BLOCKED_COLOUR = 2; // red
private static final int PATH_COLOUR = 3; // green
public static boolean findMazePath(int x, int y) {
if (x<0 || y<0 || x>=N || y>=N)
return false;
else if (maze[x][y] != PATHWAY_COLOUR)
return false;
else if (x==N-1 && y==N-1) {
maze[x][y] = PATH_COLOUR;
return true;
}
else {
maze[x][y] = PATH_COLOUR ;
if (findMazePath(x-1,y) || findMazePath(x,y+1) || findMazePath(x+1,y) || findMazePath(x,y-1)) {
return true;
}
maze[x][y] = BLOCKED_COLOUR; // dead end
return false;
}
}
public static void main(String [] args) {
printMaze();
findMazePath(0,0);
printMaze();
}
}
예제(Counting cells in a Blob)
상황:
입력으로 binary image를 받는다. 그리고 하나의 좌표(x,y)도 받는다.
각 픽셀은 background pixel이거나 혹은 image pixel
서로 연결된 image pixel들의 집합을 blob이라고 부름
상하좌우 및 대각방향으로도 연결된 것으로 간주
(x,y)가 image pixel로서 택해졌다면, 그 pixel이 속한 blob의 총 image pixel의 개수를 return하는 문제이다.
(x,y)가 background pixel이면 0을 return
슈도코드:
if (x,y)가 이미지 밖이면
결과는 0
else if (x,y)가 image pixel이 아니거나 already counted면
결과는 0
else
(x,y)를 다른 색(예를 들면 빨강)으로 색칠하라; // 이미 카운트 됐음을 표시
1+(인접한 영역의 count값);
실제 코드
private static int BACKGROUND_COLOR = 0;
private static int IMAGE_COLOR = 1;
private static int ALREADY_COUNTED = 2;
public int countCells(int x, int y) {
if (x<0 || x>=N || y<0 || y>=N)
return 0;
else if (grid[x][y] != IMAGE_COLOR)
return 0;
else {
grid[x][y] = ALREADY_COUNTED;
return 1 + countCells(x-1, y+1) + countCells(x, y+1)
+ countCells(x+1, y+1) + countCells(x-1, y)
+ countCells(x+1, y) + countCells(x-1, y-1)
+ countCells(x, y-1) + countCells(x+1, y-1)
}
}
예제(N-queens problems)
상황:
NxN 체스판에 N개의 말을 놓는다.
이때 각 말은 같은 행, 같은 열, 같은 대각선 상에 놓이지 않게 N개의 말을 놓을 수 있는지?에 대한 대답
Backtracking이용
일련의 선택을 하다가 조건에 부합하지 않게 되면, 그 이전의 선택으로 거슬러 올라가 번복하는 방법
각 행에는 1개의 말만 올 수 있음을 인지하고
0행에서 (0,0)에 말을 놓은 뒤
1행에서 (1,2)에 말을 놓은 뒤..... 쭉 하다가 안된다는 것을 깨달으면 그 이전의 행에서 놓은 말을 이동시킨다.(열을 증가하는 방향으로)
상태공간트리(State Space Tree)이용
뿌리에 Start를 두고
뿌리와 거리가 1인 노드들에는 0행에 놓일 0번 말의 가능한 좌표를 vertex에 표시하여 둔다
뿌리와 거리가 2인 노드들에는 이전 vertex(좌표)에서 1행에 놓일 1번 말의 가능한 좌표를 vertex에 표시하여 둔다.
.... 반복
해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드sequence에 해당한다. 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음
트리를 탐색하는 기법들
깊이 우선 탐색, (이후에 정확한 정의를 파악), 일단 위의 예제에서 backtracking을 상태공간트리에 적용하면 그게 깊이 우선 탐색
실제코드(recursion과 stack을 사용할 수도 있다. 아래는 recursion을 이용한 코드이다.)
int [] cols = new int [N+1]; // 매개변수 level은 현재 노드의 level(트리의 root에서 떨어진 길이)을 표현, cols[i]=j 는 i번째 말이 (i행,j열)에 놓였음을 의미
boolean queens(int level) { // 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정, level을 넣음으로써 정확한 위치는 아니지만 몇행인지는 앎
if (!promising(level))
return false;
else if (level==N) { // level이 N인데 promising(level)이 true가 나왔으니까 끝난것
for (int i=1 ; i<=N ; i++)
System.out.println("(" + i + ", " + cols[i] + ")");
return true;
}
for (int i=1 ; i<=N ; i++) {
cols[level+1] = i;
if (queens(level+1))
return true;
}
return false;
}
boolean promising(int level) {
for (int i=1 ; i<level ; i++) {
if (cols[i]==cols[level]) // level번째 말이 이전의 말들과 같은 열에 있는 경우를 검사
return false;
else if (level - i==Math.abs(cols[level] - cols[i]) // level번째 말이 이전의 말들의 영향받는 대각선에 있는 경우를 검사
return false;
}
return true;
}
(실제 사용시 queens(0)으로 호출하면 된다.)
(이해를 하기위해 queens(0)을 생각해보기)
예제(powerset 출력하기)
상황:
주어진 집합의 모든 부분집합을 출력하는 문제
전략:
만약 {a,b,c,d,e,f}라면
a를 포함하지 않는 부분집합을 나열한 후,
각각의 부분집합마다 a를 포함시켜 나열하면 된다.
(b를 포함하지 않는){c,d,e,f}의 모든 부분집합들에 a를 추가한 집합들을 나열하고
(b를 포함하는){c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열
....
즉 recursion을 해나간다.
powerSet이란 함수를 설정하는데에 있어서 argument를 집합1개만 받게 설정하면 recursion과정에서 각각의 부분집합마다 포함시켜 나열하는 경우가 해결이 안된다.
실제 코드:
private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
private static int n=data.length;
private static boolean [] include = new boolean [n];
public static void powerSet(int k) { // k와 include를 통해 상태공간트리에서 현재 위치를 알려주는 것이다.
if (k==n) { // 상태공간 트리에서 현재위치가 가장 밑인 경우
for (int i=0 ; i<n ; i++)
if (include[i]) System.out.print(data[i] + " "); // P를 출력
System.out.println();
return;
}
include[k]=false; // data[k]를 포함하지 않는 경우
powerSet(k+1);
include[k]=true; // data[k]를 포함하는 경우
powerSet(k+1);
}
(data[k], ..., data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0,...,k-1인 원소를 추가하여 출력하라는 mission)
(처음 이 함수를 호출할 때는 powerSet(0)로 호출한다.)
상태공간트리 활용
해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리
트리의 모든 노드들을 방문하면 해를 찾을 수 있다.
루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.
k=0일땐 공집합
k=1일땐 공집합이거나 a만 있거나(k=0일때의 집합에 a를 안넣거나 넣거나)
k=2일땐 k=1에서의 각각의 집합에서 b를 넣거나 안 넣거나를 만듦
k=3일땐 k=2에서의 각각의 집합에서 c를 넣거나 안 넣거나를 만듦
정렬
종류:
Simple하고 slow:Bubble sort, Insertion sort, Selection sort,
조금 복잡하지만 fast한:Quick sort, Merge sort, Heap sort,
그 외:Radix sort
기본적인 정렬 algorithm
Selection Sort:
1. 가장 큰 값(M)을 찾는다.
2. 가장 오른쪽 값(R)과 exchange(정렬한다.)
3. 가장 오른쪽 값을 제외하고 1,2를 다시 한다.
시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.
for 루프가 n-1번 반복, 가장 큰 수를 찾기 위한 비교 횟수:n-1, n-2, ..., 2, 1, 그리고 교환은 상수시간
Bubble Sort
1. 첫번째 값과 두번재값과 비교
2. 정렬(교환or유지)한다.
3. 두번째값과 세번째값과 비교
4. 정렬한다.
...반복
결과적으로 가장 큰 값이 가장 오른쪽에 오게 된다.
5. 이후 가장 오른쪽 값을 제외하고 다시 1~4를 한다.
시간복잡도 : O(n^2) = 1부터 n-1까지의 합, 최선/평균/최악 모두 정확히 n(n-1)/2이다.
for 루프가 n-1번 반복, 안쪽 for문이 n-1,n-2,...,1번 반복, 교환은 상수시간 작업
Insertion Sort
1. 첫번째 값에 두번째 값을 끼워 넣는다.
2. 세번째 값을 이전 결과에 끼워 넣는다.
3. 네번째 값을 이전 결과에 끼워 넣는다.
...반복
즉 k-1개가 이미 정렬되어 있고 k번째 item을 끼워넣는 것을 반복하는 것
구체적으로
copy the k번째 item to tmp
k번째 item이랑 k-1번쨰 item이랑 비교, k번째가 k-1번째보다 크면 끝, 작으면 k-1번째 아이템을 오른쪽으로 덮어쓰기(shift),
그리고 k번째 item이랑 k-2번째 item비교,... 이것을 반복
(만약 k번째 item을 k-1, k-2, k-3,...순으로비교할게 아니라, 1,2,3,...으로 비교한다면 대칭이므로 차이가 없어보이지만, 주어진게 배열이라면, 오른쪽에서부터 비교하는, 즉 k-1,k-2,k-3,...순으로 비교하는게 효율적이다. 왜냐하면 대상이 배열이기때문에 결국 k번째 item을 k-1개의 item들 사이에 끼워넣기 위해선, k번째 item보다 큰 녀석들을 결국 오른쪽으로 옮겨야하고, k번째 item보다 큰 값을 가진애들을 한번씩은 접근을 해야하기 때문이다. 즉 1,2,3,...순은 총 k-1개의 데이터를 결국 다 접근해야하는 것이고, k-1,k-2,k-3,... 순은 접근해야할 개수가 k-1개 전체가 되진 않을 수도 있다. 그래서 k-1,k-2,...순으로 비교하는 것이다.)
시간복잡도 : 최악이 O(n^2) = n(n-1)/2, 최선이 O(n) = n-1, 평균도 O(n^2)
for 루프는 n-1번 반복, i번째 item을삽입(Insertion)하는 최악의 경우 i-1번 비교
Merge Sort
Divide and conquer(본질적으론 recursion과 유사)
분할정복법):예전에 로마 제국이 주변 나라를 정복할 때, 전체를 통채로 정복하기 보다는 작은 것으로 분할하여 정복한 것과 유사함
분할:해결하고자 하는 문제를 작은 크기의 "동일한" 문제들로 분할(recursion할 때와 비슷)
정복:각각의 작은 문제를 순환적으로 해결
합병:작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함
Merge sort
데이터가 저장된 배열을 절반으로 나눔
각각을 순환적으로 정렬
정렬된 두 개의 배열을 합쳐 전체를 정렬<<<이게 가장 중요, 관건
9개 데이터있는 1개의 배열이 있다면, 절반으로 나누는 과정을 몇번하면 정렬된 9개의 배열을 갖게 된다.
그리고 다시 2개씩 합쳐주며 merge하는 것이다.
Merge를 하는 방법(a1<a2<a3, b1<b2<b3인 경우)
추가 배열을 만든다.
a1과 b1 중 작은 것을 추가배열의 왼쪽에 둔다.(a1<b1이라하자)
a2과 b1 중 작은 것을 추가배열의 왼쪽에 둔다(a2<b1이라하자)
a3와 b1 중 작은 것을 추가배열의 왼쪽에 둔다(b1<a3이라하자)
...이하 반복
(a배열의 index i, b배열의 index j, 추가배열의 index k중 k는 항상 +1, i는 a가 작을때 +1, j는 b가 작을 때 +1)
(sub배열중 1개가 완료되면 나머지 sub배열을 그대로 가져오면된다.)
알고리즘:
mergeSort(A[], p, r) { // 배열 A[]을 index p에서 index r까지 배열
if (p<r) then {
q = (p+q)/2 ; // p, q의 중간 선택
mergeSort(A, p, q); // 전반부 정렬
mergeSort(A, q+1, r); // 후반부 정렬
merge(A, p, q, r); // 합병
}
}
merge(A[], p, q, r) {
정렬되어 있는 두 배열 A[p,...q]와 A[q+1,...,r]을 합하여 정렬된 하나의 배열 A[p,...,r]을 만든다.
}
(merge부분을 실제 자바 코드로 써보면)
void merge(int data[], int p, int q, int r) {
int i = p; // 앞 배열 index
int j = q+1; // 뒤 배열 index
int k =p; // 도움배열의 index
int tmp[data.length()]; // 도움을 줄 추가배열을 만듦
while(i<=q && j<=r) {
if (data[i] <= data[j]) {
tmp[k++] = data[i++];
}
else {
tmp[k++]=data[j++]; // k는 항상 증가, i,j는 비교해서 작을때만 증가
}
}
while ( i <= q)
tmp[k++]=data[i++]; // 남은 것들 추가로 가져오는 과정
while (j <= r)
tmp[k++]=data[j++]; // 이 2개의 while문 중 1개만 사실 실행됨
for (int i = p ; i<=r ; i++)
data[i] =tmp[i] // 원래 데이터에 도움배열 정보를 넣는 과정
}
Merge Sort의 유일한 단점:추가배열을 잡아둬야한다는 것
시간복잡도:
T(n)
=0 (n=1일때)
=T(ceil(n/2)) + T(floor(n/2)) + n (n>=2) // n은 merge하는데 비교연산의 최대횟수가 n, 사실 ceil, floor는 필요없음, n->inf일때 고려하므로
=O(n*logn))
Quick Sort
마찬가지로 Divide and Conquer
다만, divide가 다름
pivot 선택하기
어떤 값을 pivot을 선택할 지는 나중에 배우기
현재 강의 내용에선 배열의 가장 오른쪽 값을 pivot으로 선택
알고리즘 개요
1. "pivot보다 작은 것, pivot, pivot보다 큰 것"으로 분할(분할하면서 좌, 우가 정렬하지는 않음)
2. pivot 기준으로 나뉘어진 좌, 우의 부분들에 다시 recursion으로 분할
3. "합병"단계가 필요가 없다.
알고리즘
quicksort(A[], p, r) { // A[p,...,r]을 정렬한다.
if (p<r) then {
q=partition(A, p, r);
quicksort(A, p, q-1);
quicksort(A, q+1, r);
}
}
partition(A[], p. r) {
x = A[r]; // pivot넣기
i = p-1 // 작은 애들 index
j = p // 큰 애들 index
for j to r-1 {
if A[j]<=x {
i++;
exchange A[i] and A[j];
}
}
exchange A[i+1] and A[r]
return i+1;
(배열 A[p,...,r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 return한다.)
(작/큰/x로 만든 다음, 큰애들 중 가장 왼쪽인 애를 x와 exchange할 것이다.)
(작은 애들 중 마지막 값 index i, 검사하려는 값 index j, A[j]와 pivot과 비교하여 A[j]가 x보다 같거나 크면 그냥 j++(다음꺼 검사), A[j]가 x보다 작으면 A[j]와 A[i+1]과 exchange하고 i++ 그리고 j++(다음꺼 검사))
(제일 마지막에 i+1과 pivot의 exchange, 그리고 i+1을 return)
}
복잡도
partition 한번 하는데 걸리는 시간은 O(n) // 정확히는 n-1번의 비교연산
T(n)
최악의 경우는 아이러니하게, pivot이 가장 큰 값일 때, 즉 이미 정렬된 배열인 경우이다. (pivot을 항상 가장 오른쪽 값을 갖는 상황이라 한다면)
T(n)
= T(0) + T(n-1) + Θ(n-1) = T(n-1) + Θ(n-1)
= T(n-2) + Θ(n-1) + Θ(n-2)
...
=Θ(1) + Θ(2) + ... + Θ(n-1)
= Θ(n^2)
항상 절반으로 분할되는 경우(최선의 경우)
T(n)
=2*T(n/2) + Θ(n-1)
...
=Θ(n*logn)
항상 한쪽이 적어도 1/9이상이 되도록 분할된다면(편의상 항상 1:9일때를 고려)
T(n)
= T(n/10) + T(9n/10) + Θ(n-1)
...
= k * Θ(n) = Θ(n*logn)
(이때 (9/10)^k * n = 1, k=log_(10/9) n )
(따라서 분할이 아주 극단적으로 일어나지 않는다면, Quick Sort는 빠르다.)
평균 시간 복잡도
A(n) = sum over all input I of size n P(I)*T(I), where P(I):I가 일어날 확률, T(I):I의 시간복잡도
P(I)를 구하기가 힘드므로 가정을 한다. P(I)=1/n!이라 가정(즉, 서로 다른 값을 갖는 배열만 고려)
A(n)
= 2/n * sum from i=0 to i=n-1 {A(i) + Θ(n)} // pivot의 rank가 1,2,.i..,n 일 확률이 각각이 모두 1/n, 그때마다 A(i-1) + A(n-i) + Θ(n)
= Θ(n*logn)
pivot 선택하는 기준
첫번째 값이나 마지막 값을 pivot으로 선택
이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
현실의 데이터는 랜덤하지 않으므로 정렬/거꾸로 정렬 된 데이터가 입력으로 들어올 가능성은 매우 높음
따라서 좋은 방법이라고 할 수 없음
"Median of Three"
첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 pivot으로 선택
최악의 경우 시간 복잡도가 달라지지는 않음, but 현실적인 방법이긴 함
Randomized Quick Sort
pivot을 랜덤하게 선택
no worst case instance(즉 최악의 입력은 없음), but worst case execution(즉 최악의 실행은 가능함)
(다른 방법들은 최악의 입력이 존재하지만, 이 경우는 최악의 입력이 아니라 최악의 주사위(랜덤)에 의해 최악의 실행이 가능)
평균 시간복잡도 Θ(n*logn)
그래프
개체(object)들 간의 이진관계(binary relation)를 표현하는데 사용한다.
vertex의 개수를 n, edge의 개수를 m
undirected graph, directed graph, weighted graph 등이 있다.
별말없으면 simple undirected graph를 다룬다,
그래프의 표현
undirected simple의 경우
인접행렬(Adjacency Matrix)
저장 공간:Ο(n^2)
어떤 v에 인접한 모든 노드 찾기:Ο(n)
어떤 에지 (u,v)가 존재하는지 검사:Ο(1)
Symmetric Matrix가 된다.
인접리스트(Adjacency List)
V집합을 표현하는 하나의 배열과 각 v마다 인접한 정점들의 연결 리스트
노드개수:2m(edge 하나당 2번세니까)
저장 공간:Ο(n+m)
어떤 노트 v에 인접한 모든 노드 찾기:O(d(v)) // d(v)란 degree of v 라 하자
어떤 에지 (u,v)가 존재하는 지 검사:Ο(d(u)) // u에 해당하는 배열에 있는 리스트를 다 읽어봐야 하므로
directed의 경우
인접행렬
비대칭행렬
인접리스트
m개의 노드를 가짐
weighted의 경우
인접행렬
에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장
에지가 없을 때 혹은 대각선
특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서
예:가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 inf, 대각선은 0
예:가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 inf
그래프의 순회(traversal)
모든 v를 방문하는 작업
대표적인 방법
BFS(Breadth-First search, 너비우선순회)
L_0 = {v_0} //출발노드 선택
L_1 = L_0의 모든 이웃 노드들
L_2 = L_1의 이웃들 중에서 L_0에 속하지 않는 노드들
...
L_i = L_(i-1)의 이웃들 중에서 L_(i-2)에 속하지 않는 노드들
(순회 그래프에서의 BFS, 6분40초부터 다시보기)
DFS(Depth-First search, 깊이우선순회)