전체 글

분류 유니온 파인드, 분리 집합 혼자 힘으로 해결 했는가? O 느낀 점 18116번의 응용 형태이다. 이 문제는 집합의 표현이 다소 까다롭다. 보통은 가능한 집합의 원소를 모두 알려주고 시작하지만, 이 문제는 그 때 그 때 해결을 해야한다. 따라서 집합의 표현을 배열이 아닌 딕셔너리로 표현했다. 그리고 타입 때문에 골치가 아팠다. 이 문제에서 함정인 부분은 바로 a e가 입력으로 들어온 후 e a가 입력으로 들어온 경우이다. 처음은 union 함수에서 이미 같은 함수이면 아무것도 리턴을 하지 않았다가 44%에서 Type Error가 발생했다. 그 이유는 a e를 유니온 후 e a가 입력으로 온 경우 이미 같은 집합이기에 None을 리턴했고 이 때문에 타입 에러가 발생했다. 그냥 이미 친구인 관계에 대해서..

분류 유니온 파인드, 분리 집합 혼자 힘으로 해결 했는가? △ 느낀 점 유니온 파인드 문제인데, 기본적인 유니온 파인드가 아니다. 스스로 유니온 파인드 자체를 변경하는 2가지 경우를 고민 해 보았다. 1. 집합의 크기를 구하기 2. 집합의 원소를 구하기 1번의 경우는 라이님의 블로그를 참고했다. https://blog.naver.com/kks227/220791837179 유니온 파인드(Union-Find) (수정: 2020-08-03) 이번에 소개해드릴 것은 다소 이질적이게 보일 수 있는 자료구조입니다. 그 이름하여 유니온 파인드(union-... blog.naver.com 2번의 경우는 gpt를 통해 구현을 해서 코드를 해석했다. 이 문제는 기본적인 유니온 파인드에서 더 나아가 집합의 갯수를 체크해야 ..

분류 파라매트릭 서치 혼자 힘으로 해결 했는가? 애매하다.. 느낀 점 이런 류의 문제가 생각보다 나는 접근이 힘들다. 문제의 요구사항을 그대로 수행하는 방식으론 절대 해결이 불가능 하다. 일단 입력 값 부터 10억이기 때문에 무조건 log로 만들어야 하고 이는 이분 탐색이 필요함을 알 수 있다. 그러나 어디에 이분 탐색을 써야하는지가 생각하기 힘들다. 우선 이 문제는 약간의 그리디로 접근을 해야하는데 그렇다고 무조건 그리디로 해결하면 안된다. 2가지이면 특정 사람이 1번에서 검사를 받거나 or 2번에서 검사를 받는 형태의 dp로 접근을 하겠지만 (그러나 입력 값이 10억이라 그냥 안됨) 우선 어떻게 해결을 할지부터가 어려웠다. 이 문제는 어렵게 생각하기 보다는 그냥 가장 오래 걸리는 시간까지 1씩 증가 ..