꾸준히 개발하기

Lv2가 맞나 싶은 난이도... 문제에 대한 감이 어느정도 있어야 이게 그리디로 푸는게 맞는지 아닌지 아는 것 같다.

문제

https://programmers.co.kr/learn/courses/30/lessons/42860

접근 방법

크게 상하 / 좌우로 움직일 때로 나뉜다. 

상하 이동 : 알파벳 바꿀 때 (어차피 A인 경우에는 0이므로 그냥 계산해주면 됨)
1) N(78) 이전 문자로 변경 시 위로 이동 -> 이동횟수 = 해당문자아스키값 - 65(A)
2) 이외에는 아래로 이동 -> 이동횟수 = 90(Z) - 해당문자아스키값 + 1 (+1은 A->Z 변경)
-> 더 작은 값으로 설정하기

* 여기에서 ord() 메서드를 사용해주면 해당 문자의 아스키값을 리턴해준다

좌우 이동 ** 풀이 참고 **
- 기본 최소 이동 횟수 : 길이 -1
- 연속되는 A가 있을 때, 그것의 왼쪽이나 오른쪽부터 시작하며 알파벳을 변경하는 것이 가장 효율적
(기존, 연속A의 왼쪽에서 시작, 연속A의 오른쪽에서 시작) 중 min값이 답
- 연속되는 A가 있는 곳에는 굳이 갈 필요 없음, 그 부분을 제외하고 수정하는 경우 계산
- 다만 연속되는 A가 여러 개인 경우, 가장 긴 부분을 안 가는 것이 효율적임

여기가 도저히 이해가 안되서 블로그를 많이 뒤져봤다 보니까 원래는 왼쪽만 계산해줘도 됬는데, 2022년 기준 테스트케이스가 추가되어 오른쪽을 계산하는(뒤에서 시작하는) 부분이 추가되어야 한다고 한다. 이해를 돕기 위해 이미지를 하나 첨부한다.

코드

# 2022-04-06
# 프로그래머스 고득점 kit 그리디 - 조이스틱 
# https://programmers.co.kr/learn/courses/30/lessons/42860

def solution(name):
    answer = 0

    min_move = len(name) - 1
    
    for i, char in enumerate(name):
        # 알파벳 변경 최솟값 추가
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)

        # 해당 알파벳 다음부터 연속된 A 문자열 찾기
        next = i+1
        while next < len(name) and name[next] == 'A':
            next += 1
        
        # 기존, 연속된 A의 왼쪽 시작방식, 연속된 A의 오른쪽시작방식 비교 및 갱신
        min_move = min([min_move, 2*i+len(name)-next, i+2*(len(name) - next)])

    # 상하이동 횟수 + 좌우이동 횟수     
    answer += min_move
    return answer

5 3
1
2
8
4
9

3

1차 접근 (2022.1.18 못품)

가능한 집의 좌표가 10억이기 때문에 탐색 범위가 매우 크다. 따라서 이진탐색으로 접근해야한다는 점까지는 캐치를 했는데, 이진 탐색은 특정 값을 찾는 알고리즘인데 공유기 설치를 하는 범위에 어떻게 적용이 되어야 하는지 감이 잘 안 왔다. 얼마 전에 풀었던 떡볶이 떡 자르기 문제와 유사하다는 것까지는 눈치를 챘는데, 그 뒤로 2시간동안 헤매다가 결국 해설을 참고해서 이해를 한다.

해설 1

이진 탐색으로 가장 인접한 두 공유기 사이의 거리를 조절해가며, 매번 실제로 공유기를 설치하여 C보다 많은 개수로 공유기를 설치할 수 있는지 체크하여 문제를 해결한다. 다만 가장 인접한 두 공유기 사이의 거리의 최댓값을 찾아야 하므로, C보다 많은 개수로 공유기를 설치할 수 있다면 가장 인접한 두 공유기 사이의 거리의 값을 증가시켜서 더 큰 값에 대해서도 성립하는지 체크하기 위해 다시 탐색을 수행한다. 

따라서 매번 가장 인접한 두 공유기 사이의 거리 (gap)의 최소값, 최대값을 계산해주면 될 것이다. 

{1,2,4,8,9} 인 수열에 설치해야 하는 공유기의 수 C = 3이라고 해보자.

현재 gap은 1~8 사이의 값이다.  gap = [1,8] 사이

1) gap의 값을 중간에 해당하는 4로 설정하면, 공유기를 2개밖에 설치할 수 없다. 따라서 범위를 더 줄일 필요가 있다. 따라서 범위를 [1,3]으로 수정한다. 

