알고리즘/소프티어 (4) 썸네일형 리스트형 [소프티어] 인증평가 4차 슈퍼컴퓨터 클러스터 문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=1204 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 이분탐색 문제다 가능한 정답 범위는 0 ~ 20억이다. (N이 1, a1이 10억, B가 10^18일 때) 0~20억 사이의 어떤 값 M을 정답이라 가정하면 N개의 컴퓨터 모두 성능이 M보다 크거나 같아야한다. N개의 컴퓨터를 모두 확인하면서 M보다 작다면 M에 맞추고, 크다면 무시해도 된다. N개의 컴퓨터에 대해 위 작업을 했더니 B값으로 모든 컴퓨터에 대해 할당 가능했다면 성공, 아니면 실패다. 성공했다는 것은 B값이 넉넉하거나 딱 맞았다는 것이고, 실패했다는 것은 B값이 부족했다는 뜻. * 넉넉하거나 딱 맞았다면 .. [Softeer] [21년 재직자 대회 본선] 거리 합 구하기 / problemid 635 [JAVA] 문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=635&sw_prbl_sbms_sn=39796 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 모든 노드간 연결돼 있고 간선이 N-1개인 그래프는 트리다 모든 노드마다 다른 모든 노드와 거리의 합을 구한다면 N이 최대 2*10^5 이므로 단순하게는 불가능 해보인다 1번 노드를 루트로 하고 노드간 거리의 합을 먼저 구해보자 1번 노드를 루트로 하는 트리 1번에서 3번,5번,6번 노드로 가기 위해서는 빨간 간선을 지나가야 한다. 그러므로 빨간 간선은 2*3인 6을 정답값에 더해주는 간선이다. 마찬가지로 가중치가 5인 간선은 노드 2만을 위해 지나는 .. [Softeer] [21년 재직자 대회 본선] 코딩테스트 세트 / ProblemId 630 [JAVA] 문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=630 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 짝수번 째 있는 난이도를 적절히 홀수번 째 있는 난이도에 할당하면 된다. 그렇게 해서 홀수번 째에 있는 난이도 중에 가장 작은 값을 가장 크게 만드는 방법을 찾아 그 값을 정답으로 한다. 예를들면 아래와 같다 N=3 이며 난이도의 정보는 아래와 같다고 하자(입력예제1-1) (1) 2 2 1 1 3 1) 2번째 값인 2를 왼쪽에 1, 오른쪽에 1씩 할당해준 후 난이도 결과 3 0 2 1 3 2) 4번째 값인 1을 왼쪽에 1 할당해준 후 난이도 결과 3 0 3 0 3 홀수번 째의 값은 3,3,3.. [Softeer] [21년 재직자 대회 본선] 비밀메뉴2 / ProblemId 633 [JAVA] 문제 링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=633 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 재직자 본선 문제 1번 A수열과 B 수열의 가장 긴 '연속된' 공통 부분 수열의 길이를 찾는 문제이다 방법 1. 길이를 1~3000까지 시도해보는 것이다. -> 3000(N) * 3000(M) * 2999 * 3000 / 2 (1~3000까지의 합) -> 1~3000까지 시도해볼 필요가 없다 (1500을 시도했을 때 실패했다면 0~1499중에 정답이 있다) -> 이분탐색으로 3000(N) * 3000(M) * 12이 가능하다. -> 그래도 시간 내에 해결하기 불가능해 보인다. 2. 연속된 .. 이전 1 다음
