IT-garden

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

문자열 처리

탐색

정답

a=input()
b=input()
c=0
i=0

while True:
    if i > len(a):
        break
    
    if a[i:i+len(b)] == b:
        i=i+len(b)
        c=c+1
    else:
        i=i+1
    
print(c)

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

문제

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

문제

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

예제 입력과 출력

알고리즘 분류

수학

탐색

정답

a=list(map(int, input().split(' ')))
b=min(a)

while True:
    c=0
    for i in range(len(a)):
        if b % a[i] == 0:
            c=c+1
            
    if c >= 3:
        print(b)
        break
    
    b=b+1

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