Jinho Tech

저번에 푼 적이 있는 문제인데 그때도 해답을 봤는데 이번에도 풀지 못해서 해답을 봤다. 이해를 완전히 못했나 보다.

이분 탐색 문제인데 count 함수가 핵심 부분이다. 나는 저 생각을 못해서 못 풀었다. 내일 다시 풀어봐야겠다. 

def count(li, m):
    cnt = 1
    t = li[0]
    for i in range(1, len(li)):
        if t + m <= li[i]:
            t = li[i]
            cnt += 1
    return cnt
          
          
def binarySearch(li, C):
    s, e = 1, max(li)
    while s <= e:
        m = (s + e) // 2
        if count(li, m) >= C:
            ans = m
            s = m + 1
        else:
            e = m - 1
    return ans
    
    
N, C = map(int, input().split())
li = sorted([int(input()) for _ in range(N)])

print(binarySearch(li, C))

집합을 사용한 방식

합집합을 사용하면 쉽게 풀 수 있다.

a, b = map(int, input().split())
s1, s2 = set(), set()
for _ in range(a):
    s1.add(input())
for _ in range(b):
    s2.add(input())
li = sorted(s1 & s2)

print(len(li))
for s in li:
    print(s)

이분 탐색을 사용한 방식

1) 집합을 사용한 방식과 속도가 비슷하다. input함수를 사용해서 입력을 읽는 게 시간이 오래 걸리는 것 같다.

def binarySearch(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s + e) // 2 
        if li[m] == n:
            return 1
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    return 0
    
    
a, b = map(int, input().split())
result = []
li1 = sorted([input() for _ in range(a)])
li2 = sorted([input() for _ in range(b)])
for s in li2:
    if binarySearch(li1, s):
        result.append(s)

print(len(result))
for c in sorted(result):
    print(c)

2) stdin.readline을 사용해서 해결했다. 이 방법이 훨씬 빠르다.

readline() 뒤에 rstrip을 사용하지 않으면 출력 형식이 잘못되었습니다 라는 결과가 나온다.

뒤의 공백이 출력되면 안 되는 것 같다.

from sys import stdin

a, b = map(int, input().split())
result = []
li1 = sorted([stdin.readline().rstrip() for _ in range(a)])
li2 = sorted([stdin.readline().rstrip() for _ in range(b)])
for s in li2:
    if binarySearch(li1, s):
        result.append(s)

print(len(result))
for c in sorted(result):
    print(c)

10815번 숫자 카드 문제랑 비슷한데. 개수를 새야 한다는 점만 다르다.

이 문제는 이분 탐색 또는 딕셔너리를 사용해서 풀 수 있는데, 딕셔너리를 사용해서 푸는 게 효율적인 것 같다.

이분 탐색 풀이

1) 처음에 아래와 같이 풀어서 제출했었는데 시간 초과가 나왔었다.

많은 양의 값들을 리스트에 append 해서 시간이 오래 걸린 것 같다. 

def binarySearch(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s + e) // 2 
        if li[m] == n:
            return li[s:e+1].count(n)
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    return 0
    

N = int(input())
li1 = sorted(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))
result = []

for n in li2:
    result.append(binarySearch(li1, n))
print(*result)

2) 딕셔너리에 결괏값들을 저장했더니 해결되었다!

binarySearch 함수는 동일하다

N = int(input())
li1 = sorted(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))

d = {}
for n in li1:
    if n not in d:
        d[n] = binarySearch(li1, n)
        
print(' '.join(str(d[m]) if m in d else '0' for m in li2))

딕셔너리 풀이

압도적 성능을 자랑한다. 이분 탐색 풀이는 3000ms나 걸렸는데, 딕셔너리 풀이는 800ms 밖에 시간이 걸리지 않는다.

N = int(input())
li1 = list(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))
d = {}

for n in li1:
    d[n] = d.get(n, 0) + 1
print(' '.join(str(d[m]) if m in d else '0' for m in li2))

이분 탐색은 정렬된 리스트에서 특정한 값의 위치를 찾아내는 알고리즘이다. 

리스트에서 어떤 특정 값(X)을 찾을 때, 리스트의 가운데 값(M)을 기준으로 비교하면서 탐색하는 방식인데

X가 M보다 크다면 리스트의 오른쪽 부분, X가 M보다 작다면 리스트의 왼쪽 부분을 사용 

-> 다시 가운데 값을 정의 -> 앞의 두 과정을 X == M일 때까지 반복하는 식이다.

def binarySearch(li, n):
    # s: 맨 앞 인덱스, e: 맨 뒤 인덱스
    s, e = 0, len(li)-1
    while s <= e:
        # m:가운데 인덱스
        m = (s + e) // 2 
        if li[m] == n: 
            return 1
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    return 0

