코딩생존기

코딩테스트 공부를 하다가 난이도가 올라갈 수록 알고리즘을 분석하고 여러유형에 대해 이론적으로 이해하고 있는 부분이 부족하다고 생각이 들어 알고리즘과 여러 유형에 대해 익혀보는  시간을 가져보려고 한다. 

1. 구간 합

구한 합의 핵심이론은 a~b 구간 사이의 합을 구하는 것이다. 이 때, 배열을 두고 직접 합을 구할 때, 최악의 경우 i가 0이고 j가 N인 경우 시간복잡도가 O(N)이 나와서 연산 수가 많아지면 시간초과가 뜰 수 있다. 구간 합의 경우 연산 수 가 많아지는 경우가 많기 때문에 배열 합을 쓰는게 좋다. 

*합 배열 

합 배열은 기존의 배열에서 구간마다의 합을 만들어두는 것으로 이 배열을 만들어 두고 이를 활용하여 정답을 구한다면  

연산수가 O(1)로 줄어들게 된다. 

-1차원에서의 합 배열

1차원 배열에서 합 배열을 만들 때 S가 합배열이고 B가 배열이라고 했을 때, S[i]=S[i-1] + B[i] 이다. 

그리고 만약 i~j까지의 구간 합을 구한다면 S[j] -S[i] 로 정답을 구할 수 있다.

-2차원에서의 합 배열

2차원 배열에서 합 배열을 만들 때는 경우의 수를 2가지 생각해주어야 한다

일단 1행일때 열이 변하는경우, 1열일때, 행이 변하는 경우를 생각해보자면 1차원에서의 합 배열을 구하는 공식과 똑같은데 

1행 일때 -> S[i][j] = S[1][j-1]+B[i][j] 

1열 일때 -> S[i][j] = S[i-1][i]+ B[i][j]

-> 전까지의 합 + 현재위치의 값

나머지 행과 열 일때

S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+B[i][j] 

-> i-1 값(이전 값의 행)에서 열 방향에서의 합 + j-1(이전 값의 열)값에서 행 방향  + 중복되게 더해진 값 - 현재 위치의 값

그리고 X1,Y1 ~ X2,Y2 까지의 구간 합을 구한다면

S[X2][Y2]-S[X1-1][Y2]-S[X2][Y1-1]+S[X1][Y1]

->X2,Y2까지의 구간합 - X1-1 값에서의 열 방향에서의 합 - Y1-1 값에서의 행 방향에서의 합 + 중복되게 빼진 값

예시 문제

나머지 합 구하기

이 문제에서 보면 N의 최대값이 10^6으로 최악의 경우 1초안에 연산하기는 힘들기 때문에 합 배열을 사용해야한다. 

※핵심 아이디어

1. (A+B) % C = ((A%C)+(B%C))%C -> 특정 구간 수를 나머지 연산해서 더한 값을 나머지 연산하는 것이나 구간합을 나머지 연산한 값이나 같다. 

2. if S[j]%M == S[i]%M 이라면 (S[j]-S[i])%M==0이다. 

흐름을 살펴보자면 

1. 합 배열을 만든다.

2. %M의 값으로 배열을 업데이트 해준다.

3. 경우의 수를 세어준다. (0일때는 0인 개수만큼 경우의 수를 추가, 2보다 클때에는 조합을 통해 경우의 수를 추가)

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	vector<long> S(N, 0);
	vector<long> C(N, 0);
	long answer = 0;
	cin >> S[0];

	for (int i = 1; i < N; i++) {
		int tmp = 0;
		cin >> tmp;
		S[i] = S[i - 1] + tmp;
	}
	for (int i = 0; i < N; i++) {
		int r = S[i] % M;
		if (r == 0) {
			answer++;
		}
		C[r]++;
	}
	for (int i = 0; i < M; i++) {
		if (C[i] > 1) {
			answer += (C[i] * (C[i] - 1) / 2);
		}
	}

	cout << answer << "\n";
}

무게에 따른 사람의 수를 모두 저장해준다음 그 벡터를 순회하면서

