TIL-20210727

Today

• 어제 못푼 알고리즘
• 입사 코딩 테스트 5문제

Contents

가장 큰 정사각형 풀이

나는 dfs를 이용하여 문제를 풀이 했는데, dp방식으로도 문제를 풀 수 있었다. 가장 작은 사각형을 어떻게 찾아내는가를 기준으로, 한단계 커졌을 때, 해당 좌표는 어느정도 크기의 사각형을 최대로 갖는가를 찾는 방식을 찾는다.

1. 특정 좌표를 기준으로 우하단으로 사각형을 늘려간다고 예측 할 수 있다.
2. 그렇다면 매 좌표마다의 최대 사각형의 수를 확인하고, 현재 사각형 최대 길이보다 크다면 최대 길이를 업데이트 한다.

입사 코딩 테스트

정답율 70%를 겨우 맞춤, 문제를 못풀 정도는 아닌데 시간 관리가 너무 안되는 느낌이다. 항상 단계마다의 예외상황을 체크하는게 미흡하다.

그래프 서치를 할 때는 생각한 조건에서 특이한 상황이 발생할 수 있는 예시를 찾는게 오래 걸린다. 이 상황을 어떻게 해결할 수 있을지 고민해봐야 겠다.