오늘의 알고리즘 일기(200527)

1. 가장 큰 정사각형 찾기 (프로그래머스 level 2)

def solution(board):
    answer = 0
    breaker = False
    li=[]
    standard = len(board[0])  # 가로
    num = len(board)  # 세로
    minnum = min(num,standard)
    for i in range(minnum, 0,-1): #(4,3,2,1)
        for j in range(0, len(board)-i+1): #세로부터
            for k in range(0,len(board[0])-i+1): #가로부터
                for l in range(j,j+i):
                    li= li+board[l][k:k+i]
                if 0 in li:
                    li = []
                    continue
                else :
                    answer=i
                    breaker =True
                    break
            if breaker == True:
                break
        if breaker == True:
            break
    return answer*answer

 

모든 정사각형을 조사하듯이 풀었다.

어찌어찌 돌아는 갔으나 역시 효율이 개판이기 때문에(O(n^4)) 위와 같은 형식으로 푸는 것은 지양한다.

 

이번에 공부하면서 처음 동적계획법(dp)을 접하게 되었는데, 이 문제에 대한 공부는 아래 블로그를 참고하였다.

https://codedrive.tistory.com/53  

[Programmers]Lv 2.가장 큰 정사각형 찾기

우선 동적 계획법이란 복잡한 문제를 여러개의 간단한 문제로 나누어 푸는 방법을 말하는데, 이러한 연습이 더욱 필요할 것을 느꼈다. 핵심은 왼쪽, 왼쪽 대각선, 위쪽 값들을 확인하는 것이다. 

 

참고로 이차원 리스트에서 for과 enumerate 값을 이용하면 아래와 같이 나온다.

board = [[1,0,0,1],[0,0,1,1],[1,1,1,1],[0,1,1,1]]
for y, line in enumerate(board):
    print(y,line)
    
  --결과값--
0 [1, 0, 0, 1]
1 [0, 0, 1, 1]
2 [1, 1, 1, 1]
3 [0, 1, 1, 1]

2. 소수찾기(프로그래머스 level 2)

from itertools import permutations

def solution(numbers):
    ll = []
    cnt = 0
    for i in range(1,len(numbers)+1):
        ll += list(map(int, map(''.join,permutations(numbers,i))))
    ll = set(ll)

    for i in set(ll): 
        for j in range(2,int(i**0.5)+1):
            if i%j == 0:
                ll.remove(i) # 소수가 아닌 수 제거
                break
    if 1 in ll:
        ll.remove(1)
    if 0 in ll:
        ll.remove(0)

    cnt=len(ll)

    return cnt

 

이 코드에서 핵심은 permutations(순열) 함수 사용이다.

permutation은 순열이라는 뜻이며, 고등학교 때 배운 n개의 원소 중 r개의 원소를 뽑은 집합을 리턴해준다.

따라서 for문으로 1개부터 최대 개수까지의 순열을 리스트를 만들어 넣어준다.

 

[예제]

print(list(map(''.join,permutations('abc',2))))

--결과--
['ab', 'ac', 'ba', 'bc', 'ca', 'cb']