같은 무게가 있으면 어디에 앉든 균형을 이루기 때문에 조합으로 수를 구해주고

2 3 4 m 자리가 있어서 나올 수 있는 비율은 2:3 2:4=1:2 3:4 가 있기 때문에

이 에 맞는 값이 있다면 경우의 수 를 추가해주면 된다.

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    vector<long long> cnt(1001, 0);      //몸무게 별 사람수
    for (int i = 0; i < weights.size(); i++) {
        cnt[weights[i]]++;
    }
    //나올수 있는 비율 2:3 2:4=1:2 3:4
    for (int i = 0; i < weights.size(); i++) {
        if (weights[i] % 2 == 0) {                //2:3
            long long base = (weights[i] / 2) * 3;
            if (base <= 1000) answer += cnt[base];
        }
        if (weights[i] % 3 == 0) {                //3:4
            long long base = (weights[i] / 3) * 4;
            if (base <= 1000) answer += cnt[base];
        }
        long long base = weights[i] * 2;
        if (base <= 1000) answer += cnt[base];
    }

    for (int i = 100; i <= 1000; i++) {
        if (cnt[i] >= 2)
            answer += (long long)(cnt[i] * (cnt[i] - 1)) / 2;           //같을 때
    }

    return answer;
}

ext의 값이 val_ext보다 낮은 것을 저장하고 sort_by값에 따라 오름차순 정렬하는 문제이다. 처음에는 switch 문을 통해 idx1, idx2를 정해서 저장 및 정렬을 하려고 했는데 switch 문에는 문자열을 그냥 쓸 수 가 없는 것 같아서 map 자료형을 통해 idx 값을 정해서 저장 및 분류를  해주었다. 또한 compare 함수로 기준 값에 따라 오름차순 정렬되도록 만들었다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
map<string,int> m1={{"code",0},{"date",1},{"maximum",2},{"remain",3}};
int idx;
bool compare(const vector<int> &data1,const vector<int> &data2){
    return data1[idx]<data2[idx];
}
vector<vector<int>> solution(vector<vector<int>> data, string ext, int val_ext, string sort_by) {
    vector<vector<int>> answer;
    idx=m1[sort_by];
    for(auto d: data){
        if(d[m1[ext]]<=val_ext){
            answer.push_back(d);
        }
    }
    sort(answer.begin(),answer.end(),compare);
    return answer;
}

1. 입력액션 지정

특정 키를 눌렀을 때, 해당 행동을 하게 하기 위해서는 일단 키를 눌렀을 때 작동하게 할 캐릭터의 Input/Actions 폴더에 들어가서 우클릭 후 입력 / 입력액션을 클릭하고 원하는 이름으로 지정해주면 된다.

만든 후 기본 설정으로 두면 된다. 

2. 매핑 컨텍스트에 키 추가

Input 폴더의 입력 매핑 컨텍스트를 더블클릭하여 들어간 뒤 +키를 눌러 매핑을 추가해주고 키 값은 키보드 버튼을 누른뒤 원하는 키를 입력하면 된다.

3. 움크리기 애니메이션 추가

애니메이션에 움크리는 애니메이션을 추가해서 동작할 수 있도록한다.

4. 동작 블루 프린터 추가

키를 추가해주었다면 키를 통해 작동할 캐릭터의 블루프린터로 들어 간 후, 이벤트 그래프에서 커스텀 이벤트를 추가해서 동작하도록 만들어 주면 된다. 

5. 함수 내부 동작

함수는  커스텀이벤트를 추가해서 구현해두었는데 이 때 전에 추가해둔 IA_Crouch 를 불러온다음 키가 눌릴떄, 즉 Started에서 만약 달리는 중과 움크리는 중이 아니라면 움크린 불린값을 True로 만들어준다. 이때, 애니메이션 그래프에서 Crouched Locomotion으로 애니메이션이 넘어가지게 된다. 그 이후 걷는 속도를 낮춰주고 카메라의 거리를 조금 멀리로 바꿔주는데 이때, 400 -> 500의 값을 Lerp하게 즉, 스무스하게 넘어가도록 해준다.

