1. 해시(Hash) 대표 문제: 완주하지 못한 선수
- 리스트가 숫자가 아닌 문자열일 경우 dict 자료형을 사용하는 것이 유용 (= 해시 자료구조 이용)
- get()메서드를 이용해 해당 key값에 해당하는 value를 새로 추가하거나 업데이트 할 수 있음
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
문제 풀이
def solution(participant, completion):
r = {}
for p in participant:
r[p] = r.get(p, 0) + 1 # 해당 값이 없으면 0+1, 있으면 n+1
for c in completion:
r[c] -= 1 # 완주한 사람 리스트에서 제외
for n, v in r.items():
if v > 0:
return n # value값이 1인 한 사람 찾음
2. 탐욕법(Greedy) 대표 문제: 체육복
- 탐욕법: 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하는 것
- 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법을 사용할 수 있다.
- 우선해서 선택할 순서를 정한 뒤, 최적의 선택을 하도록 알고리즘을 구성해야 함
- 현재 값 기준 양 옆의 값을 확인해야 하는 문제의 경우, 배열의 양 끝에 패딩처리를 하면 풀이하기 편함
(패딩처리: 배열 양 옆의 임시 값을 넣어 원래 배열보다 양 옆 길이가 1씩 길게처리)
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
문제 풀이
def solution(n, lost, reserve):
student = [1] * (n+2) # 학생 수 +2만큼의 배열 생성 (양쪽의 패딩처리)
# 체육복을 잃어버린 학생에 -1
for i in lost:
student[i] -= 1
# 여벌 체육복이 있는 학생에 +1
for r in reserve:
student[r] += 1
# 학생 별(패딩 제외) 2개의 체육복이 있는 학생 기준 왼쪽과 오른쪽에 빌려줄 수 있는지 확인
for s in range(1, len(student)-1):
if student[s] == 2:
if student[s-1] == 0: # 왼쪽 학생이 체육복 없을 경우
student[s-1:s+1] = [1,1]
elif student[s+1] == 0: # 오른쪽 학생이 체육복 없을 경우
student[s:s+2] = [1,1]
answer = len([i for i in student[1:n+1] if i > 0]) # 체육복 1개 이상 있는 학생 수
return answer
3. 정렬(Sort) 대표 문제: 가장 큰 수
- 기본적인 오름차순, 내림차순 정렬로 풀이할 수 없는 문제
- .sort() 메서드의 key값을 조정해서 문제 기준에 맞게 재정렬
- lambda를 잘 활용한다면 좋음
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
문제 풀이
자릿수가 다른 수들끼리의 비교:
numbers는 최대 4자리수까지만 나온다고 제한 되어 있기 때문에, 모든 수를 4자리 이상으로 만든 다음 앞 4자리까지만의 수를 비교해 정렬한다.
ex) 3, 31, 34 >>> 3333, 3131, 3434 >>> 34, 3, 31 (큰 순서대로 정렬)
def solution(numbers):
answer = ''
numbers.sort(key=lambda x: (str(x) * 4)[:4], reverse=True)
if numbers[0] == 0:
return '0'
for n in numbers:
answer += str(n)
return answer
4. 탐욕법(Greedy) 대표 문제: 큰 수 만들기
- 앞 자리수가 크게 되도록 설정해야 함
- 앞 자리와 비교해 뒤에 오는 수가 더 크다면 앞 자리 수를 빼기
- 빼야할 양을 채우지 못했다면 마지막 자리 숫자들에서 빼기
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
문제 풀이
def solution(number, k):
number = list(number) # 문자열을 리스트로
collected = []
for i, n in enumerate(number): # i: 인덱스, n: 숫자 값
while len(collected) > 0 and collected[-1] < n and k > 0: # 앞 수 보다 뒤에 올 수가 클 경우
collected.pop() # 현재 collected에 있는 값 빼기
k -= 1
if k == 0: # 반복문 도중 제거 수가 모두 만족됐을 경우 나머지를 뒤에 붙임
collected += number[i:]
break
collected.append(n)
if k > 0: # 만약 반복문이 다 돌았는데도 뺄 값이 남아있다면 끝에서 그 수 만큼 빼주기
collected = collected[:-k]
answer = ''.join(collected) # 문자열에 .join()메서드를 통해 붙여주기
return answer
5. 힙(Heap) 대표 문제: 더 맵게
- 최소/최대 원소를 반복해서 꺼내야 하는 문제 (배열 정렬 사용 시 복잡도가 많이 올라갈 때)
- 완전 이진 트리를 배열로 표현할 수 있는 장점을 활용 (힙 정렬)
- 우선 순위 큐를 구현할 때도 힙을 사용할 수 있음
문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
scoville의 길이는 1 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
입출력 예
문제 풀이
import heapq # heap을 사용하기 위한 heapq 표준 라이브러리 임포트
def solution(scoville, K):
heap = []
answer = 0
# heap에 scoville 원소들을 최소 힙 규칙으로 담는 과정
# heapq.heapify(scoville)을 통해 scoville 자체를 힙으로 만들 수도 있다.
for s in scoville:
heapq.heappush(heap, s)
while heap[0] < K: # heap[0] == 최소값
if len(heap) < 2: # 힙 내 원소가 하나만 남았다면 K 이상으로 만들 수 없으므로
return -1
mix = heapq.heappop(heap) + (heapq.heappop(heap) * 2)
heapq.heappush(heap, mix)
answer += 1
return answer
6. 동적계획법(Dynamic Programming) 대표 문제: N으로 표현
- Dynamic Programming: 주어진 최적화 문제를 재귀적인 방식으로 보다 작은 문제로 나누어 각 문제의 답을 찾고 조합하여 문제를 풀이하는 방식
- 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있다.
문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
문제 풀이
def solution(N, number):
# 집합(중복제거용)을 8개 각각 만든 s리스트
# s[i]: N을 i+1번 사용해 만들 수 있는 수의 조합(값)
s = [set() for x in range(8)] # 집합(중복제거용)을 8개 각각 만든 s리스트
for i, x in enumerate(s, start=1): # n자리수의 숫자를 미리 삽입 (ex. 5, 55, 555)
x.add(int(str(N) * i))
# N과 number가 같을 경우를 대비해 인덱스 0부터 탐색
for i in range(len(s)):
for j in range(i): # s[i]를 구하기 위해 i보다 적게 n을 사용한 집합들의 조합을 구함
for op1 in s[j]:
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 # 인덱스 + 1해야 숫자를 몇 번 사용했는지 알 수 있음
break
else: # 숫자를 8번(인덱스 상 7까지) 사용했음에도 찾지 못했을 경우(반복문이 정상 종료됐을 경우)
return -1
return answer
7. 깊이/너비 우선 탐색(DFS/BFS) 대표 문제: 여행경로
- DFS 진행 시 스택을 이용해 어느 노드에서 DFS를 진행하고 있는지 기억 (재귀적)
- BFS 진행 시 큐를 이용해 어느 노드에서 BFS를 진행하고 있는지 기록
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
문제 풀이
def solution(tickets):
t_dict = {} # 각 공항마다 가지고 있는 항공권을 저장하기 위한 딕셔너리
# 각 공항 별 항공권 딕셔너리에 저장
# key = 출발공항, value = 도착공항(의 리스트)
for t in tickets:
key, value = t[0], t[1]
if key in t_dict:
t_dict[key].append(value)
else:
t_dict[key] = [value] # 처음 삽입 시 리스트로 삽입
# 알파벳 순으로 정렬
for t in t_dict:
t_dict[t].sort(reverse=True) # .pop() 연산으로 마지막이 먼저 반환되므로 역순으로 정렬
answer = []
def travel(start):
while start in t_dict and t_dict[start]: # 출발지로부터 이어지는 항공권이 있을 경우
next_start = t_dict[start].pop()
travel(next_start)
answer.append(start) # 항공권이 없을 경우 현재 위치를 리스트에 삽입
travel('ICN')
# 도착지부터 차례대로 리스트에 삽입되므로,
# 출발지부터 차례대로 정렬하려면 역순으로 정렬되어야 함
return answer[::-1]
8. 최단 경로(다익스트라 알고리즘) 대표 문제: 배달
- 그래프로 이루어진 문제에서 최단 경로를 찾는 문제
- 다익스트라 알고리즘: 어떤 노드 하나를 시작점으로 선택하고, 나머지 노드들로부터의 최단거리를 구함
- 다익스트라 알고리즘 설명: https://m.blog.naver.com/kks227/220796029558
다익스트라 알고리즘(Dijkstra's Algorithm) (수정: 2019-08-16)
이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요. 그래프... 정말 어렵고, ...
blog.naver.com
문제 설명
N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.
위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
마을의 개수 N은 1 이상 50 이하의 자연수입니다.
road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.
입출력 예
문제 풀이
from queue import PriorityQueue # 파이썬 내장 모듈 우선순위 큐 사용
N = 5
queue = PriorityQueue()
queue.put([0,1])
dist = [float('inf')] * (N + 1) # 계산하기 편하게 N+1 길이만큼 리스트 생성
dist[1] = 0 # 1번 마을은 무조건 거리가 0
while not queue.empty():
current_cost, current = queue.get() # 현재 선택된 노드와 비용
for src, dest, cost in road:
next_cost = cost + current_cost
if src == current and next_cost < dist[dest]:
dist[dest] = next_cost
queue.put([next_cost, dest])
elif dest == current and next_cost < dist[src]:
dist[src] = next_cost
queue.put([next_cost, src])
dist'Minding's Programming > Knowledge' 카테고리의 다른 글
| [Seaborn/WordCloud] Seaborn과 Wordcloud를 활용한 시각화 (0) | 2024.10.07 |
|---|---|
| [코딩 테스트/Python] 코딩 테스트에서 자주 사용되는 Python 표준 라이브러리 (1) | 2024.10.01 |
| [CS/Python] 자료구조 & 알고리즘 정리 - 큐, 트리, 힙 (0) | 2024.09.27 |
| [CS/Python] 자료구조 & 알고리즘 정리 - 연결 리스트, 스택, 후위 표기법 (0) | 2024.09.26 |
| [CS] 알고리즘의 복잡도 (시간 복잡도) (0) | 2024.09.26 |
