백준/그리디12

• 

  [백준 15903번 / C++ / 그리디] 카드 합체 놀이 우선순위 큐에 대한 자료구조를 알고 있으면 해당 문제는 상당히 쉽게 풀린다. #접근방법 먼저, 그리디하게 접근을 해야한다. 가장 작은수를 만들기 위해선 어떻게 해야할까? 직관적으로 생각해봤을 때도 바로 느낌이 올 것이다. 가장 작은 수부터 차례대로 더해야한다. 하지만 벡터나 배열로 생성하였을 경우 매번 오름차순으로 정렬하는 것은 번거롭다. 그렇기 때문에 우선순위 큐를 활용하자는 것이다. 즉, 카드의 개수만큼 입력받아서 최소힙으로 만들면 되는것이다. 4, 2 , 3 , 1 을 입력값으로 받았다면 1을 top 으로 가진 최소힙으로 구성되어지고 top 위치한 두개의 노드를 pop 해서 더한 결과를 두번 push 해주면 된다. 가장 작은 값이 항상 top 에 위치하는 최소힙 자료구조를 활용하면 이 문제는 쉽게 .. 백준/그리디 2022. 6. 28.

• 

  [백준 1461번 / C++] 도서관 그리디 문제이다 #접근방법 본인은 우선순위 큐를 적절하게 사용을 해서 풀었다. 이것보다 더 나은 코드가 있다고 생각을 하지만 문제를 보자마자 직관적으로 떠올렸던 풀이방법이였기에 풀었던 방식을 설명하려고 한다. 이 문제에서 중요한 점은 마지막에 책을 갖다 놓고 나면 다시 돌아올 필요없다 라는 것이다. 그리디하게 해당 문제를 접근하기 위해서 위의 문장을 읽고 바로 떠올려야한다. " 음.. 그러면 가까이 있는 책들을 먼저 갖다놓고 제일 거리가 먼 책을 마지막에 갖다 놔야겠구나" 왜냐하면 가장 멀리 있는 놈을 마지막에 갖다 놔야 다시 돌아오는 비용이 추가로 들지 않기 때문이다. 먼저 문제에 접근할 때 우선순위 큐 두개를 생성하는데 하나는 음수, 하나는 양수값을 모아놓는다. 그리고 책의 좌표값을 입력할 때 가장 .. 백준/그리디 2022. 4. 6.

• 

  [백준 13904번 / C++] 과제 ​#접근방법 점수의 최댓값을 얻기 위해서는 당연히 과제 점수가 높은 것을 제일 먼저 할당 받아야한다. 그렇기 때문에 처음에 입력받을 때 마감일 d와 점수 w 를 정렬해줘야한다. 우선 제일 중요한 과제 점수가 높은 것부터 내림차순으로 정렬해주었다. 그리고 만약 과제 점수가 같을 경우네는 마감일이 짧은것부터 오름차순으로 정렬했다. (실행해본결과 상관없는 조건이다) 아무튼 과제 점수가 높은 것들부터 해서 cost라는 배열에 집어넣어준다. 예를 들어 , 마감일이 4이고 점수가 50이라면 인덱스 4를 가지고 있는 cost라는 배열에 50을 저장한다. 이후에 마감일 4이고 점수가 40이 들어왔을 경우 마감일 1~3 일을 차례대로 훑어보면서 빈자리에 넣어준다. 만약 빈자리가 없다면, 이전에 더 높은 점수를 가지는 과.. 백준/그리디 2022. 4. 5.

• 

  [백준 12904번 / C++] A와 B 그리디 문제이다. #접근 방법 처음에 문제를 읽어봤을 때 이걸 어떻게 해야하지..? 생각이 들수도 있다. 나도 그랬다. 문자열 S에 언제 A를 추가해야할지, 또는 언제 B를 추가하고 뒤집어야하는지.. 한 3분정도 생각하다가 답이 안나와서 만들어야 할 문자열에서 A와 B를 빼면 되지 않을까? 라는 생각이 들었다. 한번쯤은 직관적으로 문제에 접근해도 좋지만 만약 안풀린다면 추가하는 것이 아니라 반대로 생각해서 빼보는 방식도 고려해봐야할 것이다. 즉, 문자열 S1에서 만들어야 할 문자열이 S2 라면, S2에서 A를 빼주고, 또는 B를 빼주고 문자열을 뒤집는다. 언제동안? S1과 S2의 길이가 같을때까지! 문자열의 길이가 같아졌을 때 같은 문자열이 맞는지 비교해서 출력하면 끝이다. #include #includ.. 백준/그리디 2022. 4. 5.

• 

  [백준 1449번 / C++] 수리공 항승 백준의 그리디로 분류되어 있는 문제를 풀어보았다. #접근방법 해당 문제는 조금만 생각해도 쉽게 풀릴 수 있다고 생각한다. 로직은 다음과 같다. 해당 지점에서 좌우 0.5 간격을 줘야한다는 말이 거창하게 들릴 수 있지만 해석해보면 그냥 물이 새는 지점은 구멍이고 그 구멍을 막기 위해선 한 칸을 막아야한다는 뜻이다. 즉, 길이가 1인 테이프를 그냥 붙이라는 말인데 말을 저렇게 하는거다. 먼저 물이 새는 지점의 데이터를 받아서 오름차순으로 정렬을 한다. 그 후, 시작 지점에서 바로 소유하고 있는 테이프의 길이를 더하고 -1을 해준다면 그 값이 테이프의 마지막 위치다. 예를 들면, 만약 물이 새는 시작 지점이 3이고 소유하고 있는 테이프 길이가 5라면 3 4 5 6 7 이라는 장소를 다 막을 수 있는 것이다. .. 백준/그리디 2022. 4. 5.