의사코드가 잘나와있는 문제라 그대로 구현만 해주면 쉽게 풀리는 문제이다. 중요한 건 위 아래 왼쪽 오른쪽을 탐색하고 그 탐색한 값이 표의 크기 안에서 존재하는 지 확인해주면 된다.

#include <string>
#include <vector>

using namespace std;

int dh[4]= {0,1,-1,0};
int dw[4]= {1,0,0,-1};
int solution(vector<vector<string>> board, int h, int w) {
    int answer = 0;
    int size=board.size();
    int wsize=board[1].size();
    for(int i=0;i<4;i++){
        int h_check=h+dh[i];
        int w_check=w+dw[i];
        if(h_check>=0&&h_check<size&&w_check>=0&&w_check<wsize){
            if(board[h][w]==board[h_check][w_check]){
                answer++;
            }
        }
    }
    return answer;
}

참가자 이름과 완주자이름을 비교하여 완주하지못한 사람을 찾으면 된다. 

나는 map 자료형을 사용해서 참여자 벡터를 순회하면서 해당 이름의 값을 증가시켜주고 그 뒤에 완주자 벡터를 순회하면서 해당 이름의 값을 줄여준다. 이때 해당 이름의 값이 1보다 크거나 같을 경우 통과하지 못하였다는 것이므로 answer에 추가해준다. 

동명이인이 있을 수 도 있어서 answer에 넣은 뒤 해당 이름의 값을 줄여준다. 

#include <string>
#include <vector>
#include <map>
using namespace std;
map<string,int> m1;
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    for(int i=0;i<participant.size();i++){
        m1[participant[i]]++;
    }
    for(int i=0;i<completion.size();i++){
        m1[completion[i]]--;
    }
    for(int i=0;i<participant.size();i++){
        if(m1[participant[i]]>=1){
            answer+=participant[i];
            m1[participant[i]]--;
        }
    }
    return answer;
}

처음에는 전체를 1로 만들고 체육복을 도난당한 사람을 0으로 여분의 체육복이 있는 사람을 2로 한 뒤 앞의 사람을 먼저 체크하고 뒤를 체크하는 방식으로 풀려고 했는데 여분의 체육복이 있는 사람도 도난 당할 수 있다는 점을 제대로 못 봐서 틀렸다. 어떻게 하면 좋을까 생각해봤을 때 전체를 1로 만들고 여분이 있는 사람은 2로 만든 다음에 도난 당한 사람은 해당 값을 --로 빼주면 될 것 같다고 생각했다. 

