코딩테스트 시간복잡도 질문

Question

CS 지식이 없어서 이상한 고민에 빠져있습니다. 물론 안될 거 알지만 코딩 테스트를 보게 되면 시간 복잡도를 고려해야 할 경우가 많은데 .java 파일을 실행할 때 제가 멀티 프로세싱 병렬 처리 추가하면 시간 복잡도를 줄여서 브루트 포스로 풀어도 모두 통과하게 할 수 있나요?

mirheeoj · Accepted Answer

직접 증거는 없지만 경험상 알고리즘의 복잡도를 직접 재는 경우는 잘 못 봤고 시간으로 체크하는 경우가 많아보였는데, 그러면 멀티스레딩이 도움이 될 수도 있습니다. 근데, 양날의 검이죠. 예를 들어 코딩테스트 답안을 체크하는 에이전트가 답안당 늘 1코어만 할당되게 만들어져있다면 오히려 손해가 될 수 있습니다. 사용가능한 코어가 몇개인가 등을 체크하는 로직을 넣어 누울 자리를 보고 다리를 뻗게 만들 수도 있겠는데, 그러다보면 사용 가능한 라이브러리 제한에 해당되지 않을까 싶기도 하고요. 그래도 정 그것밖에 방법이 없다면 시도해볼만한 일이라고 생각합니다. 완전 제출 전에 직접 돌려보고 결과를 얻을 수 있다면 더더욱. 다만 이건 시간복잡도하고는 관계없는 내용입니다. 한 명이 100시간 걸려 할 노동을 백명이 달려들어 한 시간만에 끝낸 것과 같죠. 일하는 방법도, 일 내용도 그대로입니다. 단지 자원을 더 써서 빨리 끝냈을 뿐인 거죠.

청군로 · Answer

보통 코딩 테스트라 하면 제출자의 의도를 파악하고, 적절한 알고리즘을 선택하여 문제를 해결하는 것인데 작성자님이 말씀하신 방법은 코딩 테스트 의도와는 맞지 않는 것 같습니다.

임시저장보관소 · Answer

시간복잡도와 병렬처리는 상관 없긴 합니다대충 병렬처리 == cpu 여러개 사용 (cpu 코어 여러개 사용) == 컴터 여러개로 돌리는 효과(?)인데 보통 한 컴터 당 그 갯수가 제한되있긴 합니다 (8개, 16개, 등)O(n^2) 이라 하고 8개로 병렬한다 하면n 이 100 이면 n^2 1,0000 --> 나누기8: 1250n 이 1000 이면 n^2 100,0000 --> 나누기8: 125000늘어나는 것은 같스빈다

컴맹9988 · Answer

어떤방식으로 풀던지,시간내에만 문제를 풀면 통과됩니다.

코딩테스트 시간복잡도 질문

4개의 답변

기술 목록