- selection sort

- 오른쪽 리스트(정렬 안 된)에서 가장 작은 숫자를 선택하여 왼쪽 리스트(정렬 된)로 이동하는 작업을 반복

- 시간 복잡도 : 




- 코드

void selectionSort(int* list, size) {
    int indexMin, temp;

    for (int i = 0; i < size; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

'Algorithm' 카테고리의 다른 글

알고리즘 - 버블 정렬  (0) 2015.11.12
알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 재귀 호출  (0) 2015.11.12
알고리즘 - 복잡도 분석  (0) 2015.11.12
알고리즘 문제 풀이 주의사항  (0) 2015.11.05
  • 재귀 함수 구현
    1. 기저 파악 (재귀를 멈추는 부분, 끝 조건)
    2. 조건문 파악 (재귀 호출 조건)
    3. 구현

    - 거듭제곱 값, 피보나치 수열, 하노이탑

    - 반복 vs 재귀

     : 상황에 따라 속도가 더 빠른 것을 선택
     : 재귀는 스택오버플로우가 일어날 수 있다.


'Algorithm' 카테고리의 다른 글

알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12
알고리즘 - 복잡도 분석  (0) 2015.11.12
알고리즘 문제 풀이 주의사항  (0) 2015.11.05
C/C++, JAVA 데이터 형식 범위  (0) 2015.11.05
  • 빅오 표기법



    O(1)상수항상 일정한 속도를 가진다.
    O(Log(N))로그N이 증가함에 따라 조금식 시간이 늘어난다.
    O(N)선형N이 증가하면 시간도 일정하게 증가한다.
    O(NLog(N))선형로그N이 2배로 증가하면 실행 시간은 두배 보다 약간 더 많이 늘어 난다.
    O(N^2)평방형N이 증가시 2 제곱만큼 실행 시간이 늘어 난다.(이중 루프 처리시)
    O(2^N)지수형N이 증가할수록 실행 시간은 급격히 늘어 난다.
    O(N!)계승형N이 증가할수록 실행 시간은 졸라 급격히 늘어 난다.(팩토리얼)


  • 표기법

    O(Big-O)

     : 상한, 최악의 경우(Worst Case)를 나타내는 표기법으로 알고리즘 분석에서 가장많이 사용하는 표기법이다.

    Ω(Omega)
     : 하한, 최상의 경우(Best Case)를 나타내는 표기법이다.

    - θ(Theta)
     : 평균의 경우(Average Case)를 나타내는 표기법이다.


'Algorithm' 카테고리의 다른 글

알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12
알고리즘 - 재귀 호출  (0) 2015.11.12
알고리즘 문제 풀이 주의사항  (0) 2015.11.05
C/C++, JAVA 데이터 형식 범위  (0) 2015.11.05
  • 배열을 따로 저장 없이 바로 출력해도 된다. -> 각각을 독립적인 문제로 생각하고 풀면 된다. -> 전체 테스트 케이스를 입력 받은 다음에, 풀지 않아도 된다.

  • 항상 널문자를 염두해두자

  • 아스키코드를 활용하자

  • java와 c자료형 범위가 다르다
    - java
        long: 8byte -> 64bit
    - c:  
        long: 4 byte -> 32bit
        long long: 8 byte -> 64bit

  • 시간복잡도: 1초 1억
    ex. for문 O(N), 이중 for문인 경우 O(N^2)
    * 1초가 걸리는 입력의 크기
    - O(1)
    - O(logN)- O(N) : 1억
    - O(nLogN): 5백만
    - O(N^2) : 1만
    - O(N^3) : 500
    - O(2^N) : 20
    - O(N!): 10

  • dfs는 재귀가 depth가 4000번 이상일 경우 안됨->보통 bfs로 푼다.

  • 한 줄 입력 받기
    - fgets(s, 100, stdin); // cstdio.h header
    - scanf("%[^\n]\n", s); 
    - getline(cin, s); // string header


'Algorithm' 카테고리의 다른 글

알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12
알고리즘 - 재귀 호출  (0) 2015.11.12
알고리즘 - 복잡도 분석  (0) 2015.11.12
C/C++, JAVA 데이터 형식 범위  (0) 2015.11.05
  • C/C++

  • int (unsignedint)

  • __int8 (unsigned__int8)

  • __int16 (unsigned__int16)

  • __int32 (unsigned__int32)

  • __int64 (unsigned__int64)

  • short (unsignedshort)

  • long (unsignedlong)

  • long long (unsignedlonglong)

이름이 두 개의 밑줄(__)로 시작하는 경우 데이터 형식은 비표준입니다.

다음 표에 지정된 범위는 포함-포함입니다.

형식 이름

바이트

기타 이름

값의 범위

int

4

signed

–2,147,483,648 ~ 2,147,483,647

unsigned int

4

unsigned

0 ~ 4,294,967,295

__int8

1

char

-128 ~ 127

unsigned __int8

1

unsigned char

0 ~ 255

__int16

2

short, short int 및 signed short int

–32,768 ~ 32,767

unsigned __int16

2

unsigned short, unsigned short int

0 ~ 65,535

__int32

4

signed, signed int 및 int

–2,147,483,648 ~ 2,147,483,647

unsigned __int32

4

unsigned, unsigned int

0 ~ 4,294,967,295

__int64

9

long long, signed long long

–9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

unsigned __int64

9

unsigned long long

0 ~ 18,446,744,073,709,551,615

bool

1

없음

false 또는 true

char

1

없음

–128~127(기본값)

/J를 사용하여 컴파일하는 경우 0~255

signed char

1

없음

-128 ~ 127

unsigned char

1

없음

0 ~ 255

short

2

short int, signed short int

–32,768 ~ 32,767

unsigned short

2

unsigned short int

0 ~ 65,535

long

4

long int, signed long int

–2,147,483,648 ~ 2,147,483,647

unsigned long

4

unsigned long int

0 ~ 4,294,967,295

long long

9

없음(그러나 __int64와 동일)

–9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

unsigned long long

9

없음(그러나 unsigned __int64와 동일)

0 ~ 18,446,744,073,709,551,615

enum

varies

없음

자세한 내용은 이 문서의 설명을 참조하세요.

float

4

없음

3.4E+/-38(7개의 자릿수)

double

9

없음

1.7E+/-308(15개의 자릿수)

long double

double과 동일

없음

double과 동일

wchar_t

2

__wchar_t

0 ~ 65,535

  • JAVA

종류

 데이터형

 크기(bit)

데이터 표현 범위 

 정수형

 byte

8

-128 ~ 127

 short

16

-32768 ~ 32767

 int

32 

-2147483648 ~ 2147483647 

 long

64

 -9223372036854775808 ~ 9223372036854775807

 실수형

 float

32

1.4E-45 ~ 3.4028235E38 

 double

64

 4.9E-324 ~ 1.7976931348623157E308

 문자형

char

16 

'\u0000' ~ 'uFFFF' (16비트 유니코드 문자 데이터), 0 b~ 65535 

 논리형

 boolean

true 또는 false 


'Algorithm' 카테고리의 다른 글

알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12
알고리즘 - 재귀 호출  (0) 2015.11.12
알고리즘 - 복잡도 분석  (0) 2015.11.12
알고리즘 문제 풀이 주의사항  (0) 2015.11.05

+ Recent posts