2) 범위가 1~3이므로 gap의 값을 중간에 해당하는 2로 설정한다. 이 경우 공유기를 3개 설치할 수 있다. 다만 더 큰 값에 에 대해서도 확인해볼 필요가 있으므로 현재의 gap 값을 저장하고 gap의 값을 증가시켜서 gap이 더 커졌을 때도 가능한지 확인할 필요가 있다. 따라서 범위가 [1,3]인 상태에서 범위를 [3,3]으로 수정한다. 

3) 범위가 3~3이므로 gap의 값을 중간에 해당하는 3으로 설정한다. 이 경우 공유기를 3개 설치할 수 있다. gap이 더 커졌을 떄도 확인해봐야 하나, 현재 gap 범위는 더이상 변경이 불가능하다. 따라서 gap=3이 최적의 경우이다.

--> 솔직히 이코테 책에 있는 풀이 잘 모르겠다. 다른 블로그를 참고했다...

해설2

공유기 설치 길이를 움직여(이분 탐색을 통해) 적절한 집에 설치 가능한지 살펴보는 문제.

거리가 주어지면 공유기(router)를 몇 개 설치할 수 있는지 계산하는 router_setting 함수

첫번째 집을 start로, 첫집과 끝집의 차이을 end로 둔다

 1) 중간값mid로 충분한 설치 장소를 찾지 못했다면 거리를 줄여주고

 2) 설치된 집이 더 많다면 거리를 늘려준다.

Python

# 2022-01-18
# 이코테 ch15 이진 탐색 문제 Q29 공유기 설치
# https://www.acmicpc.net/problem/2110

import sys

input = sys.stdin.readline

n, c = map(int, input().split())
house = [int(input()) for _ in range(n)]
house.sort()

# 해당 거리를 유지하며 공유기를 몇대까지 설치 가능한지
def router_setting(dist):
    count = 1
    cur_house = house[0]  # 시작점 (공유기 설치)
    for i in range(1, n):  # 집 모두를 순회
        # 이전 집에서 해당 거리보다 멀리 떨어진 집이라면
        if cur_house + dist <= house[i]:
            count += 1  # 공유기 설치
            cur_house = house[i]  # 공유기 설치된 집 갱신

    return count


start = 1
end = house[-1] - house[0]  #
answer = 0

while start <= end:
    mid = (start + end) // 2
    if router_setting(mid) >= c:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1

print(answer)

회고

이진탐색 진짜 어렵다.... 토폴로지 풀 때랑 비슷한 갑갑함이다. 익숙해질 때까지 부딪혀보자 ㅠㅠ 해설을 한시간동안이나 찾아보고 읽어봤다

해당 문제는 백준 2805번 나무 자르기와 동일한 문제이나, 백준이 시간 제한이 1초로 더 짧다.

입력 가능한 값의 범위가 매우 커서 이진 탐색을 사용해서 가능한 경우를 찾아야겠다고 접근해야 한다.

다만, 여기에서 알고리즘에 매몰되는 실수를 했다.

내가 생각했던 방식은 떡의 길이를 입력받고 해당 리스트 안에서 이진탐색을 통해 중간값을 찾은 뒤, 잘라낸 길이의 총합을 target(m)과 비교하기였다. 이렇게 되면 입력받은 리스트 안에서 중간 값이지, 전체 길이의 평균이 아니다.... ㅠㅠ 사실 이 부분도 추가로 파고들면 어찌저찌 풀 수 있을 것 같기는 하다. 

잘못 접근한 방식 1. 재귀함수로 이분 탐색을 구현하고, 만약 엇갈린 경우 시작값과 끝값 사이에 가능한 경우가 있다고 생각하고 그 안에서 찾아봤다. 일단 파이썬은 시간 초과나고 pypy3는 틀렸다고 나온다. 게다가 아래 for문은 이진탐색한 의미가 없게 순차 탐색을 하고 있다.... ㅋ.T

# 잘못된 방향의 접근
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
data = list(map(int, input().split()))
data.sort()


def binary_search(array, target, start, end):
    if start > end:
        # array[start] ~ array[end] 사이에서 값 찾아야 함
        if array[start] <= array[end]:
            arr = [array[start], array[end]]
        else:
            arr = [array[end], array[start]]
        return arr
    mid = (start + end) // 2
    cutted = sum((i - array[mid]) if (i - array[mid]) >= 0 else 0 for i in array)

    if cutted == target:
        return array[mid]  # int형 return인 경우 바로 값 출력
    elif cutted > target:  # 너무 많이 자른 것. 더 긴 기준으로 다시 잘라보기
        return binary_search(array, target, mid + 1, end)
    else:  # 너무 적게 자른 것. 더 짧은 기준으로 다시 잘라보기
        return binary_search(array, target, start, mid - 1)


