대엉코딩

* 이진 탐색 트리?

 - 검색에 많이 사용이 되는 형태입니다.

 - 중위 순회 (Inordered traversal)를 할 경우 key값에 따라 sorting된 결과를 얻을 수 있습니다.

    # 구조 조건

     - 각 노드들은 자식노드를 기껏해야 두 개만을 가질 수 있습니다.

    # 순서 조건

     - 각 노드들의 왼쪽 서브트리에 있는 노드들은 각 노드보다 작은 값을 가집니다.(key)

     - 각 노드들의 오른쪽 서브트리에 있는 노드들은 각 노드보다 큰 값을 가집니다.(key)

    # 중위 순회

구조 조건과 순서 조건을 만족하는 이진탐색트리를 구성(construct) 하였다면

위와 같이 inordered traversal을 하면 key값을 기준으로 정렬이 됩니다.

(30,40,50,55,60,70)

 * 탐색연산(search)

 - root 노드 부터 시작하여 탐색하고자 하는 값 n 과 비교를 하며

   비교하는 노드보다 n값이 작다면 왼쪽 서브트리로 가서 왼쪽 서브트리의 루트노드와 다시 비교.

   비교하는 노드보다 n값이 크다면 오른쪽 서브트리로 가서 오른쪽 서브트리의 루트노드와 다시비교를 하면 됩니다.

* 삽입연산(insert)

 - 삽입연산은 탐색연산과 같이 내려가다가 자기 자리를 찾아서 들어가면 됩니다

 - 위의 저의 예시는 나름 예쁜? 모양이지만 이진탐색트리의 구조 조건과 순서 조건만 만족 하면서 구성해 나가면됩니다.

 - 같은 노드들의 값과 수 여도 다양한 모양의 이진탐색트리가 나올 수 있습니다.

 - 역시나 이와 같은 경우에도 순서와 구조 조건이 모두 맞습니다 --> 중위순회를 하여도 결과가 그대로 나옵니다.

 * 삭제연산(delete)

 - 이진탐색트리는 어떠한 노드를 삭제연산을 수행하여 제거 하여도 그 결과의 트리 역시 이진탐색트리여야 합니다.

    (당연하죠? ㅎ)

 - 두 경우로 나누어서 보겠습니다.

    1.) 삭제하려는 노드의 두 자식노드가 leaf노드인 경우입니다. --->그냥 삭제해버리면 됩니다.

    2.) 삭제하려는 노드의 자식이 하나는 leaf노드이고 한쪽은 서브트리(노드)를 가지는 경우

       - 삭제하려는 노드의 자리에 한쪽 서브트리를 연결 해주면 됩니다.

    3.) 두 자식이 모두 leaf노드가 아닌 값을 가진 노드 들( 즉, 두개의 서브트리를 가지는) 일 경우

        -- 본 예에서 60을 삭제 하고자 한다고 가정 하겠습니다. delete(40)

        -- 위의 예에서 보고 이렇게 하면되지 , 쉽게 보일 수 있지만 아래의 예를 보면 약간은 생각보다 복잡합니다.

        -- 두가지 방법이 있습니다(succesor를 삭제노드위치에 위치, predecessor을 삭제 노드 위치에 위치)

           더 금방 찾을 수 있는 (왼쪽 서브트리의 첫번째 노드) succesor를 이용합시다.

        -- succesor를 찾아서 삭제하려는 노드의 위치에 위치 시키고 부모노드와

        -- 삭제한 노드의 subtree들과 successor를 연결 시켜 주시면 됩니다.

        -- 위와 같이 삭제 연산을 수행 한 뒤에도 이진탐색트리가 나오게 되었습니다.

 * 성능분석

 - search, insert, delete (탐색, 삽입, 삭제) 연산 모두 O(n) 입니다.

 - worst case는 편향된(즉, 한쪽으로만 쭉쭉 뻗어있는 ) 트리입니다. 

 - tree에서의 연산들은 tree의 depth와 연관이 되어있는데 이럴경우 depth가 n(n-1) 이기 때문입니다.

 - average case의 경우 O(log n) 인데 worst case도 O(log n ) 을 맞추고 싶을 경우

 - depth를 맞추어주기 위해서 어느정도 균형이 잡혀 있는(예뿌장한?) 트리를 만들어 주어야 합니다.

 - 대표적인 균형이진트리들은 AVL TREE, RED-BLACK TREE 등이 있습니다.

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

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

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

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

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

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

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

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

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

출력을 하였습니다.

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

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

- 문자열을 탐색 하는 문제입니다.

- 딱히 어려운 문제는 아니고

- 단어를 차례대로 문자 하나씩 탐색 하던중 같은 문자를 받다가 다른 문자가 처음 나타날 경우

- 그 단어가 이전에 들어온적이 있는 단어 인지 처음 들어온 단어 인지만 체크 하면 되는 문제입니다.

- 들어왔던 단어들을 벡터에 저장해 두었다가 새로운 문자가 들어올 때 그 벡터들을 탐색하여 들어온적이 있었는지를

-확인 하였습니다.

<코드>

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

- 아....너무쉬운 완탐 문제 였습니다...

- 처음에 문제를 파악할 때 입력 조건이 생각보다 크지 않다는 것을 체크 했어야했는데

- 처음에 무게순으로 정렬후 비교 작업하고 또 순서대로 출력해야 해서 구조체에 순서 저장 변수 따로 저장하고...

- 고생하다가 생각해보니 입력 조건이 크지 않다면 그냥 하나씩 전부와 비교하면 된다는 것....

- 그외에 특별할 것 없는 완탐 문제였습니다....... 입력 조건 파악을 잘하자....!

<코드>

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

이차원 배열을 통해서 map을 그리고 벽을 3개만 칠 수 있는데 벽을 3개를

쳤을 때 안전영역(바이러스가 퍼지지않는) 을 최대로 만들어 그 최대값을 출력하는 문제입니다.

초반에 어떠한 규칙을 세워야 좋을까 생각이 들었지만 너무 경우의 수가 많아 딱히

적용되는 규칙을 찾기 힘들어 모든 경우의 수를 다 세우고 그 경우의 수에 따라서 안전영역의 값을

구해 봐야되나....? 라는 생각을 한후 그럴경우 입력값의 조건들이 너무 크면 안되기 때문에 그를

확인해보니 (3<=N.M<=8) 이라 작은값임을 확인하고 그로 방향을 잡아 풀었습니다.

저는 [10][10] 배열을 만들어 index 0과9는 1로 채워서 벽같은 느낌을 주었습니다(바이러스가 퍼지지 못하게)

물론  조건문에 index를 걸어도 되지만 귀찮아서.....

아 그리고 벽이 세워질 수 있는 지역은 좌표를 구조체로 설정하여

벡터(vector)에다가 모두 넣은 다음 그 벡터에서 3개씩을 골라서 그 3개에 벽이 세워졌을 때 안전구역을 구하였습니다.

bfs를 통해서 -- 더이상 바이러스가 퍼질 구역이 없어서 큐가 비어있게 될경우 탐색을 멈춤

3중 반복문 이용(완전탐색) -- 이 과정에서 조건수정을 하느라고 시간이 좀 걸렸습니다.

<코드>