프로그래머스[Python] - 방금그곡, 가장 큰 정사각형 찾기

방금 그곡[2018 KAKAO BLIND RECRUITMENT]

문제 url : https://programmers.co.kr/learn/courses/30/lessons/17683

코딩테스트 연습 - [3차] 방금그곡

문제 내용 : 네오가 라디오에서 음악을 검색할때, 어떤 음악이었는지 판단하려고한다.

알고리즘 : 문자열 슬라이싱, copy(알게된거)

알게된 점 : 우선 따져야할 조건이 여러개였다.

1. #같은 것도 하나의 음표로 봐야해서 C와 C#을 분리해야했다.
2. '(None)'을 return하는 함정도 있었다.
3. copy 모듈을 사용하여 deepcopy와 copy를 사용해 변수를 메모리에 따로 저장할 수 있다.
4. for문으로 인덱스를 다시한번 꼼꼼하게 따져보자

가장 큰 정사각형 찾기(좋은 문제)

문제 url : https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

문제 내용 : 1과 0으로 채워진 board가 있다. 1*1 정사각형으로 각 칸이 이뤄져 있다. 1로이루어진 정사각형중 가장 큰 '정사각형'의 넓이를 구하라.

알고리즘 : DP

알게된 점 : 처음에 재귀적으로 처리하려다가 시간초과가 났다. 애초에 정사각형을 큰 것부터 찾아서 1인지 판단하고 return 하면 더 빠를 것으로 생각했기 때문이다.

그런데 DP로 푼다면 전체적으로 더 효율적인 코드를 짤 수 있었다.

dp에는 정사각형이라면 가능한 가장 긴 변의 길이를 저장한다.

판단은 현재 자리가 1일때 이전에 있는 것들과 비교해서 작은 것들보다는 최소 1이 더 큰 변일 것이다.