[210208 TIL] Programmers Algorithm(완전탐색, greedy)

Today I Learned

written by 602

---

Programmers) 완전탐색 02. 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839

from itertools import permutations

def solution(numbers):
    answer = 0
    nums = []
    
    #경우의수
    for i in range(len(numbers)):
        case = list(permutations(numbers, i+1))
        nums += [int(''.join(j)) for j in case]
        
    #중복제거(set)
	for n in set(nums):
        count = 0
        
        #소수판별
        for i in range(1,n+1):
            if n%i == 0 and n != 0:
                count += 1
            if count >= 3:
                break
                
        if count == 2:
            answer += 1
            
    return answer

작년 <애널리틱스프로그래밍> 수강할 때, 소수 찾는 알고리즘을 구현해봤기 때문에 어렵지 않게 풀 수 있었다.

itertools는 알고리즘 풀이할때 적재적소에 잘 활용하면 상당히 유용하다. 특히 가능한 모든 경우의 수를 탐색할때는 permutations를 떠올리기!

Programmers) greedy 02. 조이스틱

https://programmers.co.kr/learn/courses/30/lessons/42860

def solution(name):
    answer = 0
    idx = 0
    change = [min(ord(i)-ord('A'), ord('Z')-ord(i)+1) for i in name]
    
    while True:
        
        amswer += change[idx]
        change[idx] = 0
        if sum(change) == 0:
            return answer
        
       	left, right = 1, 1
        while change[idx-left] == 0:
            left += 1
        while change[idx + right] == 0:
            right += 1
            
        answer += left if left < right else right
        idx += -left if left < right else right

조건이 많아서 너무 헷갈렸는데 알고리즘 스터디에서 좋은 힌트를 받아 그걸 이용해서 풀었다.

우선 ,상하 조정 중 최소횟수를 구하고, 좌우거리에서 최소값이 되는 방향으로 전환해야한다.

그리디는 그리디 문제인걸 알고 풀면 꽤나 수월해지는데, 처음 문제를 보고 그리디를 떠올리는 것이 어려운듯 하다.

+) if문과 그에 따른 결과를 한줄에 몰아 쓰는 것이 지난번 배운 pythonic code라고 한다

---