본문 바로가기
반응형

그리디6

프로그래머스 - 구명보트 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42885# 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제 풀이 아이디어는 쉽게 떠올랐다. 주어진 사람들의 무게를 정렬 후 최소 무게 + 최대 무게를 해서 limit이 넘어가면 최대 무게인 사람을 혼자 태우고 해당 인원을 pop한 뒤 다시 그 다음으로 무거운 사람을 최대 무게로 두는 방식으로 반복하려 했다. 그런데 실제로 원소들을 pop하다보니 시간 초과가 나서 인덱스를 .. 2022. 2. 5.
프로그래머스 - 큰 수 만들기 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제 풀이 answer의 크기는 (number의 크기) - k이다. 따라서 첫 번째 for문은 number.size() - k만큼 돈다. 그리고 다음의 과정을 거친다. 1. 0 ~ k에서 가장 큰 수를 찾아 해당 인덱스가 j라면 현재 인덱스(cur)를 j로 바꿔주고 answer에 넣는다. 2. 다시 cur + 1부터 k + i까지 가장 큰 수를 찾는다. 반복. 3번 테스트 케이스로 예를 들어보면, "4177252841"에서 0 ~ k를 탐색하면 최댓값 7이 있는 인덱스는 2이므로 cur=2, answer에는 7을 추가한다. .. 2022. 2. 5.
프로그래머스 - 조이스틱 & BOJ - 고득점 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42860 https://www.acmicpc.net/problem/3663 3663번: 고득점 현수는 조이스틱을 이용해 지렁이를 미로에서 탈출시키는 게임을 하고 있다. 최고 점수를 얻은 경우에는 조이스틱을 이용해서 이름을 입력해야 한다. 이름을 입력하는 과정은 다음과 같다. 가 www.acmicpc.net 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 문제 풀이 "AAA..."에서 .. 2022. 2. 5.
BOJ 1931 회의실 배정 / C++ 문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 코드를 보면서 이해하는 편이 빠르다. 회의의 시작 시간과 끝나는 시간을 pair로 저장하는 vector를 만든다. 최대 배정 가능 회의를 넣는 벡터도 생성해준다. 회의들을 모두 입력받은 뒤, 가장 빨리 끝나는 작업 순으로(즉, pair의 second) 정렬을 해주기 위해 compare 함수를 만든다. 이 때, a.second와 b.second가 같다면 first도 똑같이 비교해줘야 한다. 예를 들어, 6개의 회의가 1 3 3 100 4 5 6 6 5 6 7 7 의 순서로 입력되었다면 정렬.. 2021. 8. 31.
반응형

티스토리툴바