exp_blog

1. 선택정렬

• 주어진 데이터 중 최소 값을 찾음
• 해당 최소값을 데이터 맨 앞에 위치한 값과 교체
• 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

2. 패턴 찾기

• data_list = [9,3,2,1]
  • 1회 : 1, 3, 2, 9
  • 2회 : 1, 2, 3, 9
  • 3회 : 1, 2, 3, 9

1. for stand in range(len(data_list) - 1) 로 반복
2. lowest = stand 로 놓고, //기준점이 맨 앞 최소값이니까 
3. for num in range(stand, len(data_list)) stand 이후부터 반복
   • 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
     • lowest = num // 교환 해줌 
4. data_list[num], data_list[lowest] = data_list[lowest], data_list[num]

3. 알고리즘

def Selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand+1, len(data)):
            if(data[lowest]> data[index]):
                lowest = index
            data[lowest], data[stand] = data[stand], data[lowest]
    return data

import random

data_list = random.sample(range(50), 10)
Selection_sort(data_list)

>>[4, 12, 20, 27, 28, 25, 30, 39, 40, 43]

4. 알고리즘 분석

• 반복문이 두 개 O(𝑛2)
  • 실제로 상세하게 계산하면, 𝑛∗(𝑛−1)2

1. 정렬이란?

• 어떤 데이터들이 주어졌을 때, 정해진 순서대로 나열하는 것
• 다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대한 다양한 알고리즘이 고안될 수 있고, 각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석도 이해할 수 있음

2. 버블 정렬(bubble sort)

• 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

## https://visualgo.net/en 사이트에서 보면 쉽게 그림으로 이해할 수 있다. 

3. 패턴 찾기

• 데이터가 4개 일 때 
  • data_list = [1,9.3.2]
    • 1차 로직
      • 1 vs 9 => X
      • 9 vs 3 => [1, 3, 9, 2]
      • 9 vs 2 => [1, 3, 2, 9]
    • 2차 로직
      • 1 vs 3 => X
      • 3 vs 2 => [1, 2, 3, 9]
      • 3 vs 9 => X
    • 3차 로직
      • 1 vs 2 => X
      • 2 vs 3 => X
      • 3 vs 9 => X

==> N 개의 리스트가 있는 경우 N-1 로직을 적용한다

==> 로직을 1번 적용할 때마다, 가장 큰 수가 뒤에서부터 1개씩 결정된다 

==> 로직이 일찍 끝날 수도 있다 

        => 로직을 적용 시,  한 번도 데이터가 교환되지 않는다면 이미 정렬된 상태므로 더 이상 로직을 반복 적용할

             필요가 없다 

==> 로직 한 회 끝날 때 마다 가장 큰 숫자가 뒤에서 1개씩 결정된다

4. 알고리즘

<프로토 타입>
1. for num in range(len(data_list)) 반복
2. swap = false // 교환되어있는지 확인,  false 가 기본값이여야 아래 for문에서 swap 이 멈춰야 알고리즘 종료
3. 반복문 안에서 , for index in range(len(data_list) - num - 1) 를 n-1번 반복해야한다 
    //num 을 빼는 이유는  data_list에서 로직이 돌면 맨 뒤에 가장 큰 값이 고정되기 때문에 
4. 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1]  이면
5. swap 시켜야한다
6. 더이상 swap 되지 않고 false 값이 나오면 break

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

import random

data_list = random.sample(range(50), 20)
bubblesort(data_list)

>>[3, 5, 10, 11, 18, 19, 20, 21, 24, 26, 28, 29, 31, 33, 34, 38, 39, 44, 46, 49]

5. 분석

• 반복문이 두개  :  O(𝑛2)
  • 최악 : 𝑛∗(𝑛−1)2
• 완전 정렬 되어 있으면 최선 : O(n)

1. 합병정렬(n개 수 랜덤 정렬)13,11,7,4,5,9,15,10

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

#include <stdio.h> void mergeSort(int data[], int p, int r); void merge(int data[], int p, int q, int r); int main() {      int data[8] = {13,11,7,4,5,9,15,10} , i;      printf("정렬 전\n");          for(i = 0; i < 8; i++) {          printf("%d ", data[i]);      }     printf("\n\n<<변화과정>>\n");     mergeSort(data, 0, data[i] - 1);          printf("\n정렬 후\n");      for(i = 0; i < 8; i++) {          printf("%d ", data[i]);      }   return 0; }   void merge(int data[], int p, int q, int r) {     int i = p, j = q+1, k = p;     int tmp[8]; // 새 배열     while(i<=q && j<=r) {         if(data[i] <= data[j]) tmp[k++] = data[i++];         else tmp[k++] = data[j++];     }     while(i<=q) tmp[k++] = data[i++];     while(j<=r) tmp[k++] = data[j++];     for(int a = p; a<=r; a++) data[a] = tmp[a];     printf("\n 합병  >>");     for(int x=p;x<=r;x++){       printf("%d ",tmp[x]);                }     }   void mergeSort(int data[], int p, int r) {     int q;     printf("\n 분할 >>");     for(int x=p;x<=r;x++){          printf("%d ",data[x]);       }     if(p<r) {         q = (p+r)/2;         mergeSort(data, p , q);         mergeSort(data, q+1, r);         merge(data, p, q, r);     } } Colored by Color Scripter

