수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력

5 17

예제 출력

4

풀이

bfs로 n에서 k까지 가는 경우의 수를 탐색한다. 처음에는 IndexError가 생겼는데, visited 배열의 수를 넘어가는 수를 감지하려고 해서였다. 그래서 앞에 수의 범위가 0~100000을 넘어가는 경우를 조건문에 추가했다.

코드

from collections import deque
n, k=map(int, input().split())
visited=[0]*100001
q=deque([(n,0)])
while q:
  num, cnt=q.popleft()
  if num==k:
    break
  if num<=100000 and num>=0 and not visited[num]:
    visited[num]=1
    q.append((num+1,cnt+1))
    q.append((num-1,cnt+1))
    q.append((num*2,cnt+1))
print(cnt)

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력

2 162

예제 출력

5

풀이 1

첫번째로 생각했던 풀이는 m에서부터 n을 역추적하는 방식이다. 끝이 1로 끝나면 앞의 값을 m에 넣고, 2로 나누어 떨어지면 2로 나눈 값을 m에 넣었다.

코드 1

n,m=map(int, input().split())
count=0
while True:
  if m==n:
    break
  elif m%10==1:
    m=m//10
  elif m%2==0 and m!=0:
    m=m//2
  else:
    count=-2
    break
  count+=1
print(count+1)

풀이 2

사실 이 문제를 푼 목적이 bfs를 연습하기 위함이라, bfs를 사용해서 또 풀었다.

코드 2

from collections import deque

n,m=map(int, input().split())
s=n
queue=deque([(1,n)]) # 1,n 튜플을 deque로 변환
while queue:
  count, x=queue.popleft()
  if x==m:
    print(count)
    break
  if x*2<=m:
    queue.append((count+1,x*2))
  if x*10+1<=m:
    queue.append((count+1, x*10+1))
else:
  print(-1)

기억할 것

파이썬에서는 while-else, for-else문을 통해 반복문이 조건에 의해 정상종료(break, continue 사용 X) 되었음을 판별할 수 있다. 반복문이 정상종료했을 경우에는 아래의 else문이 실행된다.

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력

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

예제 출력

3 1 2 5 4 3 1 4 2 5

풀이

전형적인 그래프 탐색 문제이다. dfs는 재귀를 통해 구현하고, bfs는 큐를 사용해서 구현했으며, 노드는 인접 리스트를 이용해 표현했다.

코드

import sys
input=sys.stdin.readline

def DFS(v):
  visited[v]=1
  dfs.append(v)
  for i in node[v]:
    if not visited[i]:
      DFS(i)

def BFS(v):
  visited[v]=1
  bfs.append(v)
  queue=[v]

  while queue:
    for i in node[queue.pop(0)]:
      if not visited[i]:
        visited[i]=1
        bfs.append(i)
        queue.append(i)

n,m,v=map(int, input().strip().split())
node=[[] for i in range(n+1)]
visited=[0]*(n+1)
dfs=[]
bfs=[]
for i in range(m):
  a,b=map(int, input().split())
  node[a].append(b)
  node[b].append(a)

for i in range(n+1):
  node[i].sort()

DFS(v)
for i in range(n+1):
  visited[i]=0
BFS(v)

for i in dfs:
  print(i, end=' ')
print()
for i in bfs:
  print(i, end=' ')

참고

https://velog.io/@tks7205/dfs%EC%99%80-bfs%EB%A5%BC-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95-in-python 여러 가지 구현 방법이 모두 설명되어 있어 참고했다.

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력

12

예제 출력

2731

풀이

2xn 타일링 1과 다른 점은 2x2 타일이 추가되었다는 점이다. 아래 그림과 같이 n-1개가 채워진 경우에는 1x2 사각형만, n-2개가 채워진 경우에는 2x1 사각형 2개로 채우거나 2x2 사각형으로 채울 수 있다. 그래서 점화식은 a(n)=a(n-1)+2a(n-2)이다.

코드

import sys
input=sys.stdin.readline

dp=[0]*1000
dp[0]=1
dp[1]=3
n=int(input())
for i in range(2,n):
  dp[i]=(2*dp[i-2]+dp[i-1])%10007
print(dp[n-1])

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

예제 입력

2 AAA AAA

예제 출력

1998

풀이

그리디를 생각하면 아주 쉽다. 그냥 제일 숫자합이 큰걸 9로 두면 된다. 이 문제는 오히려 구현에서 어려움을 겪었다. dictionary를 쓰면 될 것이라 생각은 했는데 평소에 많이 써보지 않아 어색했다.

