IT-garden

문제

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

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

입력

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

출력

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

n,k=map(int,input().split())
ch=[[-1,-1] for i in range(100002)]

def bfs(s):
    de=deque()
    de.append(s)
    ch[s][0]=0

    while de:
        x=de.popleft()
        
        if x == k:
            return ch[k][0]

        for i in (x*2,x+1,x-1):
            if 0 <= i < 100001:
                if ch[i][0] == -1:
                    ch[i][0]=ch[x][0]+1
                    ch[i][1]=x # 이전에 방문했던 곳
                    de.append(i)

print(bfs(n)) # 가장 빠른 시간

li=deque()
li.append(k)

while True: # 어떻게 이동했는지 추적
    if ch[k][1] != -1:
        li.appendleft(ch[k][1])
        k=ch[k][1]
    else:
        break

print(' '.join(map(str,li)))

ch배열을 2차로 잡습니다.
ch[i][0]은 해당 지점에 가는데 걸린 시간이고 ch[i][1]은 이전에 방문했던 지점을 표시합니다.

ch[i][1]을 통해 끝에서부터 추적해서 어떻게 이동했는지 출력합니다.

백준알고리즘 - 1697번 숨바꼭질 - 파이썬(Python)

백준알고리즘 - 13549번 숨바꼭질 3 - 파이썬(Python)

위 두문제의 응용문제입니다.

백준 알고리즘 13913번 : https://www.acmicpc.net/problem/13913

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력과 출력

정답

from itertools import permutations
import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
w=[list(map(int,input().split())) for i in range(n)]
a=[i for i in range(n)]

r=10000000

def _10971(li):
    s=0
    
    for j in range(n-1):
        if w[li[j]][li[j+1]] != 0:
            s += w[li[j]][li[j+1]]
        else:
            return -1

    if w[li[-1]][li[0]] == 0:
        return -1
    else:
        s += w[li[-1]][li[0]]
    return s

for li in permutations(a):
    print(li)
    c= _10971(li)
    if c != -1:
        r=min(r,c)

print(r)

파이썬 시간초과로 PyPy3로 제출했습니다.

순열을 이용해 모든 가능한 경우를 확인합니다.
각 도시를 이동하는 비용을 더하는데 비용이 0인 경우는 이동할 수 없으니까 불가능한 경우라고 생각합니다.
또한 마지막 도시에서 여행을 출발했던 도시로 돌아올 때도 비용이 0이면 불가능한 경우라고 생각합니다.
가능한 경우 중 가장 적은 비용을 출력합니다.

백준 알고리즘 10971번 : www.acmicpc.net/problem/10971

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력과 출력

정답

from itertools import permutations
import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))

p=list(permutations(a,n))
r=0

for i in p:
    s=0
    li=list(i)
    for j in range(1,n):
        s += abs(li[j]-li[j-1])
    r=max(r,s)

print(r)

배열 a의 모든 경우의 수를 생각합니다.
순열을 이용해 각각 배열의 경우에 대한 합을 구하고 최댓값을 출력합니다.

백준 알고리즘 10819번 : https://www.acmicpc.net/problem/10819

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

예제 입력과 출력

알고리즘 분류

BFS
DFS

정답

import sys
sys.setrecursionlimit(100000)
input= lambda : sys.stdin.readline().strip()

k=int(input())

def dfs(vert,group):
    ch[vert]=group
    for i in li[vert]:
        if ch[i] == 0:
            if dfs(i,-group) is False:
                return False
        elif ch[i] == ch[vert]:
            return False
    return True

while k:
    k -= 1
    v,e=map(int,input().split())
    li=[[] for i in range(v+1)]
    ch=[0]*(v+1)

    for i in range(e):
        a,b=map(int,input().split())
        li[a].append(b)
        li[b].append(a)

    ans=True
    for i in range(1,v+1):
        if ch[i] == 0:
            if dfs(i,1) is False:
                ans=False
                break

    print('YES' if ans else 'NO')

dfs를 이용한 문제입니다.
방문하지 않은 점부터 방문합니다. 이때 점을 2개의 그룹으로 나눕니다.(그룹은 -1,1로 구분)

만약 다음 점이 이미 방문한 점이면 현재 점의 그룹과 같은지 비교합니다.
같은 그룹이면 Fasle를 리턴하고 NO를 출력하고 그렇지 않으면 계속 점을 방문합니다.
False가 나오지 않고 dfs가 끝나면 Yes를 출력합니다.

백준 알고리즘 1707번 : https://www.acmicpc.net/problem/1707

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력과 출력

정답

import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]

m=-100000000

if n > 1:
    for i in range(1,n):
        dp[i][0]=max(dp[i-1][0]+a[i], a[i])
        dp[i][1]=max(dp[i-1][0], dp[i-1][1]+a[i])
        m=max(m,dp[i][0],dp[i][1])
    print(m)
else:
    print(dp[0][0])

dp[i][0] : 수열에서 수를 제거하지 않은 경우
dp[i][1] : 수열에서 수를 제거한 경우

n = 1인 경우는 dp[0][0]을 출력하고
n > 1인 경우에 수열에서 수를 제거하는 경우와 제거하지 않는 경우를 생각합니다.

백준알고리즘 - 1912번 연속합 - 파이썬(Python)

위의 응용문제입니다.

백준 알고리즘 13398번 : https://www.acmicpc.net/problem/13398

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
dp=[1]*n

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1

ind=dp.index(max(dp))
c=dp[ind]
de=deque()

for i in range(ind-1,-1,-1):
    if c == dp[i]+1:
        c = dp[i]
        de.appendleft(a[i])

de.append(a[ind])

print(max(dp))
print(' '.join(map(str,de)))

가장 긴 증가하는 부분 수열의 길이를 구해 해당 길이의 위치를 구합니다.
위치를 인덱스를 통해 찾고 그 위치부터 dp 배열을 검사해 가장 긴 증가하는 부분 수열을 구합니다.

백준알고리즘 - 11053번 가장 긴 증가하는 부분 수열 - 파이썬(Python)

위의 응용문제입니다.

백준 알고리즘 14002번 : www.acmicpc.net/problem/14002