• 

  [백준 13458번 / C++] 시험 감독 해당 문제는 브론즈 문제이지만, 두가지의 예외사항이 있기 때문에 포스팅한다. #접근 방법 로직은 단순하다. 총 감독관은 각 시험장에 한명씩 투입돼야 하기 때문에 각 시험장에 수용하는 인원에다가 총 감독관이 감시할 수 있는 인원을 빼주고 시작한다. 그리고 부감독관이 감시할 수 있는 인원을 나누어주면 부감독관의 인원이 나온다. 그리고 나누었을 때 나머지가 1 이상이라면 한 명의 부감독관이 추가돼야한다. 여기서 예외사항이 있다. 총감독관이 모든 시험장에 투입됐는데 총감독관 혼자서 모든 인원을 감시할 수 있다면 부감독관을 고용할 필요가 없다는 뜻이다. 그렇기 때문에 각 시험장에서 수용하는 인원에서 총감독관이 감시할 수 있는 인원을 뺐을 때 해당 인원수가 0 이하로 떨어진다면 부감독관의 투입을 고려하지말자. 두번.. 백준/그리디 2022. 3. 31.

• 

  [백준 12845번 / C++] 모두의 마블 그리디를 활용해서 풀면 되는 문제이다. #접근방법 그리디의 공통은 어떻게 하면 최적의 값을 구할 수 있는지 알아채야한다. 해당 문제 같은경우에는 문제를 잘 이해해서 의도를 파악해야한다. level 값이 만약 , 10 40 50 20 70 20 10 이런식으로 주어진다면, 어떻게 합을 하면 최댓값을 찾을 수 있을까 고민해야한다. 위의 예제에서 가장 큰 레벨의 값은 70이다. 그렇다면 70에다가 주변에 있는 레벨 값을 다 더해서 생성되는 것이 최대이지않을까? 라는 생각을 하는 순간, 바로 풀 수 있다. 즉, 배열에서 가장 큰 레벨을 가진 값과 인덱스 번호를 저장을 한 다음에 그 값을 기준으로 해서 다른 레벨의 값들을 더해서 만들어진 값들이 최댓값이 된다. #include #include #include us.. 백준/그리디 2022. 3. 31.

• 

  [백준 1715번 / C++] 카드 정렬하기 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이 문제를 보고 딱 떠올려야 하는 것은 그리디하게 접근해야 한다는 것이다. 예를 들어보자 . 카드의 수가 "2, 3, 4, 10, 100"의 묶음이 존재한다. 여기서 직관적으로 어떻게 해야 두 묶음을 합친 것이 최솟값이 되는지 보여야한다. 즉, 작은 수 부터 골라서 그 값을 합쳐야 한다. (2+3), 4, 10, 100 -> (4+5), 10, 100 -> (9+10) , 100 -> (19 + 100) priority_queue 를 최소힙으로 생성하여 최상단에 위치한 두개의 데이터 값을 합해서 다시 push 해준다. 자료구조 Priority_Queue는 Queue 의 한 종류인데 말 그대.. 백준/그리디 2022. 3. 2.

• 

  [백준 11000번 / C++] 강의실 배정 자료구조 Priority_Queue는 Queue 의 한 종류인데 말 그대로 우선순위에 따라 정렬된 Queue라고 보면 도니다. 와 동일한 라이브러리에서 지원 해주며 특정 원소를 push 를 할 때 O(logN)만에 이루어진다. 해당 시간 baebalja.tistory.com 그리디 문제이다 방 배정을 하기 위한 최소 값을 구하기 위해서는 각 강의에서의 종료시간과 시작시간이 겹치지 않으면 된다. #접근방법 pair 벡터를 생성하여 시작 시간과 종료 시간을 저장한다. 오름차순으로 정렬한다. priority_queue를 최소힙으로 만들어주고 종료시간을 push한다 (종료시간의 최소값이 top에 위치) for문을 돌면서 priority_queue에 top에 위치한 값보다 같거나 큰 시작시간의 강의가 들어오게되면.. 백준/그리디 2022. 2. 21.

• 

  [백준 1202번 / C++] 보석 도둑 자료구조 Priority_Queue는 Queue 의 한 종류인데 말 그대로 우선순위에 따라 정렬된 Queue라고 보면 도니다. 와 동일한 라이브러리에서 지원 해주며 특정 원소를 push 를 할 때 O(logN)만에 이루어진다. 해당 시간 baebalja.tistory.com 이 문제는 priority_queue 내림차순인 Max heap구조를 사용하면된다. 먼저, 다음과 같은 예시가 주어졌다고 가정하자 테스트 케이스가 다음과 같이 주어졌을 때 오름차순으로 정렬을 한다. 이후, 가방의 크기가 작은 것부터 해서 담을 수 있는 보석을 하나씩 다 담아본다. 즉, 가방이 담을 수 있는 무게의 크기가 2라면 2이하인 보석들이 Queue에 빼곡빼곡 쌓여있다고 생각하면 된다. 그리고 더이상 담을 수 없는 무게의 보석이.. 백준/그리디 2022. 1. 18.