메모장

문제에서 계산식을 제공해준다.

(현재 퍼즐 소요시간 + 이전 퍼즐 소요시간) * (현재퍼즐 레벨 - 숙련도) + 현재 퍼즐 소요시간 = 해당 숙련도의 퍼즐 소요시간

해당 계산식에서 limit 범위 안에 최소 <숙련도>를 구하는 문제다 .

//(현재 퍼즐 소요시간 + 이전 퍼즐 소요시간) * (현재퍼즐 레벨 - 미지수 숙련도) + 현재 퍼즐 소요시간 = 해당 숙련도의 퍼즐 소요시간 

long long PuzzleSolve(int level, vector<int> diffs, vector<int> times)
{
    long long solveTime = 0;

    for (long long i = 0; i < diffs.size(); i++)
    {
        if (diffs[i] > level)
        {
            solveTime += (times[i] + times[i - 1]) * (diffs[i] - level) + times[i];
        }
        else
        {
            solveTime += times[i];
        }
    }

    return solveTime;
}

우선 해당 계산 수식을 함수로 구현한다.

(long long을 쓴 이유는 limit의 범위 10^15 때문)

첫번째 시도

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

//제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

//(현재 퍼즐 소요시간 + 이전 퍼즐 소요시간) * (현재퍼즐 레벨 - 미지수 숙련도) + 현재 퍼즐 소요시간 = 해당 숙련도의 퍼즐 소요시간 

long long PuzzleSolve(int level, vector<int> diffs, vector<int> times, long long limit)
{
    long long solveTime = 0;

    for (int i = 0; i < diffs.size(); i++)
    {
        if (diffs[i] > level)
        {
            solveTime += (times[i] + times[i - 1]) * (diffs[i] - level) + times[i];
        }
        else
        {
            solveTime += times[i];
        }
    }

    return solveTime;
}

int solution(vector<int> diffs, vector<int> times, long long limit)
{
    int level = 0;
    long long answer;

    do 
    {
        level++;
        answer = PuzzleSolve(level, diffs, times, limit);
    } while (limit < answer);


    return level;
}

그리디 문제인줄 알고 , 최솟값 Level(숙련도)를 구하는것이기에 1부터 ++ 하면서 값을 탐색했다.

그렇다, 이 문제가 그리디로 나왔으면 Lv.2로 나오지 않을것이다.

그럼 탐색하는 연산을 줄여야된다.

두번째 시도

탐색 알고리즘 : 이진(이분) 탐색을 사용하기 

이진 탐색은 start 와 end 를 선언하고 mid 값을 이용하여 원하는 값을 탐색하는 방법이다.

이 그림에서는 탐색하는값 37이라는 구체적인 값이 있지만 , 

해당 문제에서는 최소 숙련도를 구하는 문제이기에 mid가 Level값으로 사용함과 동시에 매개변수가 될것이다.

int solution(vector<int> diffs, vector<int> times, long long limit)
{
    long long start = 1;
    long long end = limit;
    long long level = (end + start) / 2;
    long long answer; // 걸리는 시간

    do 
    {
        answer = PuzzleSolve(level, diffs, times);

        if (answer > limit )
        {
            start = level + 1;           
        }
        else
        {
            end = level - 1;
        }

        level = (end + start) / 2;
    } while (start <= end);


    return level + 1;
}

start = 1 , end = limit ,level = (end + start) / 2 로 초기화를 한다.

answer > limit : 해당 레벨의 소요시간이 limit 보다 큰경우 start의 값을 올린다.

answer <= limit : 해당 레벨의 소요시간이 limit 보다 작은경우 end의 값을 올린다.

이런식으로 start와 end값이 교차될때까지 진행한다.

나온 결과값에 +1을 해준다.

(level이 mid 값인데, 원래 이진 탐색시 mid에 low값을 더해주는것을 마지막에 해준것일뿐)

이진 탐색의 시간 복잡도는 O(logN) 이다. 

카테고리 : 수학 , 정수론 , 유클리드 호제법

#include <iostream>
#include <string>

using namespace std;


void Swap(int& num1, int& num2)
{
	int tmp = num1;
	num1 = num2;
	num2 = tmp;
}