result = binary_search(data, m, 0, n - 1)

if type(result) == int:
    answer = result
else:  # 리스트가 돌아온 경우
    answer = 0
    for i in range(result[0], result[1]):
        cutted = sum((j - i) if (j-i) >= 0 else 0 for j in data)
        answer = i
        if cutted == m:
            break
        elif cutted < m:  # 작아지면 더이상 볼 필요가 없음
            answer = i + 1
            break

print(answer)

제대로 푼 풀이. 재귀 함수는 과하게 복잡해지는 경우라서 반복문으로 다들 많이 풀더라. 나도 그렇게 풀었다.

이렇게만 하면 원래 풀었던 방식의 불필요한 방식(그래프 안에서만 값을 찾으려 하고, 못 찾은 경우 범위를 리턴해서 그 범위 안에서 for문을 통해 값을 찾음)이 아예 사라지고 깔끔하게 이진탐색으로 풀 수 있다.

Python3 기준으로 백준 2803 통과했다. 

import sys

input = sys.stdin.readline

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

start = 0
end = max(data)

answer = 0
while start <= end:
    mid = (start + end) // 2

    cutted = sum((i - mid) if (i - mid) >= 0 else 0 for i in data)

    if cutted == m:
        answer = mid
        break
    elif cutted < m:  # 적게 잘라서 더 많이 잘라야 함 (왼쪽 부분 탐색)
        end = mid - 1
    else:  # 너무 많이 자른 것. 더 적게 잘라야 하므로 오른쪽에서 보기
        answer = mid  # 이 경우에는 답이 될 수도 있으니까 저장
        start = mid + 1

print(answer)

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5 
1 2 
2 5 
5 1 
3 4 
4 6

예제 출력 1

2

DFS를 이용한 풀이 (python)

#백준 11724 DFS
import sys
sys.setrecursionlimit(10000)

def dfs(start):
    if(visited[start]):
        return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
cnt = 0

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


for node in range(1, N+1):
    if not visited[node]:
        dfs(node)
        cnt +=1


print(cnt)

BFS를 이용한 풀이 (python)

#백준 11724 BFS
from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
cnt = 0

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


for node in range(1,N+1):
    if not visited[node]:
        bfs(node)
        cnt+=1

print(cnt)

대부분 DFS를 통해 구현하던데, 그 이유는 알겠다. BFS로 구현하는게 더 귀찮더라...ㅎㅎ

