[TIL Day6] 코딩테스트 더 풀어보기 (2)
🟢 푼 문제
🟡 접근 방법을 알았지만 못 푼 문제
🔴 접근 방법도 모르고 못 푼 문제
Lv2.
1. 문자열 압축 🟡
- 문제 해결 방법
- 결국 완전 탐색이었다.- 문자열 슬라이싱은 문자의 길이를 넘어가도 오류 없이 작동한다는 것.
def solution(s):
answer = len(s)
# 1부터 문자열s의 절반 길이까지 압축 단위를 늘려가며 확인한다
for size in range(1, len(s) // 2 + 1):
count = 1
# 압축했을 때 문자열의 길이 저장
compress = 0
prev = s[:size]
for i in range(size, len(s) + size, size):
curr = s[i:i + size]
# 이전 단위 문자열 prev와 현재 단위 문자열 curr이 같으면
if prev == curr:
count += 1
# 다르면
else:
# count가 2이상인 경우와 1인 경우 구분
compress += size + len(str(count)) if 1 < count else len(prev)
prev = curr
# count 초기화
count = 1
answer = min(answer, compress)
return answerLv3.
1. 배달 🔴
- BFS 풀이
- 정확도가 50점이 나왔다.- 다른 도시를 거쳐가는 것이 바로 가는 도로보다 비용이 더 싼 경우가 있을 수 있다.
from collections import deque
def solution(N, road, K):
graph = [[0] * (N + 1) for _ in range(N + 1)]
for r in road:
# 출발지와 도착지가 같은 도로가 또 있는 경우 더 비용이 작은 것만 기록
if graph[r[0]][r[1]] != 0:
graph[r[0]][r[1]] = min(graph[r[0]][r[1]], r[2])
else:
graph[r[0]][r[1]] = r[2]
# 반대 방향도 기록
graph[r[1]][r[0]] = graph[r[0]][r[1]]
# print(graph)
distance = [-1] * (N + 1)
distance[1] = 0
# BFS
q = deque([1])
while q:
now = q.popleft()
for next_node in range(1, N + 1):
# 도로가 있고 아직 방문하지 않은 도시라면
if graph[now][next_node] != 0 and distance[next_node] == -1:
# 최단 거리 갱신
distance[next_node] = distance[now] + graph[now][next_node]
q.append(next_node)
# print(distance)
return len([x for x in distance[1:] if x <= K])다익스트라 알고리즘
그래프에서 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘으로, 음의 간선이 없을 때 사용할 수 있다.
-
알고리즘의 작동 과정
1. 출발 노드를 설정한다.- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.
- 위 과정에서 3과 4번을 반복한다.
-
알고리즘의 특징
- '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트(최단 거리 테이블)에 저장하여 리스트를 계속 갱신한다.- 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정(4번)을 반복하므로 그리디 알고리즘으로 분류된다.
import heapq
INF = int(1e9)
def solution(N, road, K):
graph = [[] for i in range(N + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (N + 1)
# 양방향 도로임에 주의
for r in road:
graph[r[0]].append((r[1], r[2]))
graph[r[1]].append((r[0], r[2]))
# 다익스트라 알고리즘
def dijkstra(start):
q = []
# 최소 힙으로 cost가 낮은 순서로 정렬되게 함
heapq.heappush(q, (0, start))
# 시작 노드까지의 비용은 0으로 초기화
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
# 이미 처리된 노드인지 확인
if distance[now] < dist:
continue
# 현재 노드를 거쳐 다른 노드로 가는 최단 거리를 계산한다
for i in graph[now]:
# 비용 = 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지 거리
cost = dist + i[1]
# 저장된 값보다 작으면 최솟값 갱신
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(1)
return len([x for x in distance if x <= K])2. FloodFill 🔴
- 문제 해결 방법
- BFS 알고리즘을 사용한다.- 이미지를 탐색하면서 방문한 칸을 visited에 체크하고 큐에 넣는다.
- 큐의 원소를 모두 pop하면 영역 count를 증가시킨다.
from collections import deque
def solution(n, m, image):
# 영역 count
cnt = 0
# 방문 여부 체크
visited = [[False] * m for _ in range(n)]
# 이동 방향
directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
for i in range(n):
for j in range(m):
# 방문하지 않은 칸에 대해서
if not visited[i][j]:
q = deque()
# 큐에 해당 칸 삽입
q.append([i, j])
# 방문 체크
visited[i][j] = True
# 칸 색상 체크
color = image[i][j]
# 큐가 빌 때까지
while q:
x, y = q.popleft()
# 인접한 네 칸에 대해 검사
for dx, dy in directions:
nx, ny = x + dx, y + dy
# 새로 움직인 좌표가 image 안에 있는지 확인
if 0 <= nx < n and 0 <= ny < m:
# 아직 방문하지 않았고
if not visited[nx][ny]:
# 색깔이 같은 칸이라면
if image[nx][ny] == color:
# 방문 처리한 뒤 큐에 삽입
visited[nx][ny] = True
q.append([nx, ny])
cnt += 1
return cnt3. 방문 길이 🟢
- 문제 해결 방법
- 지나온 경로를 따로 저장해둔다.
def solution(dirs):
direction = {'U':(-1, 0), 'D':(1, 0), 'R':(0, 1), 'L':(0, -1)}
x, y = 5, 5
# 지나온 경로 저장
# ((x, y), (nx, ny))
road = []
answer = 0
for i, d in enumerate(dirs):
nx = x + direction[d][0]
ny = y + direction[d][1]
if nx < 0 or nx > 10 or ny < 0 or ny > 10:
continue
# 지나온 경로가 아니라면 길의 길이 업데이트
if [(x, y), (nx, ny)] not in road and [(nx, ny), (x, y)] not in road:
answer += 1
road.append([(x, y), (nx, ny)])
x, y = nx, ny
return answer4. 게임아이템 🟡
- 문제 해결 방법
- heapq를 사용해 캐릭터별로 사용할 수 있는 아이템 중 공격력을 최대로 높이는 아이템을 선택한다.- 선택된 아이템을 삭제할 때는 deque의 popleft를 이용한다.
- 최소 힙인 heapq를 최대 힙처럼 사용하고자 할 때에는 원소의 부호를 (음수로) 바꾸자.
from heapq import heapify, heappush, heappop
from collections import deque
def solution(healths, items):
# 체력을 오름차순 정렬
healths.sort()
# 아이템이 소모하는 체력을 오름차순으로 정렬
items = sorted([(item[1], item[0], index + 1) for index, item in enumerate(items)])
items = deque(items)
answer = []
heap = []
for health in healths: # 제일 작은 체력을 가진 캐릭터부터
while items:
# 가장 깎는 체력이 낮은 아이템을 쓸 수 있는지
# 낮추는 체력, 높여줄 공격치, 아이템 번호
debuff, buff, index = items[0]
if health - debuff < 100: # 체력이 100보다 적게 남게 되는 경우 루프 종료
break
items.popleft() # 아이템 목록에서 삭제
heappush(heap, (-buff, index)) # 공격치의 부호를 바꾸어 최대 힙을 구현함
if heap: # 힙이 비어있지 않으면
# 쓸 수 있는 아이템 중 공격치를 최대로 높이는 아이템 사용
_, index = heappop(heap)
answer.append(index)
return sorted(answer)5. 빙고 🔴
- 문제 해결 방법
- nums가 n x n 보드판에 있는지 매번 확인하려면 O(n^2 * nums)의 시간복잡도가 소요된다.- nums를 hash로 만들어서 O(1)로 체크하자.
def solution(board, nums):
n = len(board)
# nums 리스트의 값을 키로 변환하여 dict로 만들어준다
nums = dict.fromkeys(nums, True)
row_list = [0] * n # 행 방향으로 지운 숫자의 개수를 센다
col_list = [0] * n # 열 방향으로 지운 숫자의 개수를 센다
left_diagonal = 0 # 왼쪽 대각선
right_diagonal = 0 # 오른쪽 대각선
for i in range(n): # O(n)
for j in range(n): # O(n)
if board[i][j] in nums: # O(1)
board[i][j] = 0
row_list[i] += 1
col_list[j] += 1
if i == j:
left_diagonal += 1
if n - 1 - i == j:
right_diagonal += 1
answer = 0
answer += sum([1 for i in row_list if i == n])
answer += sum([1 for j in col_list if j == n])
answer += 1 if left_diagonal == n else 0
answer += 1 if right_diagonal == n else 0
return answer6. N-Queen 🔴
- 문제 해결 방법: DFS로 풀자.(정석)
- 경우의 수를 모두 찾으면서 가능하지 않은 것은 가지치기 <- 이것이 백트래킹이다.
- 2차원 보드판이라고 해서 무조건 2차원 배열을 사용하려고 하지 말자.- 1차원 row 리스트에 col 값을 저장해서 쓸 수 있다.
# 해당 위치에 퀸을 둘 수 있는지 체크
def check(queen, row):
for i in range(row):
# i행의 값과 row행의 값이 같다면 퀸을 둘 수 없음
# 왼쪽, 오른쪽 대각선으로 인접한지도 확인
if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
return False
return True
# 맨 위 행부터 열을 이동하면서 체크, 퀸을 뒀으면 다음 행으로 이동
def search(queen, row):
# stack = 1
n = len(queen)
count = 0
# 끝에 도달한 경우 1을 리턴
if n == row:
return 1
for col in range(n):
queen[row] = col # row, col 영역에 퀸을 둔다
if check(queen, row): # 둘 수 있는지 체크한다
# 가능하다면 다음 행으로 이동한다
count += search(queen, row + 1)
return count
def solution(n):
return search([0] * n, 0)7. N으로 표현 🟡
- 문제 해결 방법
- 다이나믹 프로그래밍으로 재귀적 방식으로 접근하자.
- 강의에서 푼 문제였지만 풀이법이 곧장 떠오르지 않았다.
- 숫자 x를 n번 사용해서 만들 수 있는 경우의 수는, 1번 사용한 숫자들과 n-1번 사용한 숫자들을 연산한 결과 + 2번 사용한 숫자들과 n-2번 사용한 숫자들을 연산한 결과 + ... + n-1번 사용한 숫자들과 1번 사용한 숫자들을 연산한 결과
def solution(N, number):
# i번 사용해서 만들 수 있는 수들의 집합을 원소로 갖는다
s = [set() for x in range(8)]
# 5, 55, 555 ... 를 각 set에 먼저 채워주자
# enumerate에 start=1 주의하자
for i, x in enumerate(s, start=1):
x.add(int(str(N) * i))
# 이 때 이미 정답이 있는 경우가 있다
if number in s[i - 1]:
return i
for i in range(1, len(s)):
for j in range(i):
# j번 사용해서 만든 수 중 피연산자 op1을 가져온다
for op1 in s[j]:
# i - j - 1번 사용해서 만든 수 중 피연산자 op2를 가져온다
for op2 in s[i - j - 1]:
s[i].add(op1 + op2)
s[i].add(op1 - op2)
s[i].add(op1 * op2)
if op2 != 0:
s[i].add(op1 // op2)
if number in s[i]:
answer = i + 1
break
else:
answer = -1
return answer8. 2 x n 타일링 🟢
- 문제 해결 방법
- 점화식 f(x) = f(x - 1) + f(x - 2)임을 이용하여(피보나치 수열)
- 보텀업 방식으로 가로 길이가 n일 때까지 경우의 수를 구하자.
def solution(n):
fibo = [1, 2, 3]
for i in range(3, n):
fibo.append((fibo[i - 2] + fibo[i - 1]) % 1000000007)
return fibo[n - 1]9. 등굣길 🔴
- 문제 해결 방법
- 격자모양의 맵에서 목표 칸까지 가는 모든 경우의 수를 더해가며 저장한다.
- 웅덩이가 있는 곳은 갈 수 없으므로, 이후 칸에 영향을 주지 않기 위해 0으로 바꿔 처리한다.
def solution(m, n, puddles):
maps = [[0] * (m + 1) for _ in range(n + 1)]
# 1, 1 좌표의 경우의 수는 1이다
maps[1][1] = 1
# 웅덩이 좌표는 -1로 표시
for x, y in puddles:
maps[y][x] = -1
for y in range(1, n + 1):
for x in range(1, m + 1):
# 웅덩이인 경우 이후 합에 영향이 가지 않도록 0으로 바꾼다
if maps[y][x] == -1:
maps[y][x] = 0
continue
# 왼쪽과 위의 경우의 수를 합해여 해당 칸으로 오는 모든 경로를 구한다
maps[y][x] += (maps[y - 1][x] + maps[y][x - 1]) % 1000000007
# n, m 좌표의 경우의 수를 반환
return maps[n][m]10. 가장 긴 팰린드롬 🟢
- 제한 시간이 넉넉할 때
- 앞에서부터 단위를 늘려가며 모든 경우의 수를 확인
def solution(s):
answer = 1
for num in range(2, len(s) + 1):
for start in range(0, len(s) - num + 1):
temp = s[start:start + num]
if temp == temp[::-1]:
answer = max(answer, num)
return answer- 정말 빠른 알고리즘으로 푸는 방법
-
Author And Source
이 문제에 관하여([TIL Day6] 코딩테스트 더 풀어보기 (2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dhelee/TIL-Day6저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