int main(void)
{
	int num1, num2;

	cin >> num1 >> num2;

    int oldnum1 = num1;
    int oldnum2 = num2;
       
    int result = 0;
    int remainder = 1; 
    int gcb = 0;
    while(remainder != 0)
        {
            if(num1 <num2)
            {
                Swap(num1,num2);
            }
            result = num1 / num2;
            remainder = num1 % num2;

            if(remainder == 0)
            {
                gcb = num2;
                break;
            }
            
            num1 = num2;
            num2 = remainder;
        }
    
    cout << gcb <<endl;

        cout << (oldnum1 * oldnum2) / num2;
	return 0;
}

카테고리 : 배열 , 이진검색 , 동적프로그래밍(DP)

알고리즘 : LIS(증가하는 수열 알고리즘)

카테고리 : 배열, DFS , BFS , Matrix

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:

    enum dir { UP = 1, DOWN = -1, LEFT = -1, RIGHT = 1 };

    void FindPixel(vector<vector<int>>& image, int sr, int sc, int pos,int color)
    {
        if((sr < 0 || sr >= image.size()) || (sc < 0 || sc >= image[0].size()))
        {
            return;
        }

        if (image[sr][sc] != pos)
        {
            return;
        }

        image[sr][sc] = color;

        FindPixel(image, sr + UP, sc, pos, color);
        FindPixel(image, sr + DOWN, sc, pos, color);
        FindPixel(image, sr, sc + LEFT, pos, color);
        FindPixel(image, sr, sc + RIGHT, pos, color);
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,int color)
    {
        if (image[sr][sc] == color)
       {
           return image;
       }

        FindPixel(image, sr, sc, image[sr][sc], color);

        return image;
    }
};

문제 풀이 :

모든 작업의 요청 시점 시간 에서부터 작업이 완료되는 시간들의 평균값을 구하는 문제다.

문제는 Heap(힙) 카테고리에 있지만 우선순위 큐를 사용하지 않아도 풀리는 문제다.

첫번째 중요한점 : 평균은 최소의 원소끼리 합했을때 최소의 평균값이 나온다.

즉, 인자값으로 준 vector를 [작업의 소요시간]을 기준으로 오름차순 정렬을 해서 각 평균을 구하면 된다.

두번째 중요한 점 : [ 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다 ]

이 문장을 잘 봐야된다.  작업이 완료된 시점의 시간에 작업이 없으면 남은 작업 중 요청 시점이 제일 빠른것 부터 다시 평균을 구해주면된다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

bool compare(vector<int> a , vector<int> b)
{
     return a[1] < b[1];  
}

int solution(vector<vector<int>> jobs) 
{
    int answer = 0;
    int cur_time =0;
    bool check = false;
    
    vector<vector<int>> results = jobs;

    while(!results.empty())
    {
        check = false;
        sort(results.begin(),results.end(),compare);
        for(int i = 0; i < results.size(); i++)
        {
            if(cur_time >= results[i][0])
            {
                check  = true;
                answer += (cur_time - results[i][0]) + results[i][1];
                cout << cur_time << " "<< results[i][0]<< " "<<results[i][1]<<endl;
                cur_time += results[i][1];
                results.erase(results.begin() + i);
                break;
            }
        }

        if(!check)
        {
            vector<vector<int>> tmp = results;
            sort(tmp.begin(),tmp.end());
            cur_time = tmp[0][0];
            answer += tmp[0][1];
            cout << cur_time << " "<< tmp[0][0]<< " "<<tmp[0][1]<<endl;
            cur_time += tmp[0][1];
            tmp.erase(tmp.begin());
            results = tmp;
        }
    }
    
  cout <<answer;
    
    return answer / jobs.size();
}

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

//알고리즘 헤더에 sort 함수에 비교자 변경해서 풀었음
//비교자에서 해당 수자를 문자열로 바꾸고 문자열 제일 앞 숫자가 같으면
//해당 숫자문자열을 합친뒤 크기를 비교하여 true인경우 정렬을 하는식으로

//비교자의 해당 숫자의 문자열 앞이 다른경우 대소비교하여 true인경우 정렬 

using namespace std;