DFS(Depth First Search, 깊이 우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수, 즉 그래프의 최대 경로가 정해져 있거나 예측 가능한 경우에 이용한다. 

DFS는 선택한 정점을 저장하기 위한 도구로 큐 대신 스택을 이용한다는 점에서 BFS와 차이를 보인다. 다만 스택을 직접 사용하지 않고, 그 원리를 이용하는 재귀 함수를 통해 구현하는 편이다.

def dfs(start):
	if(visited[start]): 
    	return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
start_node = input('시작 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


dfs(start_node)

다음 코드는 백준 11724번 풀이에서 가져와 약간 변형한 코드이다. 다만 보통 재귀 함수를 사용하는 경우 런타임 에러가 나는 경우가 잦아 다음의 코드를 통해 그 횟수를 직접 지정해주는 경우가 많다. 

import sys
sys.setrecursionlimit(10000)

BFS(Breadth First Search, 너비우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. BFS를 이용하여 최단거리, 최소비용과 같이 최솟값과 관련된 문제를 해결할 수 있는데, 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. DFS는 그래프의 최대 경로(최대 깊이)가 예측할 수 있는 유한한 범위여야만 사용할 수 있지만, BFS는 모든 경로에 대한 동시 탐색이 가능하며 최대 경로를 몰라도 사용할 수 있다. 

from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)

#N:정점개수 M:간선개수
N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
start_node = input('검색을 시작할 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)

bfs(start_node)

백준 11724번 코드 중 일부를 가져와 수정했다. 해당 코드는 정점, 간선의 개수를 입력받고 사용자에게 직접 어떤 정점이 연결되어 있는지 입력받는다.

BFS의 경우 큐를 사용하는 경우가 대부분이다. 방문했던 노드를 체크해야 살펴볼 노드를 큐에 넣을 때 중복이 발생하지 않기 때문이다.

python에서는 큐를 list 타입으로 사용하는 경우가 많은데, 살펴본 노드를 제거할 때, list.pop() 함수를 사용하는 경우 시간 복잡도가 O(N)이라 시간 복잡도 면으로 매우 비효율적이다.

따라서 collections 라이브러리의 deque을 사용하여 시간을 절약하는 편이 좋다. deque는 양 끝에서 접근이 가능하며, append(), extend(), pop(), popleft() 등의 함수를 통해 자료를 넣고 뺄 수 있다. 

동적 계획법(DP)은 어렵거나 큰 문제를 간단하고 작은 여러개의 문제로 나누어 풀고 작은 문제의 답들을 이용하여 원래 문제의 답을 구하는 방식이다.

다음의 특징을 갖고 있다,

1. 최적 부분 구조
: 문제의 정답이 작은 문제에 대해서도 정답이어야 한다. 

2. 부분 문제 반복
: 문제를 여러 개의 작은 문제로 나눌 수 있으며, 나눈 작은 문제들을 전체 문제를 푸는 방법과 같은 방법으로 풀 수 있어야 한다.

DP 문제는 하향식, 상향식 두 가지 방법으로 접근할 수 있다.

하향식 방법의 경우 큰 문제를 풀 수 있는 작은 문제가 될 때까지 나눈 후, 작은 문제들을 풀어 얻은 정답들을 합쳐가며 큰 문제의 답을 구하는 방식으로, 주로 재귀 함수를 이용하여 구현한다.

상향식 방법은 가장 작은 문제부터 시작하여 큰 문제를 풀 수 있을 때까지 차례대로 문제들을 풀어나가는 방식으로 주로 반복문을 이용해 구현한다. 

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력 1

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1

1
2
5

무작정 우선순위 큐를 쓰려고 해서 살짝 헤맸던 문제였다. 우선순위 큐는 값을 넣자마자 알아서 정렬이 되어버려서 문제 내의 '중요도가 맞지 않는 문서의 경우 큐의 맨 뒤로 이동한다'는 조건에 부합하지 않았다. 그렇다고 큐만 써서 문제를 풀자니 가장 우선순위가 높은 문서를 매번 체크해주기 귀찮아서 우선순위 큐, 일반적인 큐 두 가지를 모두 사용하여 문제를 풀었다. 

queue는 입력받은 문서가 원래 몇번째 자리에 있었는지 위치값을 함께 저장해주기 위해 pair<int,int>를 사용하였다. first 값이 value(중요도), second값이 pos(위치)이다.

함수로는 전체 입력을 받는 input()함수, 우선순위를 고려하여 큐에서 pop하고 최종 인쇄 순서를 반환하는 solve() 함수, queue와 prioirty queue를 초기화해주는 clear() 함수 세 개를 정의하였다. 자세한 설명은 코드에 주석으로 달아놓았다. 

* 큐를 초기화해줄때 일반적으로 전체를 순회하며 pop()을 해줘 초기화를 하는 경우가 많은데, 스택 오버플로우에 좀 더 나은 초기화 방법이 있어 clear() 함수는 해당 방법을 사용하였다. 메모리 해제도 해주고 초기화도 해주는 좋은 방법인 것 같다. 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int TC, N, M, cnt;
queue <pair <int, int>> q;
priority_queue <int> pq;
queue <int> ans;

void input() {
	int val = 0;
	for (int i = 0; i < N; i++) {
		cin >> val;
		q.push(make_pair(val, i));
		pq.push(val);
	}
}

int solve() {
	cnt = 0;
	int val, pos = 0;
	while(!pq.empty()) {
		// 맨 앞 원소가 우선순위인 경우
		if (pq.top() == q.front().first) {
			// 뽑을 원소가 M번째 원소인 경우
			if (q.front().second == M) {
				cnt++;
				return cnt;
			}
			// 뽑아줌
			pq.pop(); q.pop();
			cnt++;
		}
		// 맨 앞 원소가 우선순위가 아닌경우
		else {
			val = q.front().first;
			pos = q.front().second;
			q.pop(); q.push(make_pair(val, pos));
		}
	}
	return cnt;
}

// q, pq 초기화
void clearQ(queue<pair<int, int>>& q) {
	queue<pair<int, int>> empty;
	swap(q, empty);
}
void clearPQ(priority_queue<int>& pq) {
	priority_queue<int> empty;
	swap(pq, empty);
}
void clear() {
	clearQ(q);
	clearPQ(pq);
}

int main() {
	cin >> TC;

	for (int i = 0; i < TC; i++) {
		cin >> N >> M;
		input();
		ans.push( solve() );
		clear();
	}

	while (!ans.empty()) {
		cout << ans.front() << endl;
		ans.pop();
	}

	return 0;
}

사실 내 코드가 좋은 코드라고는 말하기 어렵다. 애초에 너무 알고리즘 공부를 안했다ㅠㅠ 기록용으로 남기는 코드이니 참고만 하길 바란다.