[알고리즘] 완전탐색 문제풀이 _ 파이썬

▒ 코딩테스트 공부 방법

 

 

  1. codeup 기초 100제로 기초를 다지고 사용할 언어에 익숙해지도록 한다. 

 

  2. 백준온라인 저지 단계별, 유형별 문제를 푼다.

배열, 문자열, 정렬, 브루트포스(완전탐색), 재귀, 백트래킹, 동적계획법, bfs/dfs 등의 유형에 익숙해진다.

-완전탐색(재귀나 백트래킹으로)->시뮬레이션->그래프(위상정렬, 다익스트라..)->최소신장유니온트리(유니온파인드 등)->심화문제(스택으로 라인스위핑 같은)->DP, dp는 코딩테스트에 나오면 완죠니 어렵게 나온다고 한다.

 

  3. 프로그래머스 코딩테스트 고득점 kit를 푼다.

유형별 4~7문제를 풀며 자주 나오는 유형을 익힌다.

 

  4. 프로그래머스 스킬체크

주어진 시간내에 2문제를 풀고, 나의 실력을 파악한다. 레벨3정도면 웬만한 코딩테스트에 합격할 수 있다고 한다.

 

---

 

프로그래머스 고득점 키트에 있는 완전탐색 문제 푼 것들 코드 리뷰 해보려고 합니다.

 

완전 탐색은 말 그대로 모든 경우의 수를 다 해보는 것을 말합니다.

정확하지만 시간이 최대이고 효율성이 떨어집니다. 실무에서는 많이 사용하지 않는 방법이지만 코딩테스트에 자주 등장하는 유형입니다.

 

푸는 방법은 여러가지가 있는데,

 

1. for, if 문을 반복해서 처음부터 끝까지 탐색하는 방법

2. 순열, 조합을 사용하는 방법

3. 재귀함수를 사용하는 방법

4. 비트마스크를 사용하는 방법

5. 백트래킹을 사용하는 방법

6. bfs를 사용하는 방법

 

개인적으로 순열 조합이랑 bfs를 사용하는 것을 선호합니다.

 

---

 

푼 문제는,

프로그래머스 42839, 42840, 42842, 60057

 

 

1. 프로그래머스 42840

이 문제는 고득점키트 완전탐색 유형에서 가장 난이도가 낮은 문제 입니다.

 

 

 

코드

def solution(answers):
    student = {1:[1,2,3,4,5], 2:[2,1,2,3,2,4,2,5], 3:[3,3,1,1,2,2,4,4,5,5]}
    score = {1:0, 2:0, 3:0}

    for idx, answer in enumerate(answers):
        for key, value in student.items():
            if answer == value[idx % len(value)]:
                score[key] += 1
                
    highest = max(score.values())
    result = [key for key, value in score.items() if value == highest]

    return result

학생들이 찍는 순서를 딕셔너리에 넣고,

문제와 학생을 하나씩 for if문을 이용해서 비교한다. 맞으면 점수를 올리고 max 값을 출력한다.

 

enumerate는 인덱스와 값을 모두 for 문에서 사용할 수 있고

파이썬에서는 for문을 사용할 때 변수를 여러개 지정할 수 있다. for key value in student.items() 처럼 이는 딕셔너리의 키 값과 밸류 값을 모두 포문으로 돌릴때 짱짱 유용하다. 만약 student가 딕셔너리가 아닌 리스트라면, for key value in zip (student1, student2) 처럼 zip()함수를 사용하면 여러 변수를 쓸 수 있습니다.

 

---

2. 프로그래머스 42839

 

코드

from itertools import permutations

def solution(numbers):
    number = list(numbers)
    perms = []
    answer = 0

    for i in range(1, len(number)+1):
        for perm in permutations(number, i):
            perms.append(''.join(perm))
    perms = list(set(perms))

    for num in perms:
        if num[0] != '0' and num != '1':
            if prime_number(num) == True:
                answer += 1

    return answer

def prime_number(number):
    num = int(number)
    for f in range(2, int(num**0.5)+1):  
        if num % f == 0:     
            return False   

    return True

소수 찾는 부분을 좀 더 간단하게 할 수 있을 거 같긴한데..

 

아무튼 소수를 판별하는 prime_number의 리턴 값이 True이면 answer의 값을 증가시키는 방법으로 문제를 풀었습니다.

 

 

---

3. 프로그래머스 42842

 

코드

def solution(brown, yellow):
    hap = brown + yellow
    lis = []

    for i in range(3, hap):
        if hap % i == 0:
            if i > hap//i:
                break
            lis.append([hap//i,i])
    
    answer = [li for li in lis if (li[0]-2)*(li[1]-2) == yellow]

    return answer[0]

 

 

이렇게 풀다보면 자신감이 쌓여서 코딩테스트 잘 풀것 만 같은데

막상 코딩테스트를 볼 때면 평소엔 잘 생각나던 함수도 방법도 생각이 안나더라는... 그리고 아이티 회사들의 코딩테스트 네이버, 카카오는 고득점 키트보다 훨 손이 많이 가는 문제가 나온다.