위 코드는 리스트(li)에 특정 값(n)이 있는지를 확인하는 이분 탐색 함수인데, 아래와 같은 방식으로 돌아간다.

[1,2,3,4,5,6] 리스트에서 5를 찾는 상황인데 

첫 번째 중앙값보다 n이 더 크므로 리스트의 오른쪽 부분을 사용해서 다시 비교한다.

두 번째 중앙값은 5와 같으므로 반복문이 끝이 나는 식이다.

아래는 위의 이미지 같은 이분 탐색 과정을 출력해주는 코드이다.

def binarySearch(li, n):
    s, e = 0, len(li)-1
    i = 1
    while s <= e:
        m = (s + e) // 2 
        print("%d번째 반복" % (i))
        print("s: %d e: %d m: %d" % (s, e, m))
        print("n: %d li[m]: %d\n" % (n, li[m]))
        i += 1
        
        if li[m] == n:
            print("목표 찾음!")
            return 1
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    print("목표 못찾음!")
    return 0


binarySearch([1, 2, 3, 4, 5, 6], 5)

참고로 python에는 bisect라는 이분 탐색 라이브러리가 존재해서 아래와 같은 방식으로 쉽게 사용할 수 있다!

import bisect
mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect.bisect(mylist, 3))

아래는 내가 풀었던 백준 알고리즘에 있는 이분 탐색 관련 문제들이다.

문제를 풀면서 직접 적용해보는 게 나는 이해가 훨씬 빨리 됐던 것 같다. 꼭 문제를 풀어보도록 하자!

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/307

jinho-study.tistory.com/293

jinho-study.tistory.com/295

jinho-study.tistory.com/296

jinho-study.tistory.com/46

jinho-study.tistory.com/297

jinho-study.tistory.com/298?category=911939

jinho-study.tistory.com/308

jinho-study.tistory.com/309

jinho-study.tistory.com/311

jinho-study.tistory.com/338

jinho-study.tistory.com/494

jinho-study.tistory.com/685

jinho-study.tistory.com/686

jinho-study.tistory.com/687

jinho-study.tistory.com/688

jinho-study.tistory.com/689

jinho-study.tistory.com/690

jinho-study.tistory.com/691

jinho-study.tistory.com/692

jinho-study.tistory.com/693

jinho-study.tistory.com/694

jinho-study.tistory.com/717

jinho-study.tistory.com/718

jinho-study.tistory.com/719

jinho-study.tistory.com/720

jinho-study.tistory.com/721

jinho-study.tistory.com/822

jinho-study.tistory.com/850

jinho-study.tistory.com/961

jinho-study.tistory.com/956

jinho-study.tistory.com/1028

간단한 이분 탐색 문제다

def binarySearch(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s + e) // 2 
        if li[m] == n:
            return 1
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    return 0
    
    
N = int(input())
li1 = sorted(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))
result = []

for n in li2:
    result.append(binarySearch(li1, n))
print(*result)

여름방학 때 학교에서 상금 같은 것이 들어왔길래 뭔가 했었는데 알고 보니 상을 받은 것이었다.

 만든 작품은 블로그에도 올라와있는 얼굴 인식 모자이크 프로그램이다.

처음에는 조금 삽질을 했었는데 좋은 경험이었던 것 같다.

현재는 사회복무요원을 하고 있다. 2022년 8월 31일... 소집 해제할 때에는 쓸만한 예비 개발자가 돼있으면 좋겠다.

같이 스터디하시는 분의 코드를 참고했다. 클래스를 사용해서 풀 생각은 하지 못했는데 코드를 보자마자 감명받았다.

_ = map(int, input().split())
g1 = [{'group': 1, 'name': ant} for ant in input()][::-1]
g2 = [{'group': 2, 'name': ant} for ant in input()]
ants = g1 + g2
T = int(input())

for _ in range(T):
    i = 0
    while i < len(ants) - 1:
        if ants[i]['group'] < ants[i + 1]['group']:
            ants[i], ants[i + 1] = ants[i + 1], ants[i]
            i += 1
        i += 1
        
print("".join([ant['name'] for ant in ants]))

각 행과 열마다 X가 안 들어있는 행, 열의 개수를 구하고 그중 큰 값을 출력해주면 된다.

EX) 입력이 ["XXX.", "X...", "....", "...."] 식이라고 하면

X가 안 들어있는 행의 개수: 2

X가 안 들어있는 열의 개수: 1 

-> max(2, 1) = 2 -> 2 출력 

n, m = map(int,input().split())
board = []

for _ in range(n):
    board.append(input())

a, b = 0, 0

for i in range(n):
    if "X" not in board[i]:
        a += 1

