Jinho Tech

이분 탐색 문제이다. 이분 탐색 안쓰고 그냥 반복문 돌려서 풀면 시간 초과가 나온다.

n = int(input())
s, e = 0, int((2**63)**0.5)+1
res = 0
while s <= e:
    m = (s+e)//2
    if m**2 >= n:
        res = m
        e = m-1
    else:
        s = m+1
print(res)

이분 탐색 문제이다. 처음에 s를 1로 했다가 계속 틀렸다.

제일 긴 음악의 길이로 시작하는 게 맞다 -> s = max(li)

def count(li, m):
    t = cnt = 0
    for n in li:
        if t+n > m:
            cnt += 1
            t = n
        else:
            t += n
    return cnt+1

N, M = map(int, input().split())
li = list(map(int, input().split()))
s, e = max(li), sum(li)
res = 0
while s <= e:
    m = (s+e)//2
    if count(li, m) <= M:
        res = m
        e = m-1
    else:
        s = m+1
print(res)

수학 & 이분 탐색 문제이다.

위 그림에서 w1 : c = w : h2, w2 : c = w : h1라는 점을 통해

w1 = c*w / h2, w2 = c*w / h1 

w = w1 + w2 = c*w / h2 + c*w / h1 = c*w*(h1+h2) / (h1*h2) 

-> 1 = c*(h1+h2) / (h1*h2) -> c = h1*h2 / (h1+h2)

h1 = (x**2-w**2)**0.5, h2 = (y**2-w**2)**0.5 임을 알 수 있다.

앞에서 밑줄 친 3개의 공식을 사용해서 이분 탐색을 해주면 된다.

def f(x, y, w):
    h1 = (x**2-w**2)**0.5
    h2 = (y**2-w**2)**0.5    
    c = h1*h2 / (h1+h2)
    return c
    
x, y, c = map(float, input().split())
s, e = 0, min(x, y)
res = 0
while e-s > 0.000001:
    m = (s+e)/2
    if f(x, y, m) >= c:
        res = m
        s = m
    else:
        e = m
print(res)

이분 탐색 & 브루트포스 알고리즘 문제이다. 

이분 탐색을 통해 각 버스별로 기다려야 되는 시간을 구하고,

버스를 탈 수 있는 경우가 없다면(res == []) -1을 출력 

버스를 탈 수 있는 경우가 있다면 제일 짧은 시간을 출력(min(res))해주면 된다.  

N, T = map(int, input().split())
res = []
for _ in range(N):
    t, d, n = map(int, input().split())
    li = [t+d*i for i in range(n)]
    if li[-1] < T:
        continue
    s, e = 0, n-1
    a = 0
    while s <= e:
        m = (s+e)//2
        if li[m] >= T:
            a = m
            e = m-1
        else:
            s = m+1
    res.append(li[a]-T)
print(min(res) if res else -1)

이분 탐색 문제이다.

100을 나중에 곱해주면 오차가 생겨서 틀린다. 먼저 곱해주고 //을 써서 나누도록 하자

x, y = map(int, input().split())
p = y*100//x
s, e = 0, 1000000000
res = 0
while s <= e:
    m = (s+e)//2
    if (y+m)*100//(x+m) > p:
        e = m-1
        res = m
    else:
        s = m+1
print(res if res != 0 else -1)

단순 문자열 문제이다.

while 1:
    s = input()
    if s == '#':
        break
    li = s.split()
    for t in li:
        print(t[::-1], end=' ')
    print()

단순 문자열 문제이다.

for _ in range(int(input())):
    a = input(); b = input()
    cnt = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            cnt += 1
    print(f"Hamming distance is {cnt}.")

단순 문자열 문제이다.

for _ in range(int(input())):
    d = {"TTT": 0, "TTH": 0, "THT": 0, "THH": 0, "HTT": 0, "HTH": 0, "HHT": 0, "HHH": 0}
    s = input()
    for i in range(38):
        d[s[i:i+3]] += 1
    for t, n in d.items():
        print(n, end=' ')
    print()

단순 문자열 문제이다.

for _ in range(int(input())):
    n, s = input().split()
    if s == "kg":
        print("%.4f %s" % (float(n)*2.2046, "lb"))
    elif s == "lb":
        print("%.4f %s" % (float(n)*0.4536, "kg"))
    elif s == "l":
        print("%.4f %s" % (float(n)*0.2642, "g"))
    elif s == "g":
        print("%.4f %s" % (float(n)*3.7854, "l"))

단순 문자열 문제이다.

for _ in range(int(input())):
    i, s = input().split()
    i = int(i); s = list(s)
    s.pop(i-1)
    print("".join(s))

단순 문자열 문제이다.

s = input()
res = ''
for c in s:
    res += c.upper() if c.islower() else c.lower()
print(res)

s = input()
li = [c.upper() if c.islower() else c.lower() for c in s]
print(''.join(li))

문자열 & 브루트포스 알고리즘 문제이다. 파이썬에 있는 count 함수를 쓰면 매우 쉽게 풀 수 있다.

print(input().count(input()))

단순 사칙연산 문제이다.

while 1:
    n = int(input())
    if n == 0:
        break
    res = 0
    for i in range(1, n+1):
        res += (n-i+1)**2
    print(res)

단순 사칙연산 문제이다.

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    s = 0
    for j in range(3):
        t = li[i][j]
        ok = 1
        for k in range(N):
            if k == i:
                continue
            if li[k][j] == t:
                ok = 0; break
        if ok == 1:
            s += t
    print(s)

단순 사칙연산 문제이다.

for _ in range(int(input())):
    s = input().split()
    n = float(s[0])
    for op in s[1:]:
        if op == '@':
            n *= 3
        elif op == '%':
            n += 5
        elif op == '#':
            n -= 7
    print("%.2f" % (n))