씅의 기록하는 개발노트

문제출처

https://programmers.co.kr/learn/courses/30/lessons/12977

문제풀이

재귀 함수를 이용해 숫자의 합을 구한뒤 소수 판별을 해주면 되는 간단한 문제

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%86%8C%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

#include <vector>
#include <cmath>
using namespace std;
int ans = 0;
bool checkPrime(int number) {
    if (number == 1) return false;
    if (number == 2) return true;
    for (int i=2; i<=sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
void go(vector<int> nums, int startIdx, int depth, int sum) {
    if (depth == 3) {
        if (checkPrime(sum)) {
            ans++;
        }
        return;
    }
    for (int i=startIdx; i<nums.size(); i++) {
        go(nums, i+1, depth+1, sum+nums[i]);
    }
}
int solution(vector<int> nums) {
    go(nums, 0, 0, 0);
    
    return ans;
}

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/43164

문제 풀이

dfs로 풀이했는데 전체 탐색을 중간에 멈추는 방법을 생각하지 못했다. 그래서 탐색할 수 있는 전체 경로가 출력되서 자꾸 테스트 케이스도 통과 못하는 경우가 발생했다.
생각한 해결책은 2차원 벡터를 만들어 기저조건일 때 2차원 벡터에 경로를 넣어주는 것이다. 이후 전체 탐색이 완료되면 정렬한뒤 가장 앞에 있는 경로를 return하면 된다.
dfs탐색은 보통 알고 있는 방법대로 진행했는데 탈출 조건이나 정답을 return하는게 더 어려웠던 문제.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C.cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<bool> visit;
vector<string> path;
vector<vector<string>> answer;
void getTravelPath(vector<vector<string>> &tickets, string from, int depth) {
	if (tickets.size() == depth) {
		answer.push_back(path);
		return;
	}

	for (int i=0; i<tickets.size(); i++) {
		if (visit[i] || from != tickets[i][0]) continue;
		visit[i] = 1;
		path.push_back(tickets[i][1]);
		getTravelPath(tickets, tickets[i][1], depth+1);
		path.pop_back();
		visit[i] = 0;
	}
}
vector<string> solution(vector<vector<string>> tickets) {
    visit.resize(tickets.size(), 0);
    path.push_back("ICN");
    getTravelPath(tickets, "ICN", 0);
    sort(answer.begin(), answer.end());
    return answer.front();
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/62049

문제풀이

규칙을 찾아내면 쉬운 문제. 규칙을 처음에 찾으려고 직접 종이를 접어가면서 풀이했다. 직접 종이를 접어가며 나오는 출력값을 적어가는 도중 0을 대칭으로 어떤 연산이 일어나는 걸 알아차렸다. 

즉 n이 3인경우 0 0 1 -> 0 0 1 0 0 1 1 으로 바뀌는데 0 0 1 뒤에 0을 붙이고 n이 2일때의 값을 뒤집어서 1이면 0, 0이면 1을 넣어주면 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%A2%85%EC%9D%B4%EC%A0%91%EA%B8%B0.cpp

#include <string>
#include <vector>

using namespace std;
/*
* 규칙 
* n = 1 -> 0
* n = 2 -> 0 0 1
* n = 3 -> 0 0 1 0 0 1 1
* n = 4 -> 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1
* n = 2 -> 3이 될때 0 0 1과 0 1 1 을 보면 기존 0은 1로 1은 0으로 바뀌고 가운데 0이 끼는 것을 알 수 있음
* n = 3 -> 4가 될때도 기존 3인 값에 0이 추가 되고 역순으로 0은 1로 1은 0으로 바뀜
*/
vector<int> solution(int n) {
    vector<int> answer;
    answer.push_back(0);
    if (n == 1) return answer;
    for (int i=2; i<=n; i++) {
        vector<int> temp = answer;
        answer.push_back(0);
        for (int j=temp.size()-1; j>=0; j--) {
            if (temp[j] == 0) answer.push_back(1);
            else if (temp[j] == 1) answer.push_back(0);
        }
    }
    
    return answer;
}