탐색 문제
저장된 데이터들 중에서 원하는 값을 찾는 문제
1. 선형 탐색 알고리즘 (Linear Search Alogorithm)
- 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘
- 가장 단순하고 간단함
- 맨 앞부터 하나하나 원하는 값을 찾아본다
- 원하는 값을 찾으면 탐색을 종료한다
시간 복잡도
-
길이 n짜리의 리스트 탐색할 경우
-
최선: 리스트의 첫 번째 원소가 정답인 경우: 1번
-
최악: 리스트의 맨 마지막 원소가 정답이거나, 정답이 없을 경우: n번
-
따라서 O(n) 의 시간복잡도를 가진다
2. 이진 탐색 알고리즘(Binary Search Algorithm)
- 중간 지점을 기준으로 데이터를 반씩 나눠서 탐색
- 중간 지점 선택한 뒤, 중간 지점을 기준으로 왼쪽 혹은 오른쪽 부분만 남긴다
- 남긴 부분 중에서 다시 중간 지점을 선택한 뒤, 왼쪽 혹은 오른쪽만 남긴다
- 위 과정을 원하는 값을 찾을 때까지 반복한다
시간 복잡도
-
최선: 리스트의 중간부분이 정답일 때: 1번
-
최악: 리스트에 정답이 없는 경우: log2(n)번
-
따라서 O(logn) 의 시간 복잡도를 가짐
선형 탐색은 n이 증가함에 따라 시간 복잡도가 선형적으로 증가하지만, 이진탐색은 n이 증가해도 시간 복잡도가 아주 천천히 증가한다. 정렬된 리스트에는 이진 탐색 적용.
문제 분석
- 최소 필요 피로도 -> 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
- 소모 피로도 -> 던전을 탐험한 후 소모되는 피로도
입력
- k: 유저의 현재 피로도
- dungeons: 각 던전별 ["최소 필요 피로도", "소모 피로도"] 가 담긴 2차원 배열
출력
- 유저가 탐험할 수 있는 최대 던전 수
제한 사항
- k는 1이상 5000이하의 자연수
- dungeons의 세로 길이는 1이상 8이하
- 최소 필요 피로도는 항상 소모 피로도보다 크거나 같음 -> 모두 1이상 1000이하
- 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 같을 수 있음
풀이
가장 많은 수를 나타내야 하므로 필요 피로도로 정렬한다. 근데 어차피 이게 가장 많은 경우라고 할 수 없어서 탈락됨- 그냥 순열로 모든 경우 만들어서 계산하도록 함
from itertools import permutations
def solution(k, dungeons):
answer = []
for i in permutations(dungeons, len(dungeons)):
count = 0
c = k
cnt = 0
for a, b in i:
if c >= a:
c -= b
cnt += 1
answer.append(cnt)
return max(answer)문제 분석
- 자연수로 이루어진 두 집합 A와 B
- 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하라
입력
- (한줄에 입력) 각 집합 A: 원소의 개수, B: 원소의 개수
- 집합 A의 원소
- 집합 B의 원소
출력
- A에는 속하면서 집합 B에는 속하지 않는 원소의 개수
- 구체적인 원소를 빈 칸에 두고 오름차순으로
- 원소가 없다면 첫째 줄에만 0 출력
제한 사항
- 하나의 집합의 원소는 2,147,483,647 이하의 자연수
- 하나의 집합에 속하는 모든 원소의 값은 다르다
풀이
시간 초과 풀이
#차집합
a, b = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
answer = []
for i in A:
if i in B:
pass
else:
answer.append(i)
print(len(answer))
print(' '.join(map(str, answer)))통과된 풀이
a, b = map(int, input().split())
A = set(map(int, input().split()))
B = set(map(int, input().split()))
answer = A - B
answer = list(answer)
answer.sort()
print(len(answer))
print(' '.join(map(str, answer)))- 어떻게 풀까 생각하다가 집합이라는 단어를 보고 set이 생각났다... 사실 집합끼리 빼면 될 줄 몰랐는데 그냥 해봤는데 됐다 자료구조 공부도 해야지... 모르는 게 넘 많다 아직...
문제 분석
- 각 용액은 특성값을 가짐. 두 용액을 혼합한 용액은 각 용액의 특성값을 더한 값.
- 주어진 용액들을 2개씩 혼합하여 0에 가장 가까운 값을 찾아야 함.
입력
- N: 용액의 개수
- A1, ... AN: 용액들의 특성값 (오름차순)
출력
- 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B
제한 사항
- 2 ≤ N ≤ 100,000
- -100,000,000 ≤ Ai ≤ 100,000,000
- Ai-1 ≤ A
풀이
-
정렬되어 주어진 입력값을 보고 이진 탐색 문제임을 알아냈다.
-
처음에 비교할 최소값을 0으로 둬서 틀렸다 ~~0에 가까운 값 찾는 건데 자꾸 최소값으로 헷갈린다 ~~
그 다음 틀린 풀이
N = int(input())
A = list(map(int, input().split()))
m = A[0] + A[1]
for i in range(N):
high = N-1
low = i
while high >= low:
mid = (high + low) // 2
a = A[i] + A[mid]
if a < 0:
low = mid + 1
elif a > 0:
high = mid - 1
else:
a = 0
break
if abs(a) < abs(m):
m = a
print(m)- 1번, 3번은 값이 바르게 나오는데 2번이 틀렸길래 뭐가 문제인지 하나씩 봤다 왜 가장 간단한 친구가 틀리지...??
그래서 길이가 2인 경우만 처리를 해주었당
근데 이번에 제출하니 틀렸댄다 모지!!!!
N = int(input())
A = list(map(int, input().split()))
m = A[0] + A[1]
for i in range(N):
high = N-1
low = i
while high >= low:
if N == 2:
a = A[0] + A[1]
break
else:
mid = (high + low) // 2
a = A[i] + A[mid]
if a < 0:
low = mid + 1
elif a > 0:
high = mid - 1
else:
a = 0
break
if abs(a) < abs(m):
m = a
print(m)- 아 자기 자신이랑 하면 안되겠구나 해서 또 처음 low = i+1로 바꾸었다 근데 또 틀렸다!! 뭘까
- 애초에 for문 범위도 잘못되어서 수정했다
N = int(input())
A = list(map(int, input().split()))
m = A[0] + A[1]
for i in range(N-1):
high = N-1
low = i + 1
while high >= low:
if N == 2:
a = A[0] + A[1]
break
else:
mid = (high + low) // 2
a = A[i] + A[mid]
if a == 0:
m = a
break
else:
if a < 0:
low = mid + 1
elif a > 0:
high = mid - 1
else:
a = 0
break
if abs(a) < abs(m):
m = a
print(m)- 그냥 a가 0일 경우를 처리를 안 했다 수정 완료 코드를 줄이려면 더 줄일 수 있을 것 같다
주석 달고 수정한 최종 코드
N = int(input())
A = list(map(int, input().split()))
m = A[0] + A[1] # 초기 용액 값 설정
for i in range(N-1):
high = N-1
low = i + 1 # 자기 자신 제외
while high >= low: # 이분 탐색 시작
mid = (high + low) // 2
a = A[i] + A[mid] # 기준 용액 + 중간 용액 값
if a == 0: # 0이면 종료
m = a
break
else:
if a < 0: # 0보다 작으면 오른쪽으로
low = mid + 1
elif a > 0: # 0보다 크면 왼쪽으로
high = mid - 1
else:
a = 0 # 값이 0이면 종료
break
if abs(a) < abs(m): # 0과 가까운지 비교하여 값 업데이트
m = a
print(m)
꾸준히 공부하기