대엉코딩

1. 삽입정렬(insertion sort) 란?

 - 각 단계 마다 하나의 원소를 그 앞의 원소들과 비교를 해서 자신의 자리를 찾아 가는 것이다.

 - 첫 번째 원소는 처음에는 혼자이므로 그 자체로 정렬된 상태이고 두번째 원소부터 비교를 하며 정렬을 한다

 - 첫번째 와 두번째 원소를 비교를 제대로 했다면 3번째 원소를 정렬 할때는 3번째 원소 앞쪽은 정렬이 되어있는 상태일 것 이다.

 - 그럼 세번째 원소가 이제 자신의 자리를 찾으러 갈 것이고 네번째 원소가 비교를 시작하려 할 때는 앞의 3개의 원소는 정렬된 상태

 - 그리고 비교를 해가면서 원소의 자리가 바뀔 수 있기 때문에 자신의 차례때 배정받은 위치가 최종출력의 위치는 아니다.

2. 최악의 경우 (worst case) 

 - 키 오름차순 정렬을 하고 싶다고 가정했을 때, 계속 키가 제일 작은 사람이 차례대로 들어오는 것이다.

   ( 즉, 입력이 역순으로 정렬되어 있을 때)   -->  Θ(n^2)

3. 평균의 경우 (Average Analysis)

 - 각 자리에 들어갈 확률은 모두 같다고 가정 (1/i+1) -->>내가 원소로 들어갔을 때 그자리도 포함 i+1

 - step i에서 평균 i/2의 연산

 - 평균 분석의 경우 대략 n^2/4 정도 이다. 

4.특징

 - input의 크기가 적을 때에 한정해서 매우 빠르다고 알려져있다.

 - 한번에 잘못된 위치를 하나만 수정할 수 있는 제한적인 조건 내에서는 최적의 알고리즘 이다.

5. 구현 (key값을 그냥 입력받은 int의 수라고 가정하고 , 그냥 vector<int>의 각 index에 해당하는 값을 통한 정렬을 구현)

https://www.acmicpc.net/problem/1764

그냥 모든 경우의 수를 입력 받은 후 (듣지 못하는 사람) 을 보지 못하는 사람을 입력받을 때 

듣지 못하는 사람 전체와 비교를 하면 시간 초과가 뜹니다 (n,m이 무려 500,000이기 때문에 )

그래서 오랜만에 binarysearch를 직접 구현하여 문제를 해결 하였습니다.

그리고 문제에서 사전 순 배열을 원하였으므로 중간에 sort를 사용하시면 됩니다.

https://www.acmicpc.net/problem/1181

정렬에 관련된 문제입니다.

sorting을 하면서 조건을 조금씩만 걸어서 주면 되는 문제이구요

compare 을 선언해서 sort를 하는데 조건으로 사용하였고

같은 문자가 있는경우 생략해서 출력해야 하는데 이는 입력을 받을때나 또는 따로 비교를 해서 제거를 하려 하면

비교를 하는데 있어서 따로 시간을 또 사용해야 할 것 같아서

출력을 할때 비교하여 생략하는 방식으로 구현하였습니다.

https://www.acmicpc.net/problem/16212

기본적인 정렬을 할줄 아는지 물어보기 위한 문제 인듯 싶네요

c++에서 정렬은 

sort(arr.begin(),arr.end()) 이렇게 하고

내림차순, 오름 차순이냐에 따라 greater<int> () 를 파라미터로 추가 해주느냐 마느냐 결정하시면 될 듯 합니다.

https://www.acmicpc.net/problem/11650

- 입력받은 점을 x좌표 우선비교 하고 출력( 같을 경우는 y좌표를 비교하여 순서대로 출력)

- 문제는 매우 간단한데 

- int형 vector array를 선언해서 (2차원 배열 느낌)

- 입력받은 x,y 를 arr[x].push_back(y) 를 하여 일단 x값 대로 for문을 돌다가

- size가 1 일경우 -> 그대로 출력[0]번째(arr[i][0])

- size가 2 이상이면 -> 그 vector array를 sort하여(y값 오름차순 정렬) 순서대로 출력

@@ 비효율적이다...... 더 컴팩트하게 짤 수있을텐데.. 생각해볼게요.... @@