[알고리즘 스터디/Python] 7월 2주차

  이번 주 주제는 '그리디'였다. 그리디 문제 5문제와 각자 풀고 싶은 5문제를 풀어오고 풀이를 진행했다!

빅프로젝트 마무리 후 2주 만의 스터디였고, 간만에 여유롭게 문제 풀 수 있어서 뿌듯하기도 하고 많이 배운 한 주 였다. 😃

---

 

1. 백준 1747. 소수&팰린드롬

1747번: 소수&팰린드롬

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

 

 

 팰린드롬 문제는 많이 풀어봐서 쉽게 접근할 수 있었지만, 소수 판별에서 시간초과가 나서 해결하는데 시간이 걸렸다. 유튜브에서 소수 판별 알고리즘 팁을 얻었고, 나의 제곱근 수까지만 검사를 하면 된다는 걸 배웠다! 해결한 코드는 다음과 같다.

 

# python

import math

def divide_check(n):
    div_num = 2
    while(div_num < int(math.sqrt(n)+1)):
        if n % div_num:
            div_num += 1
        else:
            return 0
    return 1
            
def palin_check(n):
    check = str(n)
    if str(n) == check[::-1]:
        return 1
    else: return 0

n = int(input())

while (True):
    if n == 1:
        print(2)
        break
    elif (divide_check(n) == 1) and (palin_check(n) == 1):
        print(n)
        break
    else:
        n += 1

 

2. 백준 2212 센서

2212번: 센서

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

 

 

 그리디 알고리즘 문제다! 처음엔 문제를 어떻게 접근해야할지 감을 얻기 어려웠다. 이 문제는 거리의 합의 최솟값을 구해야하므로 각 좌표의 차이를 구해서 정렬 후 가장 차이가 많이 나는 곳을 분리해주면 되는 문제였다. 

 

# python

n = int(input())
k = int(input())
sensor = sorted(list(map(int, input().split())))

if k >= n: 
    print(0)
else:
    sensor_minus = []
    for i in range(len(sensor) - 1):
        tmp = sensor[i+1] - sensor[i]
        sensor_minus.append(tmp)
        
    sensor_minus.sort(reverse=True)
        
    for _ in range(k-1):
        sensor_minus.pop(0)

    print(sum(sensor_minus))

 

3. 백준 13164 행복 유치원

13164번: 행복 유치원

문제

  행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

  입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

  티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

 

 그리디 알고리즘 문제. 위의 센서 문제와 접근법이 똑같다. 센서 문제를 해결하니 쉽게 풀 수 있었다.

# python

n, k = map(int, input().split())
members = list(map(int, input().split()))
member_minus = []

for i in range(n-1):
    member_minus.append(members[i+1] - members[i])

member_minus.sort()

for i in range(k-1):
    member_minus.pop()
    
print(sum(member_minus))

 

4. 백준 9251 LCS

9251번: LCS

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

 

 dp문제로 분류되는데, 최장 공통 부분 수열을 구하는 방식에 대한 공부와 이해가 필요했다. 유튜브 강의를 통해 이해 후 코드 적용했다. 아직 100% 이해한 느낌은 아니기에 더 공부가 필요할 것 같다!

# 상향식 버전
def lcs(x, y):
    x, y = [' '] + x, [' '] + y
    m, n = len(x), len(y)
    c = [[0 for _ in range(n)] for _ in range(m)] # dp
    for i in range(1, m):
        for j in range(1, n):
            if x[i] == y[j]: 
                c[i][j] = c[i - 1][j - 1] + 1 # 끝이 같을 때 
            else: 
                c[i][j] = max(c[i][j - 1], c[i - 1][j]) # 끝이 다를 때
    return c[m-1][n-1]

 
s1 = list(input())
s2 = list(input())
ans = lcs(s1, s2)
print(ans)

 

5. 프로그래머스 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

문제

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

- 섬의 개수 n은 1 이상 100 이하입니다.
- costs의 길이는 ((n-1) * n) / 2이하입니다.
- 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
- 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.

 

 이 문제는 그리디 문제지만, 최소신장트리를 구하기 위한 크루스칼 알고리즘과 합집합 알고리즘에 대한 이해가 필요했다. 크루스칼 알고리즘을 유튜브에서 공부 후 코드 적용했다. 역시나 공부가 더 필요한 부분인 것 같다!

 # 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    # 더 작은 값을 부모로 가지게 함
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
def solution(n, costs):
    v, e = n, len(costs) # 노드의 개수와 간선(Union 연산)의 개수 입력 받기
    parent = [0] * (v + 1) # 부모 테이블 초기화하기
    answer = 0
    costs = sorted(costs, key = lambda x : (x[2]))
    
    # 부모 테이블 상에서, 부모를 자기 자신으로 초기화
    for i in range(1, v + 1):
        parent[i] = i
    
    # 간선 하나씩 확인
    for each in costs:
        a, b, cost = each
        # 사이클이 발생하지 않는 경우에만 집합에 포함
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += cost

    return answer

 

6. 프로그래머스 다리를 지나는 트럭

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한사항

- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

 

 이 문제는 큐를 이용해서 해결하는 문제였다. 오늘 문제 중에선 쉬운 편에 속하는 문제였던 것 같다! 다만 시간 복잡도에서 처음에 오답을 받았는데 sum(list)가 시간복잡도를 가중시키는 요소라는 것을 배웠다. 이제 쉬운 문제여도 계속 시간 복잡도를 비롯한 성능을 고려하면서 문제를 풀어야 함을 배웠다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights) # pop(0)의 시간 복잡도를 줄이기 위해 얘도 deque로 바꿈
    bridge = deque([0 for _ in range(bridge_length)])
    answer = 0
    sum_bridge = 0
    
    while truck_weights:
        sum_bridge -= bridge.popleft()
        
        if sum_bridge + truck_weights[0] > weight:
            bridge.append(0)
        else:
            ready = truck_weights.popleft()
            bridge.append(ready)
            sum_bridge += ready
            
        answer += 1
    
    # print(answer, bridge)
    answer += bridge_length
        
    return answer

 

---

스터디까지 못 해결한 문제는 다음과 같다.

 

7. 백준 1461 도서관 [해결]

https://www.acmicpc.net/problem/1461

1461번: 도서관

문제

  세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 정답을 출력한다.

 

 이 문제는 양수와 음수를 고려해서 문제를 해결했어야 했다. 문제를 너무 어렵게 접근하면서 풀지 못했던 것 같다. 이후 스터디를 통해 이해해서 풀이에 성공했다.

# 포인트 : 양수 따로, 음수 따로, 가장 큰 값 구하기

import math

n, m = map(int, input().split())
book_position = sorted(list(map(int, input().split())))

negative = []
positive = []

for book in book_position:
    if book > 0:
        positive.append(book)
    else:
        negative.append(book)

positive.sort(reverse=True)

distance = []

for i in range(0, len(negative), m):
    distance.append(abs(negative[i]))
    
for i in range(0, len(positive), m):
    distance.append(abs(positive[i]))

distance.sort()
ans = 0

for i in range(len(distance)-1):
    ans += distance[i] * 2

ans += distance[-1]

print(ans)

 

8. 백준 16120 PPAP [해결]

https://www.acmicpc.net/problem/16120

16120번: PPAP

문제

  bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다. PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.

• P는 PPAP 문자열이다.
• PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.

  예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

입력

첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

출력

첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.

 

 이 문제는 stack 자료구조를 이용한 문제풀이 접근법에서 너무 어렵게 생각해서 못풀었던 것 같다. 생각보다 간단히 해결할 수 있는 문제여서 스터디를 통해 많이 배웠다! 그리고 deque()는 [:] 을 통한 slice가 불가하다는 것도 알게 됐다.

origin = list(input())
stack = []

for o in origin:
    stack.append(o)
    if (len(stack) >= 4) and (stack[-4:] == ['P', 'P', 'A', 'P']):
        stack[-4:] = ['P']

if stack == ['P']:
    print('PPAP')
else:
    print('NP')

 

9. 백준 2015 수들의 합4 [미해결]

https://www.acmicpc.net/problem/2015

2015번: 수들의 합 4

문제

A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.

N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 주어진다. 주어지는 정수의 절댓값은 10,000을 넘지 않는다.

출력

첫째 줄에 합이 K인 부분합의 개수를 출력한다.

 

 누적합 알고리즘은 아직 익숙하지 못한 상태인 것 같다. 더 공부가 필요하다..!

# python

 

10. 백준 11000 강의실 배정 [미해결]

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

 

 함께 스터디 중이신 분이 heapq 자료구조를 통해 문제를 푸셨는데 아직 heapq 공부가 더 필요한 것 같다.

# python

 

11. 백준 27980  문자열 게임 [미해결]

https://www.acmicpc.net/problem/27980

27980번: 문자열 게임

문제

건덕이는 문자가 일렬로 적혀있는 보드에서 게임을 하고 있다. 보드에는 N개의 알파벳 대문자가 나란히 적혀있다. 건덕이는 또 다른 M자리 영어 단어를 가지고 게임을 진행한다.

우선 보드의 한 지점에서 첫 번째 문자가 보드의 문자와 일치하는지 확인한다. L(왼쪽) 또는 R(오른쪽) 방향으로 이동한 후에 다음 문자와 보드의 문자가 일치하는지 확인한다. 일치할 경우 점수를 1점 얻는다. 단, 이동한 후 보드 바깥으로 벗어날 수 없다. 건덕이가 가지고 있는 단어의 끝에 도달하면 게임을 종료한다.

예를 들어, 보드에 "KONKUK" 이라는 문자가 적혀있고, "KONDUCK" 이라는 단어로 게임을 시작한다면, 2번째 문자부터 RRRRLL 순으로 이동한다면 마지막 1개의 문자만이 일치해 점수를 1점 얻는다. 최대 점수를 얻으려면, 1번째 문자부터 RRRRLR 순으로 이동하면 된다. 이 경우 "KONU"가 일치하여 점수를 4점 얻는다.

보드와 가지고 있는 단어가 주어졌을 때, 건덕이가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 보드의 길이와 건덕이가 가지고 있는 문자열의 길이를 나타내는 정수 N, M이 공백으로 구분되어 주어진다. (2≤ N, M ≤5000)

둘째 줄에는 보드의 문자가 순서대로 주어진다.

셋째 줄에는 가지고 있는 문자열이 주어진다.

이 때, 두 문자열은 모두 알파벳 대문자로만 구성되어 있다.

출력

건덕이가 얻을 수 있는 최대 점수를 출력한다.

 

 이 문제 다이나믹 프로그래밍 문제인데 .... 매우 열심히 도전했지만 패배했다. 우리 스터디에도 아직 정답자 분이 안계시다. 맞힌 사람도 32명이라 질문 게시판도 텅 비어있다. 풀고 싶다.......

  주어진 예제는 다 맞는데, 시간 초과로 인해 오답 중이다. 시간을 줄일 수 있는 방법을 모색해봐야겠다!

 

# python