문제

https://www.acmicpc.net/problem/1697

코드

import sys
input=sys.stdin.readline
from collections import deque

Max = 10 ** 5

n,k = map(int,input().split())

visitedCnt = [0]*(Max+1)

def bfs():
    queue = deque()
    queue.append([n,0])

    while queue:
        idx,cnt = queue.popleft()
        if(idx == k):
            print(cnt)
            break

        pos = [idx-1,idx+1,idx*2]

        for i in pos:
            if 0 <= i <= Max and not visitedCnt[i]:
                visitedCnt[i] = visitedCnt[idx] + 1
                queue.append([i,visitedCnt[i]])
bfs()

문제 해결

정점 x가 정점 x-1, x+1, x*2와 연결되어 있는 형태임을 알고 BFS를 적용하였다.

또, 처음에는 방문처리가 필요하지 않다고 생각하였으나 방문처리를 해주지 않으면 중복 탐색에 발생하여 메모리 초과가 발생하여서 방문처리까지 완성하여 코드를 작성했다.

문제

https://www.acmicpc.net/problem/1676

코드

def factorial(n):
    if n>0:
        return n*factorial(n-1)
    else: return 1

import sys
n=int(sys.stdin.readline())
cnt=0
res=factorial(n)
while True:
    if res%10==0:
        cnt+=1
        res//=10
    else: break
print(cnt)

문제 해결

팩토리얼 함수로 주어진 팩토리얼 값을 구한 후 10으로 나눠질 때마다 카운트를 세주면 된다

문제

https://www.acmicpc.net/problem/1655

코드

import sys, heapq
input = sys.stdin.readline

def insertNum(num):
    temp_right = 0
    temp_left = 0
    if len(left_max_heap)==len(right_min_heap):
        heapq.heappush(left_max_heap, [(-1)*num, num])
    else:
        heapq.heappush(right_min_heap, num)

    if right_min_heap:
        if left_max_heap[0][1] > right_min_heap[0]:
            temp_right = heapq.heappop(right_min_heap)
            temp_left = heapq.heappop(left_max_heap)[1]
            heapq.heappush(right_min_heap, temp_left)
            heapq.heappush(left_max_heap, [(-1)*temp_right, temp_right])

N = int(input())
left_max_heap = []
right_min_heap = []

for i in range(N):
    num = int(input())
    insertNum(num)
    print(left_max_heap[0][1])

문제 해결

<문제 로직>

1. leftHeap배열과 rightHeap배열이 있으면 (leftHeap과 rightHeap모두 힙정렬된 배열),

숫자를 차근차근 leftHeap과 rightHeap에 번갈아 가며 채워준다.

2. 이때 중간값은 무조건 leftHeap에서 제일 큰 숫자이다.

3. 만약 rightHeap에서 제일 작은 숫자가 leftHeap보다 작을 경우,

leftHeap의 제일 큰 숫자와 rightHeap의 제일 작은 숫자의 위치를 바꿔 준 후, leftHeap에서 제일 큰 숫자를 출력해준다.

<힙정렬을 사용하는 이유>

다른 숫자들의 정렬은 신경쓸 필요 없이, leftHeap에서는 가장 큰 숫자, rightHeap에서는 가장 작은 숫자만 비교하면 된다.

힙정렬을 사용하면, 가장 큰 숫자와 작은 숫자만 간단하게 비교할 수 있다.

leftHeap의 경우, 최대힙(max heap)을 사용하여 leftHeap[0]에 항상 제일 큰 숫자가 위치하게 하고,

rightHeap의 경우, 최소힙(min heap)을 사용하여 rightHeap[0]에 항상 제일 작은 숫자가 위치하게 한다.

문제

https://www.acmicpc.net/problem/1654

코드

import sys
input=sys.stdin.readline

data=[]
n,k=map(int, input().split())
for i in range(n):
    data.append(int(input()))

start, end=1, max(data)
while start<=end:
    need=0
    mid =(start+end)//2
    for i in range(n):
        need+=data[i]//mid
    if need>=k:
        start=mid+1
    else:
        end=mid-1
print(end)

문제 해결

이분탐색의 기본 문제이다.

start를 1, end를 가장 긴 길이로 설정후 

잘라진 랜선 개수가 n보다 많으면, mid 밑으로는 볼 필요가 없다.

만약 102cm 랜선을 2개로 자른다면, 50cm로 잘라도 2개, 51cm로 잘라도 2개다.

이 문제에서는 최대 랜선 길이를 구해야 하므로, end를 출력시켜야 한다.

문제

https://www.acmicpc.net/problem/1629

import sys
a, b, c= map(int, sys.stdin.readline().split())
#분할정복의 아이디어 
def DaC(a, b):
    if b==1:
        return a%c

    tmp=DaC(a, b//2)

    if b%2==0:
        return tmp*tmp%c
    else:
        return tmp*tmp*a%c

print(DaC(a,b))