꾸준하게 거북이처럼

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n이 100 이하라 완전탐색을 해도(O(n^2)) 괜찮다. 하지만 입력 크기가 커지게 되면 어떻게 풀어야할까 어딘가에 개수를 저장해서, 전체 개수인 n개에서 빼면 다른 트리 개수가 나올 것 같다. dp구나! 생각이 들었고, 프로그래머스에서 풀이를 찾아봤다. 자식에서 부모로 올라가면서 개수를 증가시켜나가는 방식이다. 그러면 O(n) 방식으로 풀 수 있다. function solution(n, wires) { const g = Array(n + 1) .fill() .map((e) => Array()); for (..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해가 잘 되지 않았던 문제다. 결론적으로 이 문제는 원소의 개수가 가장 큰 두 집합을 구하는 문제다. cards에서 임의의 숫자를 선택하여 규칙대로 만들어진 1번째로 생긴그룹 2번째로 생긴 그룹의 원소 개수의 곱 중 최대값을 알아내야함. 어떤 수를 먼저 선택해도 규칙대로 하다보면 같은 집합의 형태가 나온다! 나만 그 집합의 순서가 다를 뿐, 그 중 1번 2번 그룹 원소 개수 곱의 최대값을 알아야하니, 제일 원소의 개수가 가장 큰 것 2가지를 구하면된다. import collections def solu..