코딩 테스트

상호베타적(서로소) 집합이란?상호베타적 집합(또는 서로소 집합: Disjoint Set)이란 교집합이 없는 집합관계를 의미한다. 상호베타적 집합은 다음과 같이 트리 형태로 표현한다.집합 A와 B는 교집합이 존재하지 않으므로 상호베타적 집합이라고 할 수 있다. 상호베타적 집합 표현하기상호베타적 집합은 위에서 봤듯 트리 구조로 표현할 수 있다. 이에 대해 더 자세히 알아보도록 하자. 대표원소상호베타적 집합에서 각각의 집합에는 대표원소라는 것이 존재한다.대표원소는 트리의 루트노드에 해당한다. 상호베타적 집합을 배열로 구현하기트리구조로 표현한 상호베타적 집합은 배열로 구현할 수 있다. 방법은 간단하다.배열에 자신의 부모 노드에 해당하는 원소값을 넣으면 된다.루트노드일 경우에는 자신의 원소값을 넣는다. 그림으로 ..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 풀이 과정문제에는 다음과 같은 조건이 존재한다.그 중에서도임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.이 부분은 이진 탐색 트리를 의미한다. 즉, 이 문제는 x좌표를 값으로 하는 이진 탐색 트리를 만든 뒤, 전위 순회, 후위 순회를 하면 된다. 하지만 여기서 주의해야 할점이 있다.첫번째는, 트리에는 x좌표의 값이 아닌 노드의 번호..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2. 풀이 과정이 문제의 핵심 조건은 양 수가 늑대 수보다 많아야 한다는 것이다. 또한 주의해야할 점이 있는데, 루트 노드에서 왼쪽 오른쪽 중 한 곳을 정해 방문을 해도 그 다음, 그 아래 노드로만 갈 수 있는 것이 아닌 방문해왔던 윗 노드를 거쳐 다른 노드로도 갈 수 있다. 이게 무슨 말이냐면,예를 들어서 0을 방문한 뒤 1을 방문하면 1에서 갈 수 있는 곳이 2,4 뿐만아니라 이전에 방문했던 0을 거쳐 다시 8로도 갈 수 있다.즉, 1에선 2, 4, 8 노드와 인접해있다. 만약 0과 1을 방문한뒤 4..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 풀이 과정일단 문제를 풀기에 앞서 몇가지 주의사항을 생각해봤다.1. center의 수익은 계산하지 않는다.2. 자신의 추천인에게 수익금의 10%를 주고 그 추천인의 추천인에게도 10%를 준다.(없을 때까지)3. 10% 한 값이 소수면 소수부분을 버리고 추천인에게 준다.4. 10%가 1보다 작으면 분배하지 않는다. 그리고 이 문제를 풀기위해 두 가지 해시맵을 생각했다.1. 판매원 - 추천인 해시맵2. 판매원 - 수익 해시맵 일단 해시맵을 사용한 까닭은 조회를 O(1)로 할 수 있기 때문이다. 이 문..