코딩코딩해

알고리즘 분류: 이분 탐색

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

처음 풀이는 이분 탐색으로 풀었습니다. 

첫 번째 풀이😊

import sys
from math import ceil
input = sys.stdin.readline

n, power = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]

left, right, result = 1, 123455876544000001, 123455876544000001
while left <= right:
    hp = mid = (left + right) // 2
    atk = power
    for t, a, h in info:
        if t == 1:
            hp -= (ceil(h / atk) - 1) * a
            if hp < 1:
                break
        else:
            atk += a
            hp += h
            if hp > mid:
                hp = mid
    if hp > 0:
        right = mid - 1
        result = min(result, mid)
    else:
    	left = mid + 1
    
print(result)

하지만 이분 탐색 그대로 푸는 건 시간이 너무 많이 나와서 두 번째 풀이는 이분 탐색을 사용하지 않고 풀었습니다.

두 번째 풀이 - 틀림😭😭😭 (뒤에 정답 코드 나옵니다)

import sys
from math import ceil
input = sys.stdin.readline

n, atk = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]
hp=0
for t, a, h in info:
    if t == 1:
        hp += (ceil(h / atk) - 1) * a
    else:
        atk += a
        hp -= h
        if hp < 0:
            hp = 0

print(hp + 1)

아무리 생각해도 맞는 것 같은데....!!! 도대체 왜 틀렸을까... 고민하다가 백준 질문 게시판을 봤습니다.

그리고 찾은 반례 입니다. 제 코드에서는 49가 나오는데 정답은 61입니다.

8 3 
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
2 3 70
1 3 100

여기를 누르면 백준 반례 게시글로 이동합니다.

정답 코드😍

import sys
from math import ceil
input = sys.stdin.readline

n, atk = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]
hp, max_hp = 0, 0
for t, a, h in info:
    if t == 1:
        hp += (ceil(h / atk) - 1) * a
    else:
        max_hp = max(max_hp, hp)
        atk += a
        hp -= h
        if hp < 0:
            hp = 0

print(max(max_hp, hp) + 1)

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

내 풀이😊

import heapq
import sys
input = sys.stdin.readline

n = int(input())

# 회의 정보를 담을 리스트
array = []
for _ in range(n):
  # 시작 시간, 끝나는 시간, 회의 인원 입력
  array.append(list(map(int, input().split())))

# 끝나는 시간을 기준으로 오름차순 정렬
array.sort(key=lambda x:x[1])

for _ in range(n):

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

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

내 풀이😊

import sys
input = sys.stdin.readline

n = int(input())

# 회의 정보를 담을 리스트
array = []
for _ in range(n):
  # 시작 시간, 끝나는 시간, 회의 인원 입력
  array.append(list(map(int, input().split())))

# 시작 시간 기준 오름차순 정렬
array.sort()

dp = [0] * n
dp[0] = array[0][2]
for i in range(1, n):
  dp[i] = max(dp[i - 1], dp[i - 2] + array[i][2])

print(dp[n - 1])

시간복잡도는 O(NlogN)입니다.

import sys
input = sys.stdin.readline

이 코드가 없어도 결과는 맞았습니다!! 가 나옵니다. 

밑에는 위의 코드를 넣었을 때고, 위에는 넣지 않았을 때입니다.

위의 코드의 유무에 따라 시간 차이가 꽤 나서 시간초과 판정을 받을 때, 위의 코드를 삽입해주는 게 좋습니다!

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

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

내 풀이😊

n = int(input())

# 회의 정보를 담을 리스트
array = []
for _ in range(n):
  # 시작 시간, 끝나는 시간, 회의 인원 입력
  array.append(list(map(int, input().split())))

# 시작 시간 기준 오름차순 정렬
array.sort()

dp = [0] * n
dp[0] = array[0][2]
for i in range(1, n):
  dp[i] = max(dp[i - 1], dp[i - 2] + array[i][2])

print(dp[n - 1])

시간복잡도는 O(NlogN)입니다.

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

트로미노 알고리즘 문제

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

내 코드😉

import sys
input = sys.stdin.readline

k = int(input())
x, y = map(int, input().split())

num = 0
length = pow(2, k)
map = [[0] * length for _ in range(length)]
map[x - 1][y - 1] = -1

def checkHole(x, y, len):
  for i in range(x, x + len):
    for j in range(y, y + len):
      if map[i][j] != 0:
        return False

  return True

def tromino(x, y, len):
  num += 1
  halfLen = len // 2
  if (checkHole(x, y, halfLen)):
    map[x + halfLen - 1][y + halfLen - 1] = num
  if (checkHole(x, y + halfLen, halfLen)):
    map[x + halfLen - 1][y + halfLen] = num
  if (checkHole(x + halfLen, y, halfLen)):
    map[x + halfLen][y + halfLen - 1] = num
  if (checkHole(x + halfLen, y + halfLen, halfLen)):
    map[x + halfLen][y + halfLen] = num
  if halfLen == 2:
    return

  tromino(x, y, halfLen)
  tromino(x, y +  halfLen, halfLen)
  tromino(x + halfLen, y, halfLen)
  tromino(x + halfLen, y + halfLen, halfLen)

