본문 바로가기

그리디 알고리즘6

[프로그래머스 Lv3] : 섬 연결하기 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 최소비용으로 n개의 섬이 모두 연결될 수 있도록 하는 문제. 풀이 다리를 통해서 통행이 가능하다면 두 섬은 연결되어있다고 본다. 문제를 보면 최소스패닝 트리 문제인 것을 알 수 있다. 최소 스패닝 트리를 이용해서 모든 섬이 공통 조상을 가지도록 연결시켜주면 된다. 코드 작성 #include #include #include using namespace std; const int MAX_N = 100 + 5; int Parent[MAX_N]; int F.. 2022. 6. 23.

[프로그래머스 Lv2] : 구명보트 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 무인도에 갇힌 사람들을 모두 구하기 위해 필요한 최소 구명보트 수를 리턴하는 문제. 풀이 보트에는 최대 2명의 사람이 탈 수 있으며, 무게 제한이 있다. 풀이 알고리즘 무게가 가벼운 사람은 최대한 무게가 무거운 사람이랑 같이 타야 최대한 많은 사람들이 짝을 이뤄서 보트에 탈 수 있다. 일단 탈출해야할 사람들을 무게순으로 정렬.. 2022. 6. 23.

[프로그래머스 Lv2] : 조이스틱 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 원하는 이름을 완성하기 위해서 조이스틱을 최소한 몇 번 조작해야하는 지 리턴하는 문제. 풀이 이번 문제가 여태까지 풀어본 2단계 문제중에 제일 어려운 것 같다. 내 방식대로 몇 번을 시도해봤지만 몇 개의 케이스에서 계속 실패해서, 결국 구글 선생님들께 가르침을 받았다. 초기에 이름은 'A' 로만 이루어져있으며 조이스틱을 상하좌우로 .. 2022. 6. 22.

[프로그래머스 Lv1] : 체육복 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42862# 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 체육복을 도난당한 학생들이 최대한 체육복을 빌려서 체육수업을 들을 수 있도록 해주자. 풀이 나의 알고리즘 1. 잃어버린 학생들 중에 여벌옷을 가지고 있는 학생들은 빌려주지 못하고 자기가 입어야 하므로 본인 여벌옷을 입는다. 2. 체육복을 빌려줄 수 있는 학생들 중에 2명을 빌려줄 수 있는 학생이 아닌, 1명만 빌려줄 수 있는 학생들 먼저 도난 당한 학.. 2022. 6. 21.

[BOJ] 1700 : 멀티탭 스케줄링 문제 링크 1700번: 멀티탭 스케줄링 (acmicpc.net) 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 알고리즘 분류가 순수하게 그리디 알고리즘인 문제. 풀이 너무 과하게 생각해서 오래걸렸던 문제. 멀티탭을 최소한으로 뽑으면서 모든 전기용품을 사용할 수 있게 계획하는 문제이다. 처음에 나는 이미 멀티탭에 꽂혀있는 장치 중 앞으로 사용할 횟수가 많은 것은 뽑지 말아야겠다고 생각했다. 앞으로 쓸 일이 많다면 꽂아두는게 이득이라고 판단했기 때문이다. 그래서 이미 꽃혀있는 장치 중 앞으로 쓰일 횟수가 가장 .. 2022. 3. 17.

[BOJ] 10775 : 공항 문제 링크 10775번: 공항 (acmicpc.net) 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리디 알고리즘을 이용해서 푸는 문제 풀이 과정 보통 그리디 알고리즘 문제들을 보면 무엇을 기준으로 우선순위를 정할지 쉽게 정할 수 없는 문제들이 많지만, 이 문제는 명확했다. i번째 비행기는 1 G >> P; memset(section, -1, sizeof(section)); int ans = 0; for (int i = 1; i > num; int idx = 0; if (.. 2022. 3. 16.

이전 1 다음

티스토리툴바