[일반] 브루트포스 쓸지 다른방법 찾을지 어케 앎?

[익명(14.40)]

1. 자구알 계속 배우다 보면 감이 온다

2. 브루트포스로 시간/메모리제한 안뜨면 맞은거다

3. 기타?

[백갤러 1(211.234)]

일단 브루트포스로 풀린다? 넘어감 안된다? 최적화방법을찾음 1. 캐시 2. 중복제거 그래도 안될거같다? 적용할만한 알고리즘이 있을지 생각 없다-> ㅈㅈ

[익명(175.119)]

시간복잡도 계산해보셈 N=100,000일 때, 브루트포스로 O(N^2) 풀면 100,000 * 100,000 = 100억이니 시간초과잖음 그러면 더 빠른 방법 뭐가 있겠음. 이진탐색 O(NlogN) 투포인터 O(N+M) 누적합 O(N) 이런거 생각해보는거임 난 보통 이런식으로 접근함

[아마게(aagzuegq2lmc)]

대부분 시간복잡도가 어떤 알고리즘을 써야하는지 알려줍니다 - dc App

[익명(14.40)]

자바인데 1초에 1억번 잡나요?

[아마게(aagzuegq2lmc)]

모든 언어가 1초 1억번정도로 감안해서 문제를 제출해주십니다 아니면 언어제한을 거니깐ㅇㆍ - dc App

[익명(118.235)]

그럼 100억번이면 이론상 100초 걸리는 건가요? 지금까지 이중포문 걍 써도 시간제한 2초 이런거 아무 문제 없었던거같은데 모죠

[아마게(aagzuegq2lmc)]

잘못된 문제거나 출제자 실수겠죠 100억번인데 TLE 안걸리는거면 문의해야합니당. 기업코테에서 애시당초 답인지 아닌지 안알려줄경우 아예 틀린걸로 생각하시면되용 - dc App

[익명(175.119)]

현실적으로는 매년마다 컴파일 속도가 빨라져서 10억에 1초인가 100억에 1초인가 그렇긴함 근데 알고리즘 문제들은 옛날부터 1억에 1초로 계산한 관습 때문에 계산 자체는 1억 1초에서 안벗어나서 보수적으로 잡는다고 생각하셈

[아마게(aagzuegq2lmc)]

컴파일속도도 로컬환경에서나 빠르지 백준 프로그래머스는 1억 1초가 대중적이에요 - dc App

[익명(175.119)]

컴파일러 업뎃한 것만으로도 속도 빨라짐. 요즘 백준 문제 C++로 10억 = 1초로 잡아도 통과하는 문제 왕왕 있음 근데 자바랑 파이썬은 시간 보너스 2배~3배 기준으로 돌아가는 애들이니 컴파일러 성능 좋아졌다고 10억 = 1초로 계산해서 풀면 통과 못 함

[익명(211.36)]

엥 나도 1초 10억으로봤는데 여튼 보통 시간복잡도걸리는건 n중포문이라 그거만잘계신하면됨 유형만봐도 감오는경우도있고

[백갤러 2(175.214)]

브루트포스로 짠 코드가 시간복잡도가 O(N^2) 이면 대부분 시간초과임

[백갤러 3(211.209)]

브루트포스도 뇌빼고 짜면 시간복잡도 지수 & 팩토리얼 시간복잡도 나옴. 특히 조합순열로 풀려고 하면 그럼. 적어도 다항속도까지 문제를 바꿔놔야 감이잡힘. DP를 쓸지, 다른 신박한 방법으로 풀지(그래프 같은거)

[백갤러 3(211.209)]

다항문제로 바꾸고 나면 이제 DP로 조회 가능하겠구나가 파악은 됨. (점화식 세울 수 있는지여부..)

[백갤러 3(211.209)]

다른사람들은 쉬운지 몰겠는데 나는 애초에 어떻게 최적화해서 풀로 훑을지 함수 정의 및 구현 생각하는거 자체가 조금 걸렸음. 그 이후부터는 점화식 설계만 하면되어서 크게 어렵진 않음.