[프로그래머스] 완전탐색 4문제

💡 [완전탐색 공부]

https://cloudclub.notion.site/Brute-Force-a6c165440513444095dd34fda7d2b211?pvs=4

완전탐색(≒Brute Force)

1. 모의고사

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

알고리즘

• 완전탐색(?)

알고리즘은 아닌데

• enumerate 사용
• max() 사용

코드

def solution(answers):
    user =[[1,2,3,4,5],[2,1,2,3,2,4,2,5],[3,3,1,1,2,2,4,4,5,5]]
    res =[]

    for value in user:
        #value 를 answers 와 비교해서 일치하면 cnt +=1
        i, cnt = 0,0
        n = len(value) #value 마다의 개수 (ex :user[0][1]의 len)
        for ans in answers: #answers 와 비교
            if ans == value[i]:
                cnt+=1
            i +=1
            i%=n
        res.append(cnt)

    maxValue=max(res)
    answer =[]
    for num,value in enumerate(res):
        if(value == maxValue):
            answer.append(num+1)
    return answer

설명

1. 수포자들의 값을 list 에 저장
2. answers 에 수포자의 값이 있을경우 cnt +=1
3. 수포자 한명 다 돌았을때 res 리스트에 cnt 추가
4. 다 돌고 가장 큰 값과 그 값에 해당하는 인덱스 찾기

참고

어려웠던 점

• 잘 모르는 나

2. 소수찾기

문제 설명

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

프로그래머스

알고리즘

• set 자료구조
  • set 자료구조의 특징은 중복이 없다
• 소수 찾기 - 에라토스테네스의 체
• 순열

코드

from itertools import permutations
import math

def is_prime_number(x):
    if x<2:
        return False

    for i in range(2,int(math.sqrt(x)) +1):
        if x % i ==0:
            return False
    return True

def solution(numbers):
    #문자열을 요소마다 분리해 하나하나 넣어준다.
    nums = list(numbers)
    per = []
    #numbers의 모든 숫자들을 
    for i in range(1,len(numbers)+1):
        #i개씩 순열 조합
        per += list(permutations(nums,i))
        # 조합된 숫자를 숫자로 변환 
    new_nums =set(int(''.join(p)) for p in per) # 중복숫자 제거

    cnt =0
    for num in new_nums:
        if is_prime_number(num):
            cnt +=1

    return cnt

설명

💡 소수판별자체를 어떻게 하는지를 까먹음 [소수판별]

https://www.notion.so/e22110ba6eeb40169c99ab2bd63a138d?pvs=21  

소수판별

• numbers는 문자열이기 때문에, 분리해줘야한다.
• 일단 나올수 있는 숫자 경우의 수 (순열 이용해서 )구한다음에
• 소수 판별 함수에 넣어서 소수인경우 cnt+=1
• return 하면될듯 ?

어려웠던 점

• 문자열을 slice 말고 어떻게 자르지..
• Python - 문자열을 한 글자씩 분리하여 리스트에 넣기
• 순열 permutations 잘 사용하지 못한다.
• 순열 결과가 (”1”,”2”)이런식으로 나오는데, 분리된 숫자문자열을 하나로 합치는 방법을 몰랐다.

[python] 파이썬 join 함수 정리 및 예제 (문자열 합치기)

3.

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

알고리즘

• 순열, 약수

코드 (테스트케이스 4개만 통과..)

from itertools import permutations

def getPermutations(divisorList):
    arr = []
    for i in permutations(divisorList,2):
        arr.append(i)
    return arr

def getMyDivisor(n):
    divisorsList = []
    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisorsList.append(i) 
            if ( (i**2) != n) : 
                divisorsList.append(n // i)
    divisorsList.sort()
    return divisorsList

def solution(brown, yellow):
    answer = []
    if yellow == 1:
        return [3,3]
    yellowList = getMyDivisor(yellow)
    arr = getPermutations(yellowList)
    for x,y in arr:
        if (x>=y):
            if(x-y<=2) and ((x+2)*(y+2) == brown+yellow) :
                answer = [x+2,y+2]
        else:
            continue
    return answer

설명

문제를 관찰해봤다.

1. 가로 ≥ 세로
2. yellow 의 가로 +2 , 세로 +2 가 곧 카펫의 가로 세로 길이가 된다.
3. 그렇다면, yellow 의 약수를 순열 조합한 다음에 1번의 조건에 해당하는 숫자를 골라서 +2 해줘서 return 하면되지않을까?
   1. 근데 여기서 문제는, 1번에 해당하는 조합이 생각보다 많다는 것.
   2. brown 이 yellow 를 감싸려면, yellow가로-yellow세로≤2 여야만 조건이 성립하는것 같다(추리)

그렇다면 이걸 어떻게 구현하는가?

어려웠던 점

• 아직 해결못함
• 이게 이렇게까지 길어지는 코드가 아닌 것 같다는 생각이 든다.

4.

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

알고리즘

• DFS
• 백트래킹
• 순열

코드

[프로그래머스/Python] 피로도

그냥 끄적이기,,
def DFS(graph,root):
    visited = []
    stack = [root]
    while stack :
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited,stack

def solution(k, dungeons):
    answer = -1
    # DFS 호출할때에는 k 값보다 크거나 같은 dungeons를 찾아서 전달


    return answer

---
from itertools import permutations
def solution(k, dungeons):
    # 던전의 번호: 0, 1, 2
    idx = [i for i in range(len(dungeons))]
    # 던전의 개수
    cnt = len(dungeons)

    # 최대 던전의 수에서 1씩 줄여간다: 3,2,1
    for i in range(cnt,0,-1):
        # i개일 때의 던전의 순열을 구한다.
        for order in permutations(idx,i):
            now = k
            check = True
            for o in order:
                if dungeons[o][0] > now:
                    check = False
                    break
                else: 
                    now -= dungeons[o][1]
            if check:
                return i

설명

노가다로 경우를 하나하나 다 구하는 경우를 생각하다가,

DFS 나 BFS 를 써야한다는걸 깨달았다.

• 경우를 찾은다음에, return 값이 더 큰 것을 답으로 출력 하면 된다.
• 근데 방문 배열을 사용하는 DFS 랑은 다른게, 한번만 방문하는게 아니라, 이전 경우에 방문한 순서를 기억해야 해서… 이걸 어떻게 해결하지?
• 스택으로 해결이 가능할 것 같기도 하다.
  • 늦게 방문할수록 top 에 가까우니..
  • 그 반대로 방문한다면..?
  • 근데 이건 예시가 3개일때의 경우이고, 아닐때에도 같을까?
  • 가능한 순서를 구한다음에 …
  • 2차원 배열 탐색은 어떻게 하냐
  • 백트래킹..(잘몰라요)
  • 저번에 풀었던 네트워크 문제랑 비슷한거같은데 더 쉬워보이는데 모르겠으요

어려웠던 점

• 위에 써둔거 .
• 백트래킹 잘 몰라요
• 머리가 안돌아가서 내일 다시.. (ㅁ..못했더용)

백트래킹은 어떨때 자주 쓰이는지?

브루트포스처럼 모든 가짓 수를 대입해야 답이 나오는 상황에서, 적절히 일부 경우는 대입하지 않아도 될 때 쓰는 것 같아요! 대표적으로 요런 문제가 있습니닷

https://www.acmicpc.net/problem/9663