#include <string>
#include <vector>
#include <map>
using namespace std;
map<int, int> m1;
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        m1[i] = 1;					//전체를 1로 
    }

    for (int i = 0; i < reserve.size(); i++) {
        m1[reserve[i]] = 2;				//여분이 있는 사람은 2로
    }
    for (int i = 0; i < lost.size(); i++) {
        m1[lost[i]]--;					//도난당한 사람은 개수 빼주기
    }
    for (int i = 1; i <= n; i++) {
        if (m1[i] == 0) {				//만약 도난당해서 없는 사람이 있다면
            if (m1[i - 1] == 2) {		//앞사람을 먼저 체크
                m1[i - 1]--;
                m1[i]++;
            }
            else if (m1[i + 1] == 2) {
                m1[i + 1]--;
                m1[i]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (m1[i] >= 1) {			//1개 이상이 있다면 수업을 들을 수 있다.
            answer++;
        }
    }
    return answer;
}

문제가 길지만 요약하자면

숫자- 점수를 받고

영어- 점수를 계산

* / # - 보너스 점수

이여서 string을 순회하면서 이 점을 체크해주면 된다. 

*일때는 해당 점수와 바로 전의 점수를 2배 해주면 되고 #일 때는 마이너스로 만들어 주면 되는데 이 것은 영어가 나올 때 * #이 있는 지 확인해서 있다면 적용해주는 방식으로 하면 된다.

#include <string>
#include <cmath>
using namespace std;

int solution(string dartResult) {
    int answer = 0;
    int prev=0,score=0;
    
    
    for(int i=0;i<dartResult.size();i++)
    {
        //숫자 분리
        if(dartResult[i]>='0' && dartResult[i]<='9')
        {
            prev=score;         //보너스 계산을 위해 
            
            if(dartResult[i+1]=='0')
            {
                score=10;
                i++;
            }else{
                score=dartResult[i]-'0';
            }
        }else if(dartResult[i]=='S' || dartResult[i]=='D' || dartResult[i]=='T')
        {
            if(dartResult[i]=='D'){
                score=pow(score,2);
            }else if(dartResult[i]=='T'){
                score=pow(score,3);
            }
            
            if(dartResult[i+1]=='*')
            {           //보너스 점수 계산
                answer-=prev;
                prev*=2;
                score*=2;
                i++;
                answer+=prev;
            }else if(dartResult[i+1]=='#'){
                score*=-1;
                i++;
            }
            answer+=score;
        }
        
    }
    return answer;
}

코딩 문제는 머리로는 어떻게 풀 지 생각이 되는데 그걸 언어로 구현을 생각하기 어렵다. 천천히 풀어 보았다. 

일단 중요한 것은 스테이지 별로 클리어 하지 못한 사용자 수를 저장해야하고

스테이지를 깨고 다음 스테이지에 간 사람도 알고 있어야한다. 

생각을 해보니 

일단 첫번째에 실패한 사람은 다음 스테이지는 당연히 실패하는 것이여서

전체 수를 체크해두고 뺴주는 식으로 가면 된다.

그리고 실패율과 스테이지는 vector 안에 pair 자료형을 통하여 저장하고 정렬은 정렬함수를 만들어서 정렬을 할 수 있게 한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<double,int> &a,pair<double,int> &b){
    if(a.first==b.first) return a.second < b.second;            //실패율 같다면 숫자 큰 순으로
    else return a.first > b.first;
}

int cnt[501];            //스테이지별 클리어하지 못한 사용자 수
vector<pair<double,int>> failure;           //스테이별 실패율 저장할 벡터
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    int st= stages.size();
    for(int i=0;i<st;i++){
        cnt[stages[i]]++;           //스테이지별 클리어하지 못한 사용자 수 저장
    }
    int tmp=st;
    for(int i=1;i<=N;i++){
        
        if(cnt[i]==0) failure.push_back({0,i});     //실패한 사람이 없다면 실패율은 0
        else{
            double t=(double)cnt[i]/tmp;             //실패율 계산
            
            failure.push_back({t,i});
        }
        
        tmp-=cnt[i];         //해당단계에서 실패했다면 다음단계도 실패 총 인원 줄이기
    }
    sort(failure.begin(),failure.end(),compare);
    
    int fsize=failure.size();
    
    for(int i=0;i<fsize;i++){
        auto p =failure[i];
        answer.push_back(p.second);
    }
    
    return answer;
}

숫자 n 까지의 소수를 찾는 문제이다. 처음에는 n까지 for 문을 돌면서 소수를 판별하는 함수로 개수를 세려고 했는데 이렇게 해보니

 효율성 테스트에서 시간초과가 떴다. 왜 그런지 생각해보니 for문을 돌면서 계속 검사를 하면 O(N^2)로 시간복잡도가 계산되기 때문에 실패하는 것이였다. 

방법을 찾아보니 에라토스테네스의 체 라는 방법을 사용하면 시간을 많이 줄일 수 있다고 해서 이 방법을 익히고 사용해 보기로 하였다. 

에라토스테네스의 체

에라토스테네스의 체를 설명한 그림이다. 

소수 인것을 찾고 소수의 배수를 찾아 체크하는 과정을 반복하면 체크하지 않은 것이 소수이여서 이런 방식으로 소수를 찾을 수 있다.

전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> v(n+1,true);
    
    for(int i=2;i<=n;i++){              //전체 순회
        if(v[i]){               //소수라면
            for(int j=2;j*i<=n;j++){            //배수 찾기
                v[i*j]=false;               //배수는 소수가 아니다.
            }
            answer++;
        }
    }
    return answer;
}