IT-garden

문제

강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.

도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.

강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.

예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값과 그 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다.

출력

첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

플로이드 와샬 알고리즘

그래프 이론

정답

import sys

n = int(sys.stdin.readline().strip())
a = []
b = [[1]*n for i in range(n)]
c=0

for i in range(n):
    a.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        for k in range(n):
            if i == j or j == k or i == k:
                continue
            if a[j][k] == a[j][i] + a[i][k]:
                b[j][k] = 0
            elif a[j][k] > a[j][i] + a[i][k]:
                c = -1

if c != -1:
    for i in range(n):
        for j in range(i, n):
            if b[i][j] == 1:
                c += a[i][j]
print(c)

* i : 거쳐가는점

  j : 시작점 

  k : 끝점

j에서 k로 가는 최단경로와 j에서 i를 거쳐 k로 가는 최단경로의 합이 같으면 j에서 k로 가는 경로는 0으로 만들어줍니다.

j에서 k로 가는 최단경로의 값이 더 크면 c를 -1로 해서 출력합니다.

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

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

• 전체를 뒤집으면 1110011이 된다.
• 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

s=input()   
a=0
b=0

if s[0] == '0':
    a=1
else:
    b=1

for i in range(1,len(s)):
    if s[i] != s[i-1]:
        if s[i]== '0':
            a+=1
        else:
            b+=1

if a>=b:
    print(b)
else:
    print(a)

a는 0으로 바뀌는 횟수, b는 1로 바꾸는 횟수를 계산하고 이 중 작은 수를 출력합니다.

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

문제

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. n개의 길이가 같은 DNA가 주어져 있을 때(이 DNA를 a1a2a3a4...이라고 하자) Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 a1의 Hamming Distance + s와 a2의 Hamming Distance + s와 a3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

n,m=map(int,input().split())
a=[]
c=[]
h=0

for i in range(n):
    a.append(input())

for i in range(m):
    b=[0]*4
    d=[]
    for j in range(n):
        if a[j][i] == 'A':
            b[0] += 1
        elif a[j][i] == 'C':
            b[1] += 1
        elif a[j][i] == 'G':
            b[2] += 1
        else:
            b[3] += 1
            
        d.append(a[j][i])
        
    if b[0] == max(b):
        t='A'
    elif b[1] == max(b):
        t='C'
    elif b[2] == max(b):
        t='G'
    else:
        t='T'
    c.append(t)
    h=h+len(d)-d.count(t)

print(''.join(c))
print(h)

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

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

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

a.sort()

b=a[0]-0.5+l
c=1

for i in range(1,n):
    if b < a[i]+0.5:
        b=a[i]-0.5+l 
        c=c+1
        
    i=i+1
    
print(c)

테이프 하나를 사용한다고 생각해서 b를 설정해주고 b에서 리스트 a 위치의 물을 막을 수 있는지 확인합니다.
막을 수 없다면 새로운 테이프 하나를 사용합니다.

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

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

import sys

n=int(input())

a=list(map(int, sys.stdin.readline().split(' ')))
a.sort()

b=1

for i in range(n):
    if b < a[i]:
        break
    
    b+=a[i]
    
print(b)

*만약 올리려는 저울추의 무게가 지금까지 올린 저울추의 총 합 +1 보다 커지는 순간 저울추의 총 합 +1이 측정할 수 없는 최소값이 됩니다.
저울추의 총 합 +1 때문에 b는 1부터 시작합니다.

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

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다.

출력

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

예제 입력과 출력

알고리즘 분류

수학

분할 정복

재귀 호출

정답

n,r,c=map(int, input().split(' '))
num=0

while n>0:
    a=2**n // 2
    if n > 1:
        if a > r and a <= c: 
            num=num+ a**2
            c =c- a
        elif a <= r and a > c: 
            num=num+ (a**2)*2
            r =r- a
        elif a <= r and a <= c: 
            num=num+ (a**2)*3
            c =c- a
            r =r- a
            
    elif n == 1:
        if r == 0 and c == 1:
            num=num+1
        elif r == 1 and c == 0:
            num=num+2
        elif r == 1 and c == 1:
            num=num+3
    n=n-1

print(num)

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