for j in range(m):
    if "X" not in [board[i][j] for i in range(n)]:
        b += 1

print(max(a ,b))

간단한 노가다 문제이다. 각 거리마다 리스트를 생성하고 리스트에 중복되는 요소가 있는지 확인. 없다면 놀라운 문자열이고 있다면 놀라운 문자열이 아니다. 

EX) 입력: AABB

1) 거리 0

li = ["AA", "AB", "BB"] -> 중복된 것이 없으므로 통과

2) 거리 1

li = ["AB", "AB"] -> 중복된 것이 있으므로 놀라운 문자열 아님

while 42:
    s = input()
    if s == '*':
        break
        
    state = 1
    for i in range(1, len(s)):
        li = []
        for j in range(len(s)-i):
            li.append(s[j] + s[j+i])
        for k in range(len(li)-1):
            if li[k] in li[k+1:]:
                state = 0
    if state:
        print("{0} is surprising.".format(s))
    else:
        print("{0} is NOT surprising.".format(s))

처음에 첫 번째 반복문에서 s1, s2 순서를 반대로 해서 틀렸었다. 

아무리 봐도 맞는 것 같았는데 틀려서 짜증 났는데 순서를 바꾸니 바로 해결됐다. 

s1, s2 = map(str, input().split())

for i in range(len(s1)):
    if s1[i] in s2:
        col = i
        row = s2.index(s1[i])
        break
    
for i in range(len(s2)):
    if i == row:
        print(s1)
    else:
        print('.'*col + s2[i] + '.'*(len(s1)-col-1))

입력으로 알파벳 하나와 문장이 들어오는데, 문장 안에 주어진 알파벳(소문자, 대문자)이 총 몇 개 들어있는지 구하면 되는 문제다.

lower, upper, count 메서드를 사용해서 쉽게 풀었다.  

while 42:
    t = input()
    if t == '#':
        break
    li = t.split()
    alpha_upper = li[0].upper()
    alpha_lower = li[0].lower()
    s = " ".join(li[1:])
    cnt = s.count(alpha_upper) + s.count(alpha_lower)
    print("{0} {1}".format(alpha_lower, cnt))

수학, 국어 숙제를 다 풀기 위한 최대 일수를 방학 총 일수에서 빼주면 된다.

L = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())

cnt = 0
while (A > 0 or B > 0):
    cnt += 1
    A -= C
    B -= D
    
ans = L - cnt
print(ans)

이런 DP 비슷한 문제들은 아직 어색해서 푸는데 오래 걸렸다.

변을 공유하는 현재 스티커를 고른다면 위 혹은 밑, 양옆의 스티커는 포기해야 하는데,

이전 대각선과 전전 대각선의 값을 현재 값과 각각 더해 비교하여 큰 값을 취하는 방식으로 문제를 풀었다.

for _ in range(int(input())):
    n = int(input())
    
    li = []
    for _ in range(2):
        li.append(list(map(int, input().split())))
    
    li[0][1] += li[1][0]
    li[1][1] += li[0][0]
    
    for j in range(2, n):
        li[0][j] += max(li[1][j - 1], li[1][j - 2])
        li[1][j] += max(li[0][j - 1], li[0][j - 2])
    
    ans = max(li[0][n - 1], li[1][n - 1])
    print(ans)

그 유명한 에라토스테네스의 체 문제이다. 

에라토스네테스의 체를 사용해 소수 리스트를 만들 때 K(입력) 번째 지우는 수를 구해야 하는 문제이다. 

소수 리스트를 생성하는 과정에서 변수(cnt) 하나만 추가해주면 된다.

N, K = map(int, input().split())  
cnt = 0  
nums = [True] * (N+1)  
for i in range(2, N+2):  
    for j in range(i, N+1, i):  
        if nums[j] == True:  
            nums[j] = False  
            cnt = cnt + 1  
            if cnt == K:  
                print(j)  
                break

수열이 등차인지 등비인지는 맨 처음 3개의 숫자들만 보면 알 수 있다. 

두 번째 숫자 - 첫 번째 숫자 = 세 번째 숫자 - 두 번째 숫자 -> 등차수열 

두 번째 숫자 / 첫 번째 숫자 = 세 번째 숫자 / 두 번째 숫자 -> 등비수열

이 점을 이용해서 등차라면 마지막 숫자에 li[1]-li[0] 만큼 더하고,

등비수열이라면 마지막 숫자에 li[1]//li[0] 만큼 곱해주면 된다.  

li = []
for _ in range(int(input())):
    li.append(int(input()))
    
ans = li[-1]
if li[2]-li[1] == li[1]-li[0]:
    ans += (li[1]-li[0])
elif li[2]//li[1] == li[1]//li[0]:
    ans *= (li[1]//li[0])

print(ans)