Chapter 06. 기본 탐색 알고리즘

기본 탐색 알고리즘 (기초 문제 풀이)

혼자 힘으로 풀어보기

문서 검색: https://www.acmicpc.net/problem/1543

문제 제목: 문서 검색
문제 난이도: 하(Easy)
문제 유형: 탐색
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 문서의 길이는 최대 2,500이고 단어의 길이는 최대 50입니다.

• 단순히 모든 경우의 수를 계산하여 문제를 해결할 수 있습니다.

• 시간 복잡도 O(NM)의 알고리즘으로 해결할 수 있습니다.

• 문서와 단어의 위치를 맞추어서 반복적으로 비교합니다.
  
  
  
  

소스 코드

document = input()
word = input()

index = 0
result = 0

while len(document) - index >= len(word):
    # 문서에서 보고 있는 단어가 찾고자 하는 단어인 경우
    if document[index:index + len(word)] == word:
        result += 1
        index += len(word)
    else:
        index += 1

print(result)

혼자 힘으로 풀어 보기

새: https://www.acmicpc.net/problem/1568

문제 제목: 새
문제 난이도: 하(Easy)
문제 유형: 탐색
추천 풀이 시간: 20분

문제풀이 핵심 아이디어

• N이 최대 1,000,000,000입니다.
• K가 반복적으로 증가하므로, 날아가는 새의 마리 수는 빠르게 증가합니다.
• 따라서 문제에서 요구하는 대로 단순히 구현하여 정답 처리를 받을 수 있습니다.

소스 코드

n = int(input())
result = 0
k = 1

#모든 새가 날아갈 때까지
while n != 0:
    if k > n:
        k = 1
    n -= k
    k += 1
    result += 1

print(result)

혼자 힘으로 풀어 보기

베스트 셀러: https://www.acmicpc.net/problem/1302

문제 제목: 베스트셀러
문제 난이도: 하(Easy)
문제 유형: 탐색
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 본 문제는 가장 많이 등장한 문자열을 출력하는 문제와 동일합니다.
• 등장 횟수를 계산할 때는 파이썬의 Dictionary 자료형을 이용하면 효과적입니다.

소스 코드

n = int(input())

books = {}

for _ in range(n):
    book = input()
    if book not in books:
        books[book] = 1
    else:
        books[book] += 1
target = max(books.values())
array = []

for book, number in book.item():
    if number == target:
        array.append(book)

print(sorted(array)[0])

혼자 힘으로 풀어보기

트로피 진열: https://www.acmicpc.net/problem/1668

문제 제목: 트로피 진열
문제 난이도: 하(Easy)
문제 유형: 탐색
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

• 선반 위에 올려져 있는 트로피들에 대하여 왼쪽에서, 오른쪽에서 봤을 때 보이는 트로피의 수를 각각 구합니다.
• 트로피의 개수 N이 최대 50이므로 단순히 구현하면 됩니다.
  

소스 코드

def ascending(array):
    now = array[0]
    result = 1
    for i in range(1, len(array)):
        if now < array[i]:
            result += 1
            now = array[i]
    return result

n = int(input())
array = []

for _ in range(n):
    array.append(int(input()))

print(ascending(array))
array.reverse()
print(ascending(array))

혼자 힘으로 풀어 보기

성 지키기: https://www.acmicpc.net/problem/1236

문제 제목: 성 지키기
문제 난이도: 하(Easy)
문제 유형: 탐색
추천 풀이 시간: 20분

• 모든 행과 모든 열에 한 명이상의 경비원이 있어야 합니다.
• 행 기준, 열 기준으로 필요한 경비원의 수를 각각 계산하여 더 큰 수를 출력합니다.
  
  

소스 코드

n, m = map(int, input().split())
array = []

for _ in range(n):
    array.append(input())

row = [0] * n
column = [0] * m

for i in range(n):
    for j in range(m):
        if array[i][j] == 'X':
            row[i] = 1
            column[j] = 1

row_count = 0
for i in range(n):
    if row[i] == 0:
        row_count += 1

column_count = 0
for j in range(m):
    if column[j] == 0:
        column_count += 1

print(max(row_count, column_count))

혼자 힘으로 풀어 보기

공유기 설치: https://www.acmicpc.net/problem/2110

문제 제목: 공유기 설치
문제 난이도: 중(Medium)
문제 유형: 이진 탐색
추천 풀이 시간: 40분

문제 풀이 핵심 아이디어

• 집의 개수 N은 최대 200,000이며, 집의 좌표 X는 최대 1,000,000,000입니다.

• 이진 탐색을 이용하여 O(N * logX)에 문제를 해결할 수 있습니다.

• 가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾습니다.

• 반복적으로 Gap을 설정하며, C개 이상의 공유기를 설치할 수 있는 경우를 찾습니다. (N = 5, C = 3)
  
  
  
  
  
  

소스 코드

n, c = list(map(int, input().split(' ')))

array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)

start = array[1] - array[0]
end = array[-1] - array[0]
result = 0

while(start <= end):
    mid = (start + end) //2 # mid는 Gap을 의미합니다.
    value = array[0]
    count = 1
    for i in range(1, len(array)):
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c: # c개 이상의 공유기를 설치할 수 있는 경우
        start = mid + 1
        result = mid
    else: # c개 이상의 공유기를 설치할 수 없는 경우
        end = mid - 1

print(result)

혼자 힘으로 풀어 보기

중량제한: https://www.acmicpc.net/problem/1939

문제 제목: 중량제한
문제 난이도: 중상(Hard)
문제 유형: 이진 탐색
추천 풀이 시간: 1시간

문제 풀이 핵심 아이디어

• 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000입니다.
• 이진 탐색을 이용하여 O(M * logC)에 문제를 해결할 수 있습니다.
• 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 이진 탐색으로 찾습니다.
• 반복적으로 중량을 설정하며, 이동이 가능한 경우를 찾습니다. (시작 노드: 1, 도착 노드: 3)
  
  
  
  
  
  

소스 코드

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]

def bfs(c):
    queue = deque([start_node])
    visited = [False] * (n+1)
    visited[start_node] = True
    while queue:
        x = queue.popleft()
        for y, weight in adj[x]:
            if not visited[y] and weight >= c:
                visited[y] = True
                queue.append(y)
    return visited[end_node]

start = 1000000000
end = 1

for _ in range(m):
    x, y weight = map(int, input().split())
    adj[x].append((y, weight))
    adj[y].append((x, weight))
    start = min(start, weight)
    end = max(end, weight)

start_node, end_node = map(int, input().split())

result = start
while(start <= end):
    mid = (start + end) // 2 # mid는 현재의 중량을 의미합니다.
    if bfs(mid): # 이동이 가능하므로, 중량을 증가시킵니다.
        result = mid
        start = mid + 1
    else: #이동이 불가능하므로, 중량을 감소시킵니다.
        end = mid -1

print(result)