글 읽기 - 30ms 대 코드가 궁금합니다.

osc0105 1년 전 0

모든 문제를 가장 빠르게 풀고 싶어하는 변태입니다.

쉬운 문제라고 일단 풀고 최단 시간으로 풀어보고 다른 사람 답안을 보고 더 빠른 알고리즘을 찾는데...

아무리 생각해도 30초가 나오는게 생각이 나지 않습니다.

그런데 30초 대 분들이 코드 공개를 안해놓으셔서... 혹시 기억 나시는 분은 답글 부탁드립니다.

구글링해서 일단 대입해보고 더 빠르면 응용해보는데 60ms 이하로 안떨어집니다.

#1 74ms
from itertools import combinations

card_num, target_num = map(int, input().split())
card_list = list(map(int, input().split()))
biggest_sum = 0

for cards in combinations(card_list, 3):
   temp_sum = sum(cards)
   if biggest_sum < temp_sum <= target_num:
       biggest_sum = temp_sum
print(biggest_sum)

#2 60ms
n,_max = map(int,input().split())
data = list(map(int,input().split()))

temp = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if temp<data[i]+data[j]+data[k]<=_max:
                temp=data[i]+data[j]+data[k]

print(temp)

#3 68ms
n,_max = map(int,input().split())
data = list(map(int,input().split()))

temp = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            r=data[i]+data[j]+data[k]
            if temp<r<=_max:
                temp=r

print(temp)

#.... 60ms 가 가장 빨랐다.

vyu 1년 전 3

N 자체가 작다보니 BigO와 별개로 자잘한 연산이 없는(간단한) 코드가 더 적은 시간이 걸리네요

원하시는 코드는 이 분의 코드를 참고하시면 좋을 듯 합니다

# 3중 for문 : bruteforce (브루트포스)

https://www.acmicpc.net/source... : O(N^3)

N이 지금과 같이 얼마 안 되면 문제가 없지만 값이 커질 수록 코드 수행은 무거워질 수 밖에 밖에 없습니다

이하를 참고하시면 장기적으로 도움이 되실 겁니다

# 2중 for문 + binary search (이분 탐색)

https://www.acmicpc.net/source... : O(logN * (N^2))

이분 탐색 문제들 : https://www.acmicpc.net/proble...

# for문 + two-pointer(두 포인터)

https://www.acmicpc.net/source... : O(N^2)

두 포인터 문제들 : https://www.acmicpc.net/proble...

효율적인 알고리즘을 탐색하시는 자세가 훌륭하시기에 제 최대한으로 답변 드립니다 :)

osc0105 1년 전 1

저도 처음에 # 2중 for문 + binary search (이분 탐색)

방법으로 접근을 하다가

가장 가까운값을 찾는 부분에서 결국에 제일 가까운 값을 찾으려면 o(n^3) 과 값이 비슷하다는걸 알고 돌아갔는데.

이분탐색을 사용하면 문제를 해결할 수 있었군요...

가능한 빠른 풀이 접근 뿐만이 아니라 다른 개념의 응용도 사사해주셔서 정말 감사합니다.

그리고 저 뭔가 답안에 항상 보이는 답말고 다른 특이한 답도 정말 좋아해서 다르게 풀려고 노력 많이 하는데 도움이 많이됐습니다.

뭐가 다른사람이랑 알고리즘에 조금 겹치면 뭔가 복붙한거 같아서 기분이 좀 이상하더라고요 ㅎㅎ

그리고 항상 생각하던거는 사실 log 그래프를 실제로 그려보면

n값이 작을때 오히려 o(n)이 빠른 구간이 존재합니다!

저는 그래서 뭔가 데이터 값도 생각하면서 항상 문제에 접근했는데.

뭔가.. 수학적으로 컴퓨터를 생각해도 될까?... n은 거이 무한에 가까운수인데

하는 뭔가 증명되지 않은 느낌이 있었는데. 그부분도 많이 해결이 된것 같습니다!

vyu 1년 전 1

도움이 됐다니 기쁘네요 :)

항상 효율적인 혹은 남다른 알고리즘 접근 방법 탐색에 대해서

당장은 오래 걸릴 수 있지만 꾸준하게 갈고 닦으시면 꼭 좋은 결과 있으실 겁니다

화이팅 !

댓글을 작성하려면 로그인해야 합니다.