cs

<결과>

 

 

 

=> 안정적인 정렬 가능하지만 / 레코드를 배열로 하면 임시공간이 필요하여 공간낭비가 생길 수 있다

===>>> 제자리  (in-place-sort) 해야함

2. 제자리 정렬 종류인 "선택 정렬" 사용 <java>

• 매 루프마다 최소값 또는 최대값을 선택해서 정렬하는 알고리즘
• 비교 기반 정렬 알고리즘
• 안정적이지 않은 정렬(동일한 키 값이 있을 경우 순서가 바뀔 수 있음)
• 최악, 최적, 평균 모두 O(n^2)의 수행시간을 보임
• 제자리 정렬

이 케이스를 나누는 방식은 a, b의 값을 바탕으로 계산한다.

 

<1번 경우>

 위와 같이 계산할 수 있다.

  예를 들어 T(n) = 4*T(n/2) + n 이라면, a = 4, b = 2 이고 log_b a = 2이다. 이때 f(n)의 최고 차항이 1이므로 이 함수의 시간 복잡도는 theta(n^2)가 된다.

 

<2번 경우>

  

 예를 들어 T(n) = 2*T(n/2) + n 이라면, a = 2, b= 2이고 c = 1이다. 따라서 시간 복잡도는 theta(n log n)이다.

 

<3번 경우>

 

예를 들어 T(n) = 2*T(n/3) + n 이라면, log_b a 는 log_3 2 이면서, c는 1이다. 따라서 c > log_b a를 만족한다. 또한 2*(n/3) <= k(n)의 경우 2/3 <= k < 1을 만족하므로 시간 복잡도는 theta(n)가 된다.

 

<풀 수 없는 경우>

사실 저 형태의 시간복잡도가 아닌 함수는 빠르게 해결 할 수 없다. 예를 들어 T(n) = T(n/2) + T(n/4) + n 인 경우

트리 형태로 그려가면서 풀면 공비가 3/4인 등비수열의 합으로 나타낼 수 있다.

또한 멱급수나, 미적분을 해야하는 경우 또한 존재한다

def fibonacci(n):

    answer = [0,1]    #list의 초기값을 0,1로 지정

 

    for i in range(2,n+1):#i= list의 주소를 뜻함

        answer.append(answer[i-1]+answer[i-2])#list에 추가

    #print(answer)  # 피보나치 list를 출력위해

    #print(i)       #리스트 주소가 잘 돌고있는지 확인

    return answer[-1]    #리스트에서 가장 마지막것만 출력해줌

 

$print(fibonacci(30))

832040

초기에 python으로 해결하려 하였으나 실패ㅜㅜ 시간 계산 함수가 따로있다고 하는데 조금 더 찾아보고싶었지만 노타임.. 노열정..

<python 으로 반복문 사용하여 피보나치 계산> -> 아 잘되는데 시간 계산 .....

<java 피보나치 합 /시간 계산>

import java.util.Scanner;
 
public class recursionVsIteration {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        //원하는 숫자 입력
 
        System.out.print("Enter the last element of Fibonacci sequence: ");
 
        long n = sc.nextInt();
 
        //반복문 출력
 
        System.out.println("Fibonacci iteration:");
 
        long start = System.currentTimeMillis();
 
        System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibIteration(n));
 
        System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
 
        //재귀함수 출력
 
        System.out.println("Fibonacci recursion:");
 
        start = System.currentTimeMillis();
 
        System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibRecursion(n));
 
        System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
 
    }
 
    //반복문 method
 
    static long fibIteration(long n) {
 
        long x = 0, y = 1, z = 1;
 
        for (long i = 0; i < n; i++) {
 
            x = y;
 
            y = z;
 
            z = x + y;
 
        }
 
        return x;
 
    }
 
    //재귀 method
 
    static long fibRecursion(long  n) {
 
        if ((n == 1) || (n == 0)) {
 
            return n;
 
        }
 
        return fibRecursion(n - 1) + fi

 

 

 

---

<피보나치 수열>

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 

 

<피보나치 수열의 호출 방법>

1. 재귀 호출 

-함수 호출 횟수가 너무 큼                                                     -> 해결책 : recursive를 한겹만 쓰면 확실히 줄어들 것

-stack 깊이가 너무 깊어져서 컴퓨터 터짐..(stack overhead)-> 해결책 : stack을 쓰되 새로 만들지말고 누적해서 재사용하자

 

-대신 적은 코드 사용해 효율적으로 처리                              -> 종료하는 지점 정의해줬을 때 얘기이다..

 

2. 반복 호출 

- 반복 할 때마다 나온 계산 값을 어딘가에 저장해 두고 그 다음 반복에서는 앞 단계에서 저장된 값에 새로운 값 내용 누적 시킨다.

- 매개변수 리스트 보관(메모리 영역) / 메소드 실행공간(복사 공간) 필요하다

 

3. 꼬리 재귀(tail-recursion)

-재귀가 느려지는 이유(작업 끝마쳐도 해야할 일 남아)를 보완해서 함수의 꼬리 부분에 호출하여 원래 시점으로 돌아갔을 때 해야할 일 이 없게 만드는 호출

 

---

 

-참고 블로그 : https://nittaku.tistory.com/81