[Programmers] C++ 탐욕법(Greedy) - 구명보트

[Programmers] C++ 탐욕법(Greedy) - 구명보트 문제 설명 보트 한 번에 최대 2명이라고 제한되어있어서 난이도가 높지 않은 문제였던 것 같다. 먼저 주어진 `vector people`을 낮은 몸무게부터 오름차순으로 정렬해주었다. 다른 사람들의 풀이를 보니, 투포인터 방식으로 풀면 조금 더 깔끔하지 않았을까 싶은데 나는 조금 복잡하게(?) deque 방식으로 풀었다. 가장 낮은 몸무게, 가장 높은 몸무게 하나씩 좌우로 빼기 위해서 이 자료구조를 사용하기로 선택했다. 가장 낮은 몸무게(min)를 기준으로 삼아서, 만약 max와의 합이 `limit`을 넘지 않는다면 둘을 각각 deque에서 빼고, `answer++` 해주었다. 만약 `limit`을 넘게 된다면, min을 다시 deque에 p..

• format_list_bulleted Algorithm/C,C++
• · 2024. 4. 19.
• textsms

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로 문제 설명 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return 해야하기 때문에 tickets배열을 우선 정렬한다. 정렬한 tickets배열을 DFS로 돌고, tickets를 다 돌았을 경우가 답이 된다. 만약 tickets를 다 돌기도 전에 DFS가 끝나게 되면 백트래킹으로 마지막을 하나씩 가지치기 하면서 답을 구한다. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경..

• format_list_bulleted Algorithm/C,C++
• · 2024. 4. 18.
• textsms

[Programmers] C++ 2024 Kakao Winter Internship - 가장 많이 받은 선물

[Programmers] C++ 2024 Kakao Winter Internship - 가장 많이 받은 선물 문제 설명 선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다. 두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다. 예를 들어 `A`가 `B`에게 선물을 5번 줬고, `B`가 `A`에게 선물을 3번 줬다면 다음 달엔 `A`가 `B`에게 선물을 하나 받습니다. 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수..

• format_list_bulleted Algorithm/C,C++
• · 2024. 3. 13.
• textsms

[Programmers] C++ 그래프 - 가장 먼 노드

[Programmers] C++ 그래프 - 가장 먼 노드 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 ..

• format_list_bulleted Algorithm/C,C++
• · 2024. 2. 5.
• textsms

[Programmers] C++ 완전탐색 - 피로도

[Programmers] C++ 완전탐색 - 피로도 문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있..

• format_list_bulleted 카테고리 없음
• · 2024. 1. 31.
• textsms

[Programmers(프로그래머스)] C++ 정렬 - H-Index

[Programmers(프로그래머스)] C++ 정렬 - H-Index 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 `h`를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 `n`편 중, `h`번 이상 인용된 논문이 `h`편 이상이고 나머지 논문이 `h`번 이하 인용되었다면 `h`의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논..

• format_list_bulleted Algorithm/C,C++
• · 2024. 1. 30.
• textsms