tromino(0, 0, length)

for i in range(length):
  for j in range(length):
    print(map[i][j], end=' ')
  print()

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

알고리즘 분류: 그리디 알고리즘

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

내 풀이😊

import sys
input = sys.stdin.readline

# 테스트 케이스 수만큼 반복
for t in range(int(input())):
  n = int(input())

  data = []
  for _ in range(n):
    x, y = map(int, input().split())
    data.append([x,y])

  data.sort()
  count = 0
  min = [data[0][0], data[0][1]]
  for i in range(1, n):
    if data[i][0] > min[0]:
      min[0] = data[i][0]
      if data[i][1] > min[1]:
        min[1] = data[i][1]
        count += 1

  print(n - count)

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

알고리즘 분류: 그리디 알고리즘

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

내 풀이😊

n = int(input())

time = []
for _ in range(n):
    a, b = map(int, input().split())
    # 끝나는 시간, 시작 시간 순으로
    time.append([b,a])

# 끝나는 시간을 기준으로 오름차순 정렬
time.sort()

count, end = 0, 0
for i in time:
    # 직전 회의랑 겹치지 않으면 선택
    if end <= i[1]:
        count += 1
        end = i[0]

print(count)

시간복잡도는 정렬 때문에 O(NlogN)입니다. 부족한 부분은 말해주시면 감사하겠습니다 :)

아래는 백준 문제 풀이 깃허브 주소입니다.

https://github.com/Yiseull/baekjoon

탐욕법(Greedy) - 출제 빈도 낮음

https://programmers.co.kr/learn/courses/30/lessons/42862

내 풀이😊

def solution(n, lost, reserve):
    answer = n - len(lost)

    # 여벌 체육복이 있는 학생이 체육복을 도난당했을 경우
    for i in reserve:
        if i in lost:
            answer += 1
            lost.remove(i)
            reserve.remove(i)

    reserve.sort()
    lost.sort()
    for i in lost:
        for j in reserve:
            if -1 <= i - j <= 1:
                answer += 1
                reserve.remove(j)
                break

    return answer

시간 복잡도는 O(n^2) 나오는 것 같습니다😭

알고리즘 분류: 다익스트라, 그래프 이론

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

첫 번째 풀이는 시간초과 판정 (밑에 해결 방법 있음)

import heapq
INF = int(1e9)

def dijkstra(start):
    q = []
    # 시작 노드까지의 최단 경로를 0으로 설정하고, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    # 큐가 빌 때까지
    while q:
        dist, now = heapq.heappop(q)
        # 이미 처리된 노드 무시
        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서 가는 경로가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


# 정점의 개수 V, 간선의 개수 E 입력
V, E = map(int, input().split())
# 시작 정점 K
k = int(input())

# 최단 거리 테이블 INF로 초기화
distance = [INF] * (V + 1)
# 방향그래프 정보를 담는 리스트
graph = [[] for _ in range(V + 1)]

for _ in range(E):
    # u에서 v로 가는 가중치 w
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

# 다익스트라 수행
dijkstra(k)

# 각 정점으로의 최단 경로값 출력
for i in range(1, V + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

💡해결 방법 - 아래 코드 추가

import sys
input = sys.stdin.readline

내 풀이😊

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    q = []
    # 시작 노드까지의 최단 경로를 0으로 설정하고, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    # 큐가 빌 때까지
    while q:
        dist, now = heapq.heappop(q)
        # 이미 처리된 노드 무시
        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서 가는 경로가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


# 정점의 개수 V, 간선의 개수 E 입력
V, E = map(int, input().split())
# 시작 정점 K
k = int(input())

# 최단 거리 테이블 INF로 초기화
distance = [INF] * (V + 1)
# 방향그래프 정보를 담는 리스트
graph = [[] for _ in range(V + 1)]

for _ in range(E):
    # u에서 v로 가는 가중치 w
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

# 다익스트라 수행
dijkstra(k)

# 각 정점으로의 최단 경로값 출력
for i in range(1, V + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

전에 풀었던 C++코드와 메모리/시간을 비교했을 때, 확실히 파이썬이 훨씬 더 많이 잡아먹긴 하네요ㅜㅜ

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

알고리즘 분류: 다이나믹 프로그래밍

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

내 풀이😊

# 정수 N 입력
n = int(input())

# DP 테이블 초기화
dp = [0] * (n + 1)

# 다이나믹 프로그래밍 - 보텀업
for i in range(2, n + 1):
    # 1 빼기 연산 수행
    dp[i] = dp[i - 1] + 1
    # 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    # 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[n])

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon