코딩 테스트

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 풀이 과정N/2마리의 폰켓몬을 선택할 때 최대 몇 종류의 폰켓몬을 선택할 수 있는지를 계산하는 문제이다. 해결하는 과정은 다음과 같다. 1. N마리의 폰켓몬 중 중복을 제거한다.최대 몇 종류인지를 알아야하기 때문에 중복된 폰켓몬은 제거해줘야 한다. nums 배열을 순회하며 해시 셋에 데이터를 넣어 중복을 제거해준다. 2. 중복이 제거된 폰켓몬 목록을 통해 최대 몇종류의 폰켓몬을 선택할 수 있는지 파악한다.폰켓몬은 최대 N/2 마리까지 선택할 수 있고 그 N/2 마리는 최대한 다른 종류의 폰켓몬을..

상호베타적(서로소) 집합이란?상호베타적 집합(또는 서로소 집합: 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..