bool compare(int a, int b)
{
     string str_lhs = to_string(a) ;
     string str_rhs = to_string(b) ;
    
    switch(str_lhs.front() == str_rhs.front() )
    {
        case true:
            if(str_lhs+str_rhs > str_rhs + str_lhs) { return true;}
            break;
        case false:
            if(to_string(a).front() > to_string(b).front())  {return true;} 
            break;
    }
  
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";
        
    sort(numbers.begin(),numbers.end(),compare);
   
    //정렬된 배열 제알 앞이 0인경우 숫자 완성이 안됬기에 0문자열 리턴 
    if(numbers.front() == 0 ) { return "0";}
    
    for(int num : numbers) {  answer += to_string(num);}

    return answer;
}

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;


string solution(string s, string skip, int index) {
    string answer = "";
    
    
    //sort 정렬 : 시간복잡도 N , 우선순위 큐 : 시간복잡도 : log n
    //이기에 우선순위큐를 이용하여 minheap으로 정렬함
    priority_queue<char,vector<char>,greater<char>> pq_skip;
    for(char ch : skip) {  pq_skip.push(ch);}
    
    
    char pivot = 'a'; //알파벳 배열에 넣을 시작 문자
    vector<char> alpabet;
    while(pivot <= 'z') 
    {
        //해당 알파벳이 skip문자열에 있는경우 알파벳 배열에 넣지 않는다.
        if( pq_skip.top() != pivot) { alpabet.push_back(pivot); }
        else { pq_skip.pop(); }
        pivot++;
    }
        
    //문자열 s 길이만큼 순회하며 문자를 변환한다.
    int result;
    for(int i = 0; s.size() >i;i++)
    {
        //문자열 s의 단일문자가 알파벳배열의 어디에 위치하는지 찾는다.
        int alpabet_index = find(alpabet.begin(),alpabet.end(),s[i]) - alpabet.begin();
        
        //찾은 단일문자위치에 인자값index를 더하여 최종 위치를 찾는다.
        result = alpabet_index + index;
        //만약 알파벳 사이즈를 초과한 경우 , 알파벳 사이즈만큼 뺀다.
        while(result> alpabet.size()-1 )
        {
            result -= alpabet.size();
        }
        
        answer += alpabet[result];
    }
    
    
    return answer;
}

#include <string>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

//체육복 빌려주는 조건 : 자기 앞,뒷 1번호 만큼 가능
//체육수업을 들을수있는 학생의 최댓값 return 
//여벌 체육복을 가져온 학생도 도난 가능,체육복을 빌려줄수 없음 하지만 자기것는 있음

bool reserve_check(int index, map<int,int>& students)
{
    //iter = 자신의 앞 또는 뒤 학생의 iter
    map<int,int>::iterator iter_before = students.find(index);
    
    //해당 학생이 없을수도 있기에(제일 앞학생 또는 제일 뒷학생 고려)
    //여벌 체육복이 있으면 해당 학생의 체육복을 -1 시킴
    if(iter_before  != students.end() && iter_before->second == 2)
    {
        iter_before->second--;
        return true;
    }  
    
    return false;
}


int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    map<int,int> students; //학생번호,체육복 수
    
    //여벌 체육복이 있는 학생을 맵에 추가
    for(int num : reserve) {  students.insert({num,2}); }
    
    //체육복을 잃어버린 학생을 맵에 추가
    for(int num : lost)
    {
        //해당 맵에 여벌 체육복을 갖고 있지만 잃어버린 학생이 있을수 있기에 find 실행
         map<int,int>::iterator iter = students.find(num);
        //find결과가 없으면 해당 체육복이 없는 학생으로 추가
        if(iter  == students.end()) {  students.insert({num,0}); }
        //find 결과가 있으면 해당 학생의 체육복 수를 1감소
        else {  iter->second--;}
    }
    
    for(int i=1; i <= n ; i++)
    {
        map<int,int>::iterator iter = students.find(i);
        
        //해당 학생이 map에 없으면 수업을 들을 수 있기에 answer후 순회
        if(iter == students.end()) {  answer++;  continue;}
        
        //해당 학생이 체육복이 없는경우
        if(iter->second == 0)
        {
            //자기 앞,뒷 번호의 여벌 체육복을 체크후 true인경우 해당 학생의 체육복을 1증가
           if(reserve_check(i-1,students) || reserve_check(i+1,students))  iter->second++; 
        }
        
        //해당 학생이 체육복이 1개 이상인경우 answer증가 
        if(iter->second >=1) {  answer++; } 
        
    }

    
    
    return answer;
}