프로그래머스 - 알고리즘 고득점 Kit 완전탐색, 탐욕법(Greedy) 풀이 모음
: 프로그래머스 코딩테스트 연습 Python 알고리즘별로 풀어보기
🔍 완전 탐색 > 최소직사각형
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(sizes):
sorted_sizes = [sorted(i) for i in sizes]
maxRow = 0
maxCol = 0
for i in sorted_sizes:
maxRow = max(i[0], maxRow)
maxCol = max(i[1], maxCol)
return maxRow * maxCol📢 풀이 설명
큰 변 중 가장 큰 것, 작은 변 중 가장 작은 것을 곱하면 최소 넓이가 나온다.
🔍 완전 탐색 > 모의고사
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(answers):
person_1 = [1, 2, 3, 4, 5]
person_2 = [2, 1, 2, 3, 2, 4, 2, 5]
person_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
correct = [0, 0, 0, 0]
for idx, i in enumerate(answers):
if person_1[idx % len(person_1)] == i: correct[1] += 1
if person_2[idx % len(person_2)] == i: correct[2] += 1
if person_3[idx % len(person_3)] == i: correct[3] += 1
maxCount = max(correct)
return list(filter(lambda x: correct[x] == maxCount, range(len(correct))))
📢 풀이 설명
풀이가 너무 비효율적인 것 같다는 생각에 불안감이 들었지만 일단 go 했던 문제...
완전 탐색 문제라 그런지 이 풀이도 나쁘지 않은 것 같다는 생각이 든다 ㅎ.ㅎ
- dict -> list로 변환 방법
1).items(): dict 뒤에 붙여주면dict_items([(key, value), (key, value), ...])형태로 반환
2) 앞에 붙는 dict_items을 없애고 싶을 경우:리스트 컴프리헨션이용
3)zip(): 인자들을 엮어서 튜플 형태로 반환
4)map(): 요소들마다 함수를 적용해 리스트로 반환
-> dictToList = [(k, v) for k, v in dictName.items()]dictName = { "a": 1, "b": 2, "c": 3 } # 1) print( dictName.items() ) # dict_items([("a": 1), ("b": 2), ("c": 3)]) # 2) print( [(k, v) for k, v in dictName.items()] ) # [("a": 1), ("b": 2), ("c": 3)] # 3) print( list(zip(dictName.keys(), dictName.values())) ) # [("a": 1), ("b": 2), ("c": 3)] # 4) print( list(map(list, dictName.items())) ) # [["a": 1], ["b": 2], ["c": 3]]
🔍 완전 탐색 > 소수 찾기
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from itertools import permutations
import math
def solution(numbers):
numbersList = [i for i in numbers]
newNums = []
newNumList = []
result = 0
for i in range(len(numbers)):
combinationList = permutations(numbersList, i + 1)
for j in combinationList:
newNums.append(j)
for num in newNums:
newNumList.append(int("".join(num)))
newNumsSet = set(newNumList)
print(newNumsSet)
for i in newNumsSet:
if i == 0 or i == 1: continue
sqrtNum = int(math.sqrt(i))
count = 0
prime = True
for j in range(2, sqrtNum + 1):
if i % j == 0:
prime = not prime
break
if prime == True: result += 1
return result
📢 풀이 설명
순열을 이용해 가능한 숫자들을 모두 만든 뒤, set으로 중복을 없애주었다.
그 후 에라토스테네스의 체 알고리즘을 이용해 소수를 판별하였다.
🔍 완전 탐색 > 카펫
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(brown, yellow):
k = (brown // 2) - 2
for i in range(1, k):
n, m = (k - i), i
if n * m == yellow: return [n + 2, m + 2]
📢 풀이 설명
-
brown의 가로 = n + 2, 세로 = m + 2
-
yellow의 가로 = n, 세로 = m
-
브라운의 가로 한 줄 + 세로 한 줄
=> brown // 2 = n + m + 2 (겹치는 타일 4개 빼고 나눈 값)
=> (brown // 2) - 2 = n + m = k -
(k - i), i = yellow 가로, yellow 세로
🔍 완전 탐색 > 피로도
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from itertools import permutations
def solution(k, dungeons):
result = 0
dungeonsLen = len(dungeons)
dungeonsList = list(permutations(dungeons, dungeonsLen))
for i in dungeonsList:
curK = k
tmpResult = 0
for (minimum, consume) in i:
if curK < minimum: break
else:
tmpResult += 1
curK -= consume
result = max(result, tmpResult)
if result == dungeonsLen: break
return result
🔍 완전 탐색 > 전력망을 둘로 나누기
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from collections import deque
def solution(n, wires):
tree = [[] for _ in range(n + 1)]
result = float("inf")
for (a, b) in wires:
tree[a].append(b)
tree[b].append(a)
def bfs(num, cutNum):
queue = deque([num])
visited = [0 for _ in range(n + 1)]
visited[num] = 1
visited[cutNum] = 1
count = 0
while queue:
curNum = queue.popleft()
for k in tree[curNum]:
if visited[k] == 0:
visited[k] = 1
queue.append(k)
count += 1
return count
completion = dict()
for i in range(1, n + 1):
for j in tree[i]:
if completion.get(str(i)) and completion.get(str(i)) in str(j): continue
completion[str(i)] = str(j)
completion[str(j)] = str(i)
iCount = bfs(i, j)
jCount = bfs(j, i)
interval = abs(iCount - jCount)
if interval == 0: return 0
else: result = min(result, interval)
return result📢 풀이 설명
각 노드들이 연결되어있는 부분을 둘로 나누어 각 노드에 속하는 개수를 파악해 두 노드 차의 최솟값을 리턴하는 문제다.
먼저 각 노드들과 연결된 노드들의 개수 파악을 위해 bfs 함수를 만든다.
그 후 for문을 통해 각 노느들을 돌며, 방문하지 않았던 연결 지점이면 분리될 노드들을 bfs 돌려 개수를 센다.
이때 값이 0이면 똑같다는 얘기고, 가장 최솟값이기 때문에 바로 return한다.
🔍 완전 탐색 > 모음사전
클릭해서 문제 전체 보기🔼
📖 풀이 코드
from itertools import product
def solution(word):
alphabet = ["A", "E", "I", "O", "U"]
words = []
for i in range(1, 6):
curList = ["".join(w) for w in list(product(alphabet, repeat = i))]
words += curList
words.sort()
return words.index(word) + 1📢 풀이 설명
사전을 다 만들어도 속도가 크게 오래걸릴 것 같지 않아 그냥 다 만들었다.
그 후 찾으려는 단어의 index + 1을 반환해주면 된다.
🔍 탐욕법(Greedy) > 체육복
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(n, lost, reserve):
lost.sort()
reserve.sort()
for i in lost[:]:
if i in reserve:
lost.remove(i)
reserve.remove(i)
if len(reserve) == 0: return n - len(lost)
if len(lost) == 0: return n
for i in reserve:
if (i - 1) in lost: lost.remove(i - 1)
elif (i + 1) in lost: lost.remove(i + 1)
if len(lost) == 0: return n
return n - len(lost)
📢 풀이 설명
로직은 금방 짰는데 시간이 엄청 오래 걸린 문제다 ㅜㅜ for i in lost[:]: 이 부분의 [:]를 쓰지 않아 계속 틀렸었다.
여기서 lost[:]:는 lost의 복사본이라는 뜻이다.
그냥 lost를 쓴 후 for문을 돌며 remove로 인해 lost가 바뀔 경우, for문의 요소도 변동이 생겨 정확한 값을 만들 수 없다.
따라서 for문에 영향이 가지 않게 복사본을 사용해야한다.
🔍 탐욕법(Greedy) > 조이스틱
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(name):
n = len(name)
def changeChar(char):
fromA = ord(char) - 65
fromZ = 1 + (90 - ord(char))
return min(fromA, fromZ)
charCount = sum(changeChar(i) for i in name)
movingCount = n - 1
for (idx, i) in enumerate(name):
nextIdx = idx + 1
while nextIdx < n and name[nextIdx] == "A":
nextIdx += 1
continuousA = n - nextIdx
backMoving = min(2 * idx + continuousA, 2 * continuousA + idx)
movingCount = min(movingCount, backMoving)
return charCount + movingCount📢 풀이 설명
쉬운 문제인줄 알았는데 중간에 방향을 바꾸는 걸 고려 못해서 엄청 오래걸렸다.
이 문제의 핵심은 최소 movingCount를 찾는 것이다. 나의 풀이는 다음과 같다.
-
changeChar함수를 통해 문자를 바꾸기 위해 움직이는 횟수를 세어charCount에 저장 (A의 아스키코드는 65, Z의 아스키코드는 90) -
movingCount = n - 1으로 기본값을 설정 (처음부터 끝까지 앞으로 가는 경우) -
name을 for문으로 돌며 방향을 바꾸는 경우 이동 횟수를 세고, movingCount의 값을 최솟값으로 계속 갱신한다
-> 현재 도달한 문자열i, i의 인덱스번호idx, i 다음 글자의 인덱스번호nextIdx
-> 다음 문자열로 A를 만날 경우 스킵하기 위해nextIdx을 그 A의 다음 idx로 업데이트함 (문자열이 끝나거나 연속된 A가 끝날 때까지 계속 업데이트)
->continuousA는 연속된 A의 길이,backMoving은 2가지 중 더 작은 움직임을 선택하는 것 (아래에서 그림으로 자세히 설명)
->movingCount를 최솟값으로 업데이트
-
최종 움직인 횟수 return
🔍 탐욕법(Greedy) > 큰 수 만들기
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(number, k):
stack = []
deleteCount = 0
for idx, i in enumerate(number):
while len(stack) != 0 and stack[-1] < int(i) and deleteCount < k:
stack.pop()
deleteCount += 1
stack.append(int(i))
if deleteCount == k:
return "".join(map(str, stack)) + number[idx + 1:] if len(stack) != 0 else number[idx + 1:]
remainK = k - deleteCount
return number[:-remainK]
📢 풀이 설명
단순히 작은 수를 제거하는 것이 아닌, 앞 수와 비교해 작은 것을 제거해야하는 문제라서 stack을 사용했다.
🔍 탐욕법(Greedy) > 구명보트
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(people, limit):
result = 0
people.sort()
for (idx, i) in enumerate(people):
flag = False
while idx != (len(people) - 1):
result += 1
if i + people.pop() <= limit:
flag = True
break
if idx == (len(people) - 1) and not flag: result += 1
return result📢 풀이 설명
people을 가벼운 순으로 정렬 후 people로 for문을 돈다.
제일 무거운 사람은 people.pop()한 값이고, 제일 가벼운 사람은 people[idx]이다.
people이 1명 남을 때까지 while로 돌리는데, 일단 보트 1개 꺼내서 result += 1 하고, 제일 가벼운 사람 + 무거운 사람 > limit이면 무거운 사람만 보내고, 제일 가벼운 사람 + 무거운 사람 <= limit이면 둘이 한 보트 탔으니 flag = True 후 break해서 다음 가벼운 사람으로 넘어간다.
이때 제일 가벼운 사람이 마지막 사람이자 보트를 탄 사람이 아니면 그 사람도 보트를 태워 result += 1 한다.
🔍 탐욕법(Greedy) > 섬 연결하기
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(n, costs):
costs.sort(key = lambda x: x[2])
parent = [i for i in range(n)]
rank = [0] * n
def find(x):
if parent[x] != x: parent[x] = find(parent[x])
return parent[x]
def union(rootA, rootB):
if rank[rootA] > rank[rootB]: parent[rootB] = rootA
elif rank[rootA] < rank[rootB]: parent[rootA] = rootB
else:
parent[rootB] = rootA
rank[rootA] += 1
totalCost = 0
for (a, b, cost) in costs:
rootA = find(a)
rootB = find(b)
if rootA != rootB:
union(rootA, rootB)
totalCost += cost
return totalCost📢 풀이 설명
처음에는 bfs로 풀었는데 틀리고 시간초과가 발생했다. 이유를 찾아보니 문제 유형 자체가 틀렸었다.
이 문제는 전형적인 MST 문제로, 모든 노드를 연결할 수 있는 간선들의 최솟값을 찾아야한다. 크루스칼 알고리즘을 이용해 풀었다.
비용을 기준으로 섬들의 연결을 정렬하고, 작은 비용 순서대로 섬을 합쳐서 최소 비용을 만들었다.
🔍 탐욕법(Greedy) > 단속카메라
클릭해서 문제 전체 보기🔼
📖 풀이 코드
def solution(routes):
result = 0
routes.sort(key = lambda x: x[1])
curLocation = -30001
for i in routes:
if i[0] > curLocation:
curLocation = i[1]
result += 1
return result📢 풀이 설명
차들을 진출 지점을 기준으로 정렬한 후, default값을 초기화한다.
그 후 차들을 돌며 진입 지점이 default값보다 클 경우(뒤에 있을 경우) 그 차의 진출지점에 카메라를 한 대 더 설치한다.
