21. 11. 08 자구알

재미난 컴퓨터 이야기

알고리즘

• 문제해결을 위한 절차/ 방법 (여러 동작들의 모음) ex) 테트리스처럼 문제를 순차적으로 해결해 나가는 느낌, 여행가방을 꾸릴 때, 필요한 것을 어떤 순서대로 넣을지 고민하는 것이라고 볼 수 있다
  
• 대표적 알고리즘 - 정렬, 탐색, 재귀 등 (정렬 알고리즘 비교영상 참고)
• 알고리즘마다 풀어가는 방식이 다르고 컴퓨터에서는 항상 절대 우위라는 것은 존재하지 않는다.
• 정렬 알고리즘
  • 선택정렬 → 일단 자리는 정해져 있음. 첫번째 자리에 젤 작은 애를 집어 넣는다. 두번째 자리에 그 다음으로 작은 애 집넣는다. 이걸 배열이 끝날 때까지 반복..
  • 버블정렬 → 현재 배열 요소와 그 다음 배열 요소를 비교한다음, 조건에 걸리면 교환하는 식의 정렬. 배열의 0번 인덱스의 요소와 1번 인덱스의 요소를 비교하고, 그 다음 1번 인덱스의 요소와 2번 인덱스의 요소를 비교한다. 이 과정을 계속하면 정렬이 된다..
  • 삽입정렬 → 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입한다.
  • 병합정렬 → 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다.
  • 퀵정렬 → 제일 빠른걸까? 항상 빠른게 아니고 대체적으로 다른 것보다 그래도 평균이상의 속도를 보여준다해서 퀵정렬이란 이름이 붙음. pivot point라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다. 이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것이다.
• 시간복잡도
  • 알고리즘이 실행되는데 소요되는 시간분석
  • 점근 표기법 (대문자 O 표기법)
• 탐색 알고리즘의 시간복잡도
  • 선형탐색 - O(n) 100개있으면 100번 훑어본다
  • 이진탐색 - O(logn)

자료구조 (Data Structure)

• 자료를 효율적으로 이용할 수 있는 방법론
• 데이터를 구조적으로 표현하는 방식 ex) 테트리스라는 문제를 해결하기 위해 가장 최적화된 모습으로 블럭을 재조립해서 사용할 수 있다. 여행가방을 꾸릴 때, 여행가방에 들어가는 아이템들이 자료라고 생각하면 가장 최적화된 방법으로 넣는 법을 고민하는 것
  

→ 알고리즘과 자료구조는 치맥같은 뗄레야 뗄 수 없는 환상의 궁합..!

→ 적절한 모양의 블럭(자료구조)을 요리조리 돌리고 옮겨(알고리즘)서 테트리스 게임을 클리어!

→ 효율적으로 물건들의 부피를 줄이고(자료구조) 꺼낼 순서에 맞게(알고리즘) 차곡차곡 정리해 넣으면 알차게!

**원시구조**
    - 정수, 실수, 문자 ...
**선형구조**
    - 배열, 연결 리스트, 스택, 큐, 덱
**비선형구조**
    - 트리, 그래프

**물리적구조**
    - 정수, 실수, 문자
    - 배열, 연결리스트
**추상적구조**
    - 스택, 큐, 덱, 트리, 그래프

• 주기억장치(메모리) 공간에 CPU에서 연산을 할 데이터들을 갖고 있겠지? 연산을 하려면 데이터들이 적합한 모양을 갖추고 있어야 함. ex) 사과주스를 만들려면, 사과를 깎고 사과를 적당한 모양으로 소분을 해서 밑처리를 해야한다. 사과라는 원시적인 자료들을 쪼개거나, 조합을해서 나중에 일처리를 하기 용이한 형태로 만들어 놓는게 자료구조의 핵심! → 어떤 데이터들을 우리가 필요로하는 모양들로 제대로 구성해 놓은 것이 자료구조
  
• Array
  • 원시구조처럼 데이터 하나당 하나의 공간을 갖을 수도 있고, 배열처럼 한줄로 있을 수도 있다. 배열은 정해진 공간을 갖고 있다. 정해진 타입만 들어올 수 있음.
  • 한칸 한칸의 크기는 데이터의 크기만큼 지정되어있음, 컴퓨터가 메모리에 100개만큼의 똑같은 크기의 방을 그냥 만들어 놓는 것. 배열을 넣고 빼고 할 때는 방 번호만 알고있으면 가져다 넣고 빼고 할 수 있음.
  • 배열은 가장 간단하고 빠른 자료구조 형태. 컴퓨터가 알아서 찾아감. 크기가 다 똑같으니까~ 하지만, 단점은 배열은 칸의 수가 정해져있어서 데이터의 양에 상관없이 배열의 크기를 마음대로 조정할 수 없다는 것.
• Linked List
  • 하나의 노드에는 다음 노드의 주소값을 갖고있음
  • 이중 연결 리스트는 반은 앞에꺼 반은 다음꺼 주소값을 갖고 있음
  • 원형 연결 리스트는 맨 마지막 노드가 맨 앞 노드의 주소값을 갖고있어서 순환 구조이다.
  • 중간요소를 삭제하거나 추가할 때 자유롭다 (변경되는 주소값만 알려주면 되니까)
  • 단점은 컴퓨터가 찾는 값을 한번에 갈 수 없고 찾고 찾고 찾아서 가야하기 때문
  • 값과 다음 친구의 주소를 저장해야해서 차지하는 리소스가 배열에비해 크다. 그래서 꼭 필요한 경우에만 사용하는게 좋을 듯.

→ 어떤 알고리즘이냐에 따라 배열과 연결리스트를 적절히 선택하여 사용하자!

• 스택
  • 구현체라기보다는 개념이다.
  • 데이터를 차곡차곡 쌓아서 필요할때마다 나중거를 꺼내쓴다.
  • 언제 써봤을까? 웹 브라우저에서 뒤로가기 버튼을 눌렀을 때, 맨 마지막 페이지부터 빠진다.
  • First-In-Last-Out
• 큐
  • First-In-First-Out 선입선출
  • 대기열을 의미한다.
  • 은행을 가도 먼저온 사람이 먼저 일처리를 한다 → 대표적인 큐의 예시
  • 연결리스트로 스택이나 큐를 구현할 수 있다.
• 덱(Double-ended-queue)
  • 큐와 스택을 합쳐놓은 것
  • 큐가 양쪽으로 있다. 위에서도 나가고 들어올 수 있고, 밑에서도 나가고 들어올 수 있다.
• 트리(Tree)
  • root로부터 branch가 파생되어 나가는 것
  • 가계도 같은 모양
  • 부모, 자식간의 관계를 표현하기도 함.
  • 어쨌든 하나의 루트가 있고 거기서 브랜치가 뻗어 나오는데, 선이 서로 겹치지 않는다.
• 그래프
  • 서로 연결된 그물망을 뜻한다.
  • 시작과 끝이라는게 없다. 서로서로 연결될 수 있음.

자료구조들을 코드로 직접 구현해보고 언제 쓸 수 있을지 고민해보자!

참고자료

기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1