코드

n=int(input())
a=dict()
for i in range(n):
    tmp=input()
    for j in range(len(tmp)):
        if tmp[j] in a:
            a[tmp[j]]+=10**(len(tmp)-j-1)
        else:
            a[tmp[j]]=10**(len(tmp)-j-1)
a=sorted(a.items(), key=lambda item:item[1], reverse=True)    # Value를 기준으로 정렬
p=9
sum=0
for i in a:
    sum+=p*i[1]
    p-=1
print(sum)

기억할 것

a=sorted(a.items(), key=lambda item:item[1], reverse=True)

이렇게 하면 Key 대신 Value로 정렬을 할 수 있다. lambda를 쓴 부분은 item이라는 값이 있으면 item[1]을 반환한다는 그런 뜻이 되겠다.

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 입력

18

예제 출력

4

풀이

문제에서 최소 개수를 구하라고 했으므로, 최대한 3kg 봉지의 수를 줄여야 한다. 따라서 문제의 경우를 이렇게 나눌 수 있다.

1. 5kg으로 나누어떨어지는 경우(15=5+5+5)
2. 5kg과 3kg 모두 사용하는 경우(18=5+5+5+3)
3. 3kg만 사용하는 경우(9=3+3+3)
4. 나누어 떨어지지 않는 경우(4=3+?) 1은 따로 if문으로 처리해주고, 2와 3의 경우만 반복문으로 돌려보면 된다.

코드

n=int(input())
count=0
if n%5==0:
    print(n//5)
else:
    while n>0:
        n-=3
        count+=1
        if n%5==0:
            print(n//5+count)
            break
        elif n==0:
            print(count)
        elif n==1 or n==2:
            print(-1)

풀고 나서...

풀고 나서 문제 분류를 봤더니 DP가 있었다. DP 풀이는 추후에 다시 풀어봐야겠다.

알고리즘 공부를 하면서 제가 보기 위해 정리한 글입니다. 본 글은 아래 링크를 참조하여 작성되었습니다. [알고리즘] 탐욕 알고리즘(Greedy Algorithm)

그리디 알고리즘이란?

그리디, 즉 Greedy는 탐욕을 의미한다. 그리디 알고리즘은 말 그대로 순간마다 최선의 선택을 함으로써 해답에 도달하는 방식이다. 순간마다 하는 선택은 각 상황에 최선임이 보장되지만 최종 답이 최선이라는 보장은 없다. 하지만 그리디로 풀 수 있는 문제들은 이 최종 답 또한 최선이 되는 문제들이다.

그리디 알고리즘의 조건

01 탐욕적 선택 속성(Greedy Choice Property) 앞의 선택이 이후의 선택에 영향을 주지 않는다.

02 최적 부분 구조(Optimal Substructure) 문제에 대한 최종 해결 방법은 부분적인 문제들에 대한 최적의 문제 해결 방법으로 구성된다.

다만 이러한 조건을 만족하지 않아도 그리디 알고리즘을 근사 알고리즘으로 충분히 활용할 수 있는 경우가 있다. 또한 위 조건을 갖춘 구조를 매트로이드라 하는데, 이 구조를 가진 문제에 대해서는 그리디 알고리즘이 언제나 최적해를 찾아낼 수 있다.

예제. 보물(백준 1026번)

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

예제 입력

5 1 1 1 6 0 2 7 8 3 1

예제 출력

18

풀이

s를 최소로 하려면 가장 작은 수와 가장 큰 수를 곱해서 더해야 한다. 따라서 A 배열을 오름차순으로, B 배열을 내림차순으로 정렬(물론 반대로 해도 된다)해서 각 원소를 곱해서 더해주면 된다. 문제에서 B는 재배열할 수 없다고 했지만, 저렇게 해도 항상 두 원소가 대응될 수 있으므로 상관 없다.

코드

n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
a=sorted(a)
b=sorted(b, reverse=True)
s=0
for i in range(n):
   s+=a[i]*b[i]
print(s)

마치며...

방학 중 알고리즘 공부를 하겠다던 야심찬 계획은 어디 갔는지 모르겠다. 그래도 정리하면서 문제 풀면 좀 더 오래 가지 않을까 싶어 벨로그를 시작하게 되었다. 질문은 (저도 잘 모르지만) 아래 남겨주시면 최대한 답변 드리겠습니다. 모두 파이팅 :P