소프트웨어 마에스트로 1차 코테 후기

진짜 금방 막 시험이 끝났습니다.

알고리즘 올솔하려고 시험친건데 느낌상 3솔이라 이럴줄 알았으면 sql이랑 web문제를 먼저 풀 걸 이라는 후회가 남습니다.

 

아무튼 시작

 

A. DFS

그냥 dfs돌려서 leaf찾아주고 각 리프의 부모를 쭉 출력해주면 됩니다.

다만 출력을 주어진 간선 순으로 하라는데 이게 구현이 더 어려웠습니다.

저는 그냥 역순 놓고 제출했습니다.(당연히 간선순으로 출력 안나왔습니다😅)

 

B. Two pointer

각 배열마다 투포인터를 이용하여 주어진 시간이하의 가장 큰 값을 찾아주면 됩니다.

$O(N^2)$ 정도 시간으로 잘 돌아갈 것 같습니다.

 

C. 이분탐색+슬라이딩윈도우

시험 중에는 이분탐색에 뭘 더하면 될 것 같은데 모르겠어서 포기했습니다.

시험 끝나고 화장실 갔다오는데 이분탐색 조건으로 슬라이딩윈도우를 끼얹으면 바로 풀린다는걸 떠올렸습니다.

사람 위치가 포함되면서 m개 먹을 수 있으면 True, 이때 구간의 길이는 이분탐색으로 찾아주고 전구간을 길이 k의 윈도우로 밀어주기(참인지 거짓인지 확인)

(어차피 슬라이딩 윈도우 구현 딱 1번해봐서 제시간에 구현 안될것 같습니다 민망하네요😆)

 

D. union-find

well-known인데 문제 잘못 읽어서 삽질에 삽질을 더하다 겨우 제출했습니다.😭

 

그래도 목표는 무조건 만점입니다