- 두 수의 합 구하기 정수 배열이 주어졌을 때, 지정된 합계가 되는 두 개의 요소를 찾는 문제를 해결해 보겠습니다. 먼저 기본 접근법의 시간 복잡도를 분석한 후, O(n) 알고리즘으로 개선하겠습니다.
def solve():
data = [11, 7, 45, 67, 134, 5, 83, 55, 106, 33, 57, 82, 6, 24, 87, 61, 3, 39, 6, 26]
target = 13
result, a, b = find_pair(data, target)
if result == 1:
print('가능합니다: %d + %d = %d' % (a, b, target))
else:
print('불가능합니다')
# 방법1: 해시 테이블 활용 - 중복 없는 배열에 적합, 시간 복잡도 O(n)
def find_pair(arr, target):
lookup = set(arr)
for val in arr:
complement = target - val
if complement in lookup:
return 1, val, complement
return None, None, None
# 방법2: 정렬 후 투 포인터 방식 - 정렬로 인해 O(n log n)
def find_pair_sorted(arr, target):
sorted_arr = sorted(arr)
left, right = 0, len(sorted_arr) - 1
while left < right:
current_sum = sorted_arr[left] + sorted_arr[right]
if current_sum > target:
right -= 1
elif current_sum < target:
left += 1
else:
return 1, sorted_arr[left], sorted_arr[right]
return None, None, None
분석: 첫 번째 방법은 해시 셋을 사용하여 각 요소에 대해 상수 시간 조회가 가능하므로 O(n) 복잡도를 가집니다. 두 번째 방법은 정렬에 O(n log n)이 소요됩니다.
- 주식을 한 번 사고팔기 가격 배열에서 최대 한 번의 거래로 얻을 수 있는 최대 수익을 계산합니다. i번째 요소는 i번째 날의 주가입니다.
예제: prices = [12, 15, 14, 8, 11, 10, 12], 최대 수익은 4입니다.
def calculate():
prices = [12, 15, 14, 8, 11, 10, 12]
profit = max_profit(prices)
print(profit)
def max_profit(prices):
"""최소값과 최대 차이값을 추적하며 한 번의 거래로 가능한 최대 수익 계산"""
max_return = 0
min_price = prices[0]
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_return:
max_return = price - min_price
return max_return
이 알고리즘은 한 번의 순회로 O(n) 시간 복잡도로 최대 수익을 구합니다.
- 단일 연결 리스트에서 순환 检测 단일 연결 리스트의 헤드 포인터가 주어졌을 때, 순환이 있으면 순환의 길이를 반환하고 그렇지 않으면 0을 반환합니다.
예제: head → 3 → 8 → 7 → 1 → 2 → 3 → 4 → 5 → 1, 순환 길이 = 5
class Node:
def __init__(self, val=0):
self.val = val
self.next = None
def find_cycle_length(head):
"""방문한 노드를 추적하여 순환 检测"""
if head is None:
return "순환 아님"
visited = []
index = 0
current = head
while current.next:
index += 1
node_id = id(current)
if node_id in visited:
return index - visited.index(node_id)
visited.append(node_id)
current = current.next
return "순환 아님"
# 방법2: 플로이드 순환 검출 알고리즘 (토끼와 거북이)
def find_cycle_floyd(head):
slow = fast = head
count = 0
while fast and fast.next:
slow = slow.next
fast = fast.next.next
count += 1
if slow == fast:
return count + 2
return 0
- IP 주소 생성 숫자로만 구성된 문자열이 주어졌을 때, 모든 유효한 IP 주소를 반환합니다.
예제: 입력 "10112", 출력 ["1.0.1.12", "1.0.11.2", "10.1.1.2"]
def generate():
s = '10112'
addresses = restore_ip(s)
for addr in addresses:
print(addr)
def restore_ip_str(s):
"""가능한 모든 IP 주소 조합 생성"""
result = []
n = len(s)
def is_valid(segment):
"""IP 세그먼트 유효성 검사"""
if not segment:
return False
if segment[0] == '0' and len(segment) > 1:
return False
return int(segment) <= 255
# 3중 중첩 루프로 4개 세그먼트 분할 시도
for i in range(3):
for j in range(i + 1, i + 4):
for k in range(j + 1, j + 4):
if i < n and j < n and k < n:
part1 = s[:i+1]
part2 = s[i+1:j+1]
part3 = s[j+1:k+1]
part4 = s[k+1:]
if all(map(is_valid, [part1, part2, part3, part4])):
result.append(f"{part1}.{part2}.{part3}.{part4}")
return result
- 주식 거래 (최대 2회) 가격 배열에서 최대 2번의 거래로 얻을 수 있는 최대 수익을 계산합니다.
def compute():
prices = [12, 15, 14, 8, 11, 10, 12]
result = max_profit_two_trades(prices)
print(result)
def max_profit_two_trades(prices):
"""두 번의 거래로 가능한 최대 수익 계산"""
n = len(prices)
if n < 4:
return 0
max_profit = 0
# 각 지점을 기준으로 분할하여 두 거래의 수익 합산
for split in range(1, n - 1):
left_prices = prices[:split + 1]
right_prices = prices[split:]
min_left = float('inf')
max_left = 0
for p in left_prices:
min_left = min(p, min_left)
max_left = max(max_left, p - min_left)
min_right = float('inf')
max_right = 0
for p in right_prices:
min_right = min(p, min_right)
max_right = max(max_right, p - min_right)
max_profit = max(max_profit, max_left + max_right)
return max_profit
- 개구리 점프 (최소 점프 수) 각 요소가 해당 위치에서 가능한 최대 점프 거리를 나타내는 배열이 주어집니다. 시작 위치는 첫 번째 요소이고, 배열 끝에 도달할 수 있다고 가정합니다. 필요한 최소 점프 수를 계산합니다.
예제: A = [2, 1, 3, 1, 1], 출력 = 2
def jump():
arr = [2, 1, 3, 1, 1]
min_jumps = minimum_jumps(arr)
print(min_jumps)
def minimum_jumps(arr):
"""그리디 알고리즘으로 최소 점프 수 계산"""
jumps = 0
max_reach = 0
boundary = 0
for i, step in enumerate(arr):
max_reach = max(max_reach, i + step)
if boundary == i:
boundary = max_reach
jumps += 1
return jumps
- 최대 인덱스 거리 배열이 주어졌을 때, A[i] < A[j]이고 i < j인 조건에서 최대 j - i를 찾습니다.
예제: [5, 3, 4, 0, 1, 4, 1], 최대 거리 = 4 (i=1에서 A[i]=3, j=5에서 A[j]=4)
def distance():
arr = [5, 3, 4, 0, 1, 4, 1]
max_dist = find_max_distance(arr)
print(f"최대 거리: {max_dist}")
def find_max_distance(arr):
"""하락 시퀀스를 기록하고 역방향 스캔으로 최대 거리 계산"""
n = len(arr)
descent_mark = []
current_min = arr[0]
# 각位置的이전 최소값보다 작은지 확인
for i in range(n):
if i == 0:
descent_mark.append('S') # Start
else:
if arr[i] < current_min:
descent_mark.append('S')
current_min = arr[i]
else:
descent_mark.append('X')
i = j = n - 1
max_distance = 0
while i >= 0:
if descent_mark[i] == 'X':
i -= 1
continue
while arr[j] <= arr[i] and i < j:
j -= 1
if i < j and j - i > max_distance:
max_distance = j - i
i -= 1
return max_distance
- 한 번만出现的 숫자 찾기 다른 모든 숫자가 두 번出现하고 하나의 숫자만 한 번出现합니다. 해당 숫자를 찾으세요.
예제: [2, 35, 8, 16, 8, 2, 7, 35], 결과: 7
def locate():
arr = [2, 35, 8, 16, 8, 2, 7, 35]
unique = find_unique(arr)
print(f"唯一한 숫자: {unique}")
def find_unique(arr):
"""딕셔너리로 각 숫자의出現 횟수 추적"""
counter = {}
seen = set()
for num in arr:
if num in seen:
counter[num] = 2
else:
seen.add(num)
counter[num] = 1
for key, count in counter.items():
if count == 1:
return key
- 점프 게임 - 끝 도달 가능성 각 요소가 해당 위치에서 가능한 최대 점프 거리를 나타내는 배열이 주어집니다. 시작 위치에서 배열 끝에 도달할 수 있는지 判断합니다.
예제: A = [2, 1, 3, 1, 1] → True, A = [3, 2, 1, 0, 1] → False
def check():
a = [2, 1, 3, 1, 1]
b = [3, 2, 1, 0, 1]
print(can_reach(b))
print(can_reach(a))
def can_reach(arr):
"""현재 위치에서 도달 가능한 가장 먼 지점을 추적"""
farthest = arr[0]
n = len(arr)
for i, step in enumerate(arr):
if i == farthest:
farthest += step
if farthest >= n - 1:
return True
return False
- 가장 가까운 큰 수 구성 두 배열로 표현된 정수가 주어집니다. 첫 번째 정수의 배열을 재배열하여 두 번째 정수보다 크면서 가장 가까운 값을 구합니다.
예제: [1, 2, 3, 4]와 [2, 4, 1, 0], 결과: [2, 4, 1, 3]
def compare():
x = [1, 2, 3, 4]
y = [2, 4, 1, 0]
result = nearest_greater(x, y)
print(f"결과: {result}")
def nearest_greater(source, target):
"""각 자리에 가능한 가장 작은 큰 숫자 배치"""
source_sorted = sorted(source)
answer = []
for t in target:
for s in source_sorted:
if s >= t:
answer.append(s)
source_sorted.remove(s)
break
return answer
- 회전 정렬된 배열의 최소값 오름차순으로 정렬된 배열을 한 번 회전시켰을 때, 최소값을 찾습니다.
def rotate():
arr = [3, 4, 5, 6, 1, 2]
minimum = find_minimum(arr)
print(f"최소값: {minimum}")
def find_minimum(arr):
"""이진 검색을 활용하여 최소값 찾기"""
left = 0
right = len(arr) - 1
minimum = arr[left]
while left < right:
mid = left + (right - left) // 2
minimum = min(arr[left], minimum)
if arr[mid] == arr[left] and arr[mid] == arr[right]:
left += 1
elif arr[mid] >= arr[left]:
left = mid + 1
minimum = min(arr[left], minimum)
else:
minimum = min(arr[mid], minimum)
right = mid - 1
return minimum
- 배열의 분할점 찾기 배열에서 왼쪽의 모든 요소보다 크거나 같고 오른쪽의 모든 요소보다 작거나 같은 요소를 찾습니다. O(n) 시간 복잡도가 요구됩니다.
def partition():
arr = [1, 0, 1, 0, 1, 2, 3]
points = find_partition_points(arr)
print(points)
def find_partition_points(arr):
"""양쪽 스캔으로 분할점 찾기"""
n = len(arr)
markers = [0] * n
# 왼쪽에서 오른쪽으로 스캔: 왼쪽 모든 값보다 크거나 같은지 확인
max_so_far = arr[0]
for i in range(n):
if arr[i] >= max_so_far:
max_so_far = arr[i]
markers[i] = 1
# 오른쪽에서 왼쪽으로 스캔: 오른쪽 모든 값보다 작거나 같은지 확인
min_so_far = arr[-1]
results = []
for i in range(n - 1, -1, -1):
if arr[i] <= min_so_far:
min_so_far = arr[i]
if markers[i] == 1:
results.append(i)
return results