인프런 커뮤니티 질문&답변
작성한 질문수
문제풀이 아이디어
해결된 질문
작성
·
76
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요 큰돌님.
강의 들으면서 잘 공부하던 도중에 발견한 문제의 풀이 아이디어가 잘 생각나지 않아 질문드립니다.
(정올이나 백준같은 유명한 사이트가 아니라 링크를 달아드릴 수 없어 테스트 케이스가 부족해요...)
이진트리를 사용하면 풀리는 문제이지만 커리큘럼상 트리 구조에 대해 배우지 않은 부분이라 혹시 다른 방법이 있는지 궁금합니다.
02. [알고리즘 종합 - 2] 상어
문제 설명
상어는 동족을 잡아먹는 동물이다. 상어가 다른 상어를 잡아먹기 위해서는 특정 조건을 만족해야 하는데,
A라는 상어가 B라는 상어보다 크기와 속도 그리고 지능 모두가 높거나 같을 때 A는 B를 잡아먹을 수 있다.
두 상어가 서로 잡아먹을 수 있는 경우도 존재한다. 상어 한 마리당 잡아먹을 수 있는 상어의 개수는 최대 두 마리이다.
그 보다 많이 잡아먹고자 할 경우에는 너무 배가 부르기에 상어는 잡아먹을 수 없다.
상어의 정보가 들어 와서 서로 잡아먹는 살육전이 벌여졌을 때, 남게 되는 최소한의 상어의 개수를 구해보자.
입력
첫 줄에는 상어가 몇 마린지 뜻하는 정수 N(1≤N≤50)이 입력된다.
그 다음 줄부터 한 줄에 상어 하나의 크기, 속도, 지능이 순서대로 입력된다.
크기, 속도, 지능은 1 이상 2,000,000,000 이하이다.
출력
살아남게 되는 상어의 최소 개수를 출력한다.
예시 입력 1
3
1 2 1
4 3 5
3 1 2예시 출력 1
1예시 입력 2
5
1 4 2
2 3 4
3 2 1
4 1 3
100 100 100예시 출력 2
3예시 입력 3
20
7 8 6
5 2 3
7 3 7
3 5 7
8 5 8
2 5 10
8 8 1
7 8 5
5 1 8
2 10 3
4 9 8
8 1 4
3 2 9
10 3 9
1 6 6
5 8 1
1 2 10
3 3 5
9 3 8
4 2 7
예시 출력 3
7
답변 2
0
0
안녕하세요, 인프런 AI 인턴입니다.
lky3548님, 큰돌님의 강의를 들으며 학습 중에 맞닥뜨린 문제 해결에 도움을 드리고자 합니다. 질문해 주신 내용은 상어의 능력치 비교를 통해 잡아먹는 규칙을 따지는 문제로 상어 간의 포식 관계를 분석해 최소한으로 남게 되는 상어의 수를 구하는 문제입니다. 주로 그래프나 트리 문제처럼 보이지만 좀 더 단순한 해결 방법을 기대할 수 있습니다.
문제 이해 및 전략
상어 A가 상어 B를 잡아먹을 수 있으려면 세 가지 조건 모두 A가 B보다 크거나 같아야 하며, 상어 한 마리가 잡아먹을 수 있는 상어의 최대 수는 두 마리입니다. 최종 목표는 남아있는 상어의 수가 최소가 되도록 하는 것입니다.
해결 방법
비교 조건: 상어의 크기, 속도, 지능을 비교해서 얼마나 많이 포식 관계를 만들 수 있는지 알아본 후 문제를 해결합니다. 비교의 대상이 되는 상어나 포식 관계를 만드는 과정은 일종의 “최대 연결 매칭” 문제로 간주할 수 있습니다.
알고리즘 접근: 이 문제는 “선형 배정 문제”(Maximum Bipartite Matching)에 기반한 헝가리안 알고리즘이나 적절한 그리디 알고리즘을 적용할 수 있습니다.
프로그래밍 구현:
- 모든 상어 쌍을 비교하면서 ‘잡아먹을 수 있는 관계’를 잠재적으로 형성합니다.
- 각 상어가 잡아먹을 수 있는 상어의 수를 추적하여 최대 두 마리까지만 잡아먹도록 합니다.
- 결국, 잡아먹히지 않고 남을 수 있는 상어의 수를 찾습니다.
- 모든 상어 쌍을 비교하면서 ‘잡아먹을 수 있는 관계’를 잠재적으로 형성합니다.
추가 자료
위 관련 자료를 참고하여 문제를 해결할 수 있는 방향성을 잡아보세요. 이 문제는 다양한 알고리즘 개념을 배우고 적용하는 데 많은 도움이 될 것입니다.
저는 질문자님의 이해를 돕고자 지식 공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.