[인공지능 데브코스] 1주차 day5 - 알고리즘 문제풀이(3)
12월 04일 금
오늘도 역시나 프로그래머스 알고리즘 문제들을 풀었다. 오늘은 조금 난이도 있는 문제들도 풀어보았다. 전에 풀어봤던 문제들도 잘 안풀리는 문제가 많았다. 알고리즘 문제 푸는걸 잠깐 쉬는 사이에 상당히 많은 것을 까먹었다는 것을 알 수 있었다. 물론 한번 해봤던 것은 한 번 보면 금방 기억나지만 반복을 안하면 결국 다 까먹게 되는것 같다. 다시 한번 꾸준한 복습과 기록의 중요성이 느껴졌다. 오늘 날짜를 보니까 입대날이다…
문자열 압축 사본
전에 한번 풀어봤던 문젠데 그 때랑 똑같은 실수로 똑같이 틀리게 했다.
압축한 문자의 개수가 10개 이상일때는 자리수만큼 추가해 줘야 하는데 자리수를 생각을 안했다.
파이썬에서는 문자열 다루는 거나 자리수 구하는게 쉬워서 코드가 간결한 것 같다.
방법은 길이를 1부터 늘려가면서 문자열을 쪼개고 리스트에 저장한 다음 리스트를 순회하면서 압축 여부를 확인 하도록 했다.
def solution(s):
answer = len(s)
for l in range(1, len(s)//2 + 1):
lis = [s[i:i + l] for i in range(0,len(s), l)]
lis.append(1)
i=0 ; tmp = len(s); start = 0; count = 1
while i+1 <len(lis):
if lis[start] == lis[i+1]:
count += 1
tmp -= l
i += 1
else:
if count > 1:
tmp += len(str(count))
count = 1
i += 1
start = i
answer = min(answer, tmp)
return answer
배달
다익스트라 알고리즘을 사용해서 푸는 문제이다.
다익스트라 알고리즘이 뭔지만 알면 풀 수 있다.
하지만 다익스트라 알고리즘을 문제가 나올때마다 찾아봐야 기억날만큼 머리에 잘 들어오지 않는다.
이번에 확실히 외우고 넘어가야 겠다.
from queue import PriorityQueue
def solution(N, road, K):
INF = 987654321
graph = [[INF for i in range(N)] for j in range(N)]
for r in road:
graph[r[0]-1][r[1]-1] = min(graph[r[0]-1][r[1]-1], r[2])
graph[r[1]-1][r[0] -1] = min(graph[r[1]-1][r[0] -1], r[2])
for i in range(N):
graph[i][i] = 0
dis = [INF for i in range(N)]
pq = PriorityQueue()
pq.put([0,0])
while not pq.empty():
d, cur = pq.get()
if dis[cur] < d:
continue
for i in range(N):
n = i
ndis = d + graph[i][cur]
if ndis < dis[i]:
dis[i] = ndis
pq.put([ndis, i])
answer = [i for i in dis if i<=K]
return len(answer)
게임아이템
먼저 items의 각 원소에 index를 추가해 준다.
healths를 오름차순으로 정렬하고 items도 내려가는 체력을 기준으로 정렬한다.
체력의 요소를 기준으로 순회하며
만약 items중 마실 수 있는 물약이 있다면 heap에 넣어주고(-값을 넣어줘서 최대힙처럼 되도록 한다.) items에서는 제거해준다.
모든 물약에 대해서 반복한다.
그렇게 healths에 대한 한번의 루프가 끝났을 때 heap에 있는 물약들중 가장 공격력이 많이 올라가는 물약을 마신다.
(heap에서는 pop, answer에 append)
모든 healths에서 반복한다.
heap을 활용해서 소요시간을 줄일 수 있다는 점이 중요한 것 같다.
import heapq
def solution(healths, items):
healths.sort()
items = [items[i] + [i+1] for i in range(len(items))]
items.sort(key = lambda x:x[1], reverse = True)
answer = []
heap = []
for h in healths:
while items:
up, down, index = items[-1]
if h - down < 100:
break
items.pop()
heapq.heappush(heap, (-up, index))
if heap:
_, index = heapq.heappop(heap)
answer.append(index)
return sorted(answer)
빙고
각 행, 열에 몇개의 빙고가 들어있는지 list를 만들어서 개수만 세고 개수가 n개면 빙고인 점을 이용한다.
대각선의 경우는 변수 2개에 저장하여 세어준다.
def solution(board, nums):
nums = set(nums)
l = len(board)
row = [0 for i in range(l)]
col = [0 for i in range(l)]
d1 = 0
d2 = 0
for i in range(l):
for j in range(l):
if board[i][j] in nums:
row[i] += 1
col[j] += 1
if i==j:
d1 +=1
if i== l-j-1:
d2 += 1
answer = 0
answer += sum([1 for i in row if i==l])
answer += sum([1 for i in col if i==l])
answer += d1==l
answer += d2==l
return answer
N-Queen
dfs를 이용해서 풀었다.
첫번째 행부터 퀸을 어디에다가 놓을지를 선택하고 다음 행으로 넘어가는 방식으로 진행한다.
dfs의 입력값을 현재 상태를 나타내는 board와 지금 퀸을 놓을 행의 번호 row로 설정하였고
board[행]에 있는 값이 퀸을 놓여져 있는 열의 번호로 나타내면 1차원 리스트로 판의 상태를 표현 할 수 있다.
모든 경우에 퀸을 놓아보면서 조건을 만족하는 경우만 dfs의 값을 더해주는 방식으로 구현하였다.
유명한 문제여서 전에도 풀어본 적이 있었지만 오랜만이라서 그런지 처음에 조금 헤멨다.
def solution(n):
answer = dfs([0] * n , 0)
return answer
def dfs(board, row):
l = len(board)
if row == l:
return 1
ans = 0
for col in range(l):
board[row] = col
can = True
for i in range(row):
if board[i] == board[row] or abs(board[i] - board[row]) == row - i:
can = False
break
if can:
ans += dfs(board, row+1)
return ans
가장 긴 펠린드롬
dp로 풀었다.
dp를 이차원 리스트로 선언한다음 dp[i][j]를 문자열의 i부터 j까지의 부분문자열이 펠린드롬인지의 여부로 설정하였다.
문자열을 뒤에서부터 순회하면서 새로운 dp의 값이 이전까지 구한 dp값으로 나타나 지도록 for문을 구성하였다.
각 루프마다 길이의 최대값을 저장하여 답을 찾았다.
def solution(s):
answer = 0
l = len(s)
dp = [[False] * l for _ in range(l)]
for st in range(l-1, -1, -1):
for en in range(st, l):
if st>=en:
dp[st][en] = True
if s[st] == s[en]:
if st+1 >= en-1:
dp[st][en] = True
else:
dp[st][en] = dp[st+1][en-1]
if dp[st][en] and en-st+1 > answer:
answer = en-st+1
return answer