D-3

1. BFS 문제풀이

 

2. sw expert academy D3 문제 : flatten 평탄화

투포인터를 사용해서 풀었음

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int num;
		vector<int> height(100);

		cin >> num;
		for (int i = 0; i < 100; i++) {
			cin >> height[i];
		}

		int cnt;
		vector<int> each_height(101);
		for (int h = 1; h <= 100; h++) {
			cnt = 0;
			for (int i = 0; i < 100; i++) {
				if (height[i] >= h) {
					cnt++;
				}
			}
			each_height[h] = cnt;
		}


		int start = 1;
		int end = 100;

		while (num > 0) {
			if (each_height[start] == 100) {
				start++;
				continue;
			}
			else if (each_height[end] == 0) {
				end--;
				continue;
			}
			else {
				each_height[start]++;
				each_height[end]--;
				num--;
			}
		}

		if (each_height[start] == 100) {
			start++;
		}
		else if (each_height[end] == 0) {
			end--;
		}
		cout << "#" << test_case << " " << end - start+1<< "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

3. 프로그래머스 동적 계획법 - N으로 표현

 

너무나 어려웠던 동적 계획법.

DP 는 배열을 그냥 인덱스와 순서가 같도록 설정해야 그나마 내 머리가 따라가준다는 걸 먼저 알 수 있었다.

인터넷에서 찾을 때, 2= 1+1, 3=1+2 or 2+1 이라는 비유가 어느정도 도움이 되었다.

 

또한 DP의 조합을 찾을 때,

DP[4] = DP[1] + DP[3] , DP[2] + DP[2], DP[3] + DP[1] 이런 식으로 조합을 찾아내는 걸 어떻게 할까 고민했는데,

이중 for문에서

if(y+x != 4){
	continue;
}

그냥 이런 식으로 짜서 조합을 찾아내는 구현도 쓸모 있다는 것을 배웠다.

 

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

int calNN(int N, int cnt){
    int num = 0;
    for(int i=0; i<cnt; i++){
        num = num * 10 + N;
    }
    return num;
}

int solution(int N, int number) {
    vector<unordered_set<int>> DP(9);
    
    DP[1].insert(N);
    //첫번째 바로 맞으면
    if(DP[1].find(number) != DP[1].end()){
        return 1;
    }
    
    for(int i=2; i<=8; i++){
        //NN... 과 N 사칙연산 저장
        DP[i].insert(calNN(N, i));
        
        //계산 가능한 모든 값 저장 DP[1] =  DP[0] (사칙연산) NN
        //|| DP[0] (사칙연산) DP[0]
        
        for(int y=1; y<i; y++){
            for(int x=1; x<i; x++){
                if(y+x != i){
                    continue;
                }
                //갯수 조합에 해당하면
                for(int num1 : DP[y]){
                    for(int num2 : DP[x]){
                        DP[i].insert(num1+num2);
                        DP[i].insert(num1*num2);
                        DP[i].insert(num1-num2);
                        if(num2 != 0){
                            DP[i].insert(num1/num2);
                        }
                    }
                }
            }
        }

        //다음 DP로 가기전에 답이 있는지 확인
        if(DP[i].find(number) != DP[i].end()){
            return i;
        }
    }
    return -1;
}

 

 

4. 최빈수

알고리즘이 아닌 점수별 백터 나열로 해결함

이 때, 항상 추가 조건을 주의할 것. 최빈값이 같다면 더 큰 값으로 취급한다는.

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

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int case_num;
		cin >> case_num;
		
		vector<int> score(101);
		int temp;
		for (int i = 0; i < 1000; i++) {
			cin >> temp;
			score[temp]++;
		}
		
		int max_num = 0;
		int max_index;
		for (int i = 0; i <= 100; i++) {
			if (score[i] > max_num) {
				max_index = i;
				max_num = score[i];
			}
			else if (score[i] == max_num) {
				max_index = max(max_index, i);
			}

		}

		//최대값의 주소 반환.따라서 *을 통해 값을 반환해줘야 함. 현재는 index == score임
		cout << "#" << case_num<< " "<< max_index << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

 

5. 타겟 넘버

전역 백터를 썼더니 프로그래머스에서는 세그멘테이션 오류를 뱉어서 이리저리 바꿨다.

 

아래 코드는 고치기 전 전역 백터 코드.

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

using namespace std;

int answer = 0;
vector<int> c_numbers;

int DFS(int current_v, int index, int target) {
    if (index >= c_numbers.size()) {
        //비교
        if (target == current_v) {
            answer++;
        }
        return 0;
    }
    //더하거나
    DFS(current_v + c_numbers[index], index + 1, target);

    //빼거나
    DFS(current_v - c_numbers[index], index + 1, target);

}

int solution(vector<int> numbers, int target) {
    c_numbers = numbers;

    //숫자를 더하거나, 뻬거나
    DFS(0, 0, target);

    cout << answer;
    return 0;
}

int main() {
    solution({4, 1, 2, 1}, 2);
    return 0;
}

 

 

6. sw expert 점프 놀이

다시 나온 동적 계획법. 아직 동적 계획법은 코드가 안 떠오른다.

 

요약하자면 최단 거리를 저장하는 이중 백터를 하나 더 만든 후, 1을 쭉 돌면서 0에서부터 오는 최소값을(없으니까 0),

2를 쭉 돌면서 1에서부터 오는 최소값을( 거리 + shortest 백터 1의 값 ) 을 저장하면서 진행하는 것.

 

다음날 해결