대엉코딩

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/1969

문제의 입력과 출력을 명확히 이해한 후

저는 문자열의 배열을 선언하여 (마치 이차원 배열처럼)  (string은 index단위로 접근이 가능하기 때문에)

입력을 받고 출력할 char배열 hamDNA와 그때의 디스턴스 의 합을 나타내는 변수 hmdistancesum을 선언 하였습니다.

전략은 문자열을 하나씩 확인 하는데 한번에 한자리씩 ...

즉 1번째 문자열의 1번째 자리, 2번째 문자열의 1번째 자리, 3번째 문자열의 1번째 자리.....

그 후 1번째 문자열의 2번째 자리, 2번째 문자열의 2번째 자리, 3번째 문자열의 두번째 자리...를 살펴보아

ACGT중 가장 많이 나오는 숫자로 설정해야 해밍디스턴스는 가장 최소가 되므로 그 값을 hamDNA 벡터에 넣어 

주었습니다.

몇개의 조건이 달린 dfs 이용 문제입니다.

while문 안에서 물의 높이를 1씩 증가 시켜가면서 

dfs를 돌려 침수영역을 구하고 기존의 최대 침수 지역을 넘는 수 라면 그 수를 최대침수지역에 넣습니다.

모든 지역이 모두 침수 되었을 경우 break문을 걸어 while문 을 빠져 나오고 

출력을 하였습니다.

(코로나 때문에 학사일정이 너무 정신없어서 간만에 문제를 풀었더니 깔끔하지가 않은 느낌이네요...)

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

- 조건1. 같은 문자끼리 연결한 선이 교차 하지 않아야 한다.

- 조건2. 각 글자를 정확히 한개의 다른위치에 있는 다른글자와 짝지을 수 있다.

- 문제를 읽고 조건을 생각해보다가 스택을 이용하면 편하게 풀수 있다고 생각한 것이

- 스택에 넣어놓고 같은 단어가 들어와서 그 단어와 함께 pop이 되면 그것이 선이 교차하지 않는다는 것으로 생각

- 1. 스택이 비어있으면 삽입

- 2. 스택의 top()과 현재 문자가 같으면 스택을 pop()

- 3. 스택의 top()과 현재 문자가 다르면 그대로 스택에 push()

- 단어 전체를 순회 하는동안 위 과정을 거쳐는데 만약 1번 조건이 만족하지 않는다면 스택에서 빠져나가지

- 못한채로 남아있는 문자들이 있을 것이고 1번은 만족해도 2번이 만족되지 않는다면 홀수개의 문자가 스택에 남아있을

- 것입니다.

- 즉 반복문을 모두 돌았을 떄 스택이 비어있어야 그 단어는 좋은 단어 인것입니다.

<필기>

<코드>

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

- chess 맵을 만들어주고 (흰색 ,검은색) i+j가 홀수 이냐? 짝수 이냐? 로 나누시면 됩니다.

- 그 후 입력을 받으면서 그때그때 counting을 증가시켜주시고

- 출력해주시면 됩니다.

<코드>

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

- 기본적인 dfs 문제입니다. 

- 문제를 읽으면 dfs구나 알 수 있고 처음 접해서 풀기 좋은 문제인 것 같습니다.

- 좌표 기준 때문에 i,j만 조금 신경써서 해주시면 됩니다(문제에 맞추어서)

- 전 항상 몇번 풀어도 좌표 기준 신경 쓰는게 그렇게 짜증나더라는...ㅎ;;;

<필기>

<코드>

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

- 문제에서 요구하는 정렬 조건만 잘 맞춰주면 되는 간단한 문제 !.

- 저는 vector 배열에 age와name을 저장하는 구조체에 whenin 이라는 언제 가입했는지(가입순서)

- 를 초기화 하는 과정에서 i를 넣어놓았고 정렬을 하는 과정에서 나이가 같으면 whenin을 비교하여 정렬하도록 하였습니다.

<코드>

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

- 처음에 생각하면 복잡한데..... 생각을 하다가 하나씩 어떻게 할까 맞춰보면 쉬운 문제....

- 사실 꽤 어려운 문제라고 개인적으로 생각합니다....복잡......

- 짜고 나서 보면 매우 쉽지만....

- 핵심은 일단 입력은 키 순서대로 들어온다는 것을 이용하는것이 가장 중요한 것 같습니다.

- 즉 입력순으로 처리를 하는데 나보다 뒤에 들어오는 사람들은 나보다 큰사람들이라는 것을

- 생각하는것이 중요합니다.

<코드>