구이팔이

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

문제 접근 풀이

1. 폰켓몬 종류의 최대값을 return하면 되니까 같은 값의 경우 무시하고 다른 값들에 대해서 접근한다

2. 정렬을 해놓은 상태로 접근하면 한번의 for문으로 중복된 값을 신경쓰지 않고 처리할 수 있다고 생각했다

3. 정렬을 하고 같은 값인 경우 넘어가고 아닌 경우의 값을 저장하여 비교한다 answer의 값은 1 증가시켜준다

이상태로 제출하니 맞고 틀리고 하는 상황이 발생했는데

폰켓몬을 선택할 수 있는 것은 총 수의 n/2 이므로 마지막에 조건을 추가해주어 정답에 도출하게 되었다

총코드

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

int solution(vector<int> nums)
{
    int answer = 1;
    sort(nums.begin(),nums.end());
    int tempNum = nums[0];
    for(auto i : nums)
    {
       if(tempNum == i)
           continue;
        else
        {
            tempNum = i;
            answer++;
        }
    }
    if(answer > nums.size()/2)
        return nums.size()/2;
    return answer;
}

프로그래머스 단어변환 문제

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43163

문제 풀이 생각

방향을 잘못 잡았는지 3일 동안 틈틈히 생각하면서 풀게 되었다

풀긴 풀었는데 한번에 딱 답을 찾은 것이 아니라 주먹구구 식으로 

여러 방법으로 수정하다보니 정확한 방향성을 갖고 풀지 못했다

몇일 뒤에 다시한번 풀어봐야겠다. 만족스럽지 못하다..;;

총 코드

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

bool check[51];
int result = 51;
int compare(string a, string b)
{
	int count = 0;
	for (auto i = 0; i < a.size(); i++)
	{
		if (a[i] != b[i])
			count++;
		
		//	cout << a[i] << ", " << b[i] << endl;
	}
	cout << a << ", " << b << endl;
	cout << count << endl;
	return count;
}

void dfs(string begin, string target, vector<string> words, int answer)
{
	cout <<"asd: " <<answer << endl;
	if (begin == target)
	{
		cout << result << "," << answer << endl;
		if (result > answer)
			result = answer;
		return;
	}
	for (auto i = 0; i < words.size(); i++)
	{
		int count = 0;
		if (check[i] == false)
			count = compare(begin, words[i]);

		if (count == 1)
		{
			answer++;
			check[i] = true;
			dfs(words[i], target, words, answer);
			check[i] = false;
		}


	}


}


int solution(string begin, string target, vector<string> words) {
	//int answer = 0;

	for (auto i : words)
	{
		if (compare(target, i) == 0)
		{
			cout << "타겟이 있다" << endl;
			dfs(begin, target, words, 0);
			return result;
		}
	}

	result = 0;
	return result;
}

int main()
{
	string begin = "hit";
	string target = "cog";
	vector<string> words = { "hot", "dot", "dog", "lot", "log", "cog" };

	cout << solution(begin, target, words);

프로그래머스 네트워크 문제

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43162

문제 풀이 생각

1. 전체를 순회해야한다.

2. 인접행렬으로 대칭이다.

3. 연결 상태는 1로 표시 되어있다.

4. 인접행렬은 연결된 부분이 대칭으로 1로 표시 되어 있으니

   순회 후 0 으로 만들 때 대칭 두 곳을 0을 만들어준다. 

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

void dfs(int num, vector<vector<int>>& computers, int& answer)
{
	for (auto i = 0; i < computers.size(); i++)
	{
		//자기 자신
		if (i == num)
			computers[i][num] = 0;
		//아직 순회 하지 않았을 때
		if (computers[num][i] == 1)
		{
			//연결된 노드 양쪽 다 방문 처리
			computers[num][i] = 0;
			computers[i][num] = 0;
			dfs(i, computers, answer);
		}
	}
	
}

int solution(int n, vector<vector<int>> computers) 
{
	int answer = 0;
	
	for (auto i = 0; i < n; i++)
	{
		if (computers[i][i] == 1)
		{
			dfs(i, computers, answer);
			answer++;
		}
	}

	return answer;
}


int main()
{
	vector<vector<int>> v = { {1,1,0},{1,1,0},{0,0,1} };
	cout<<solution(3, v)<<endl;
}

프로그래머스 타겟 넘버 문제

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

풀이 과정 생각

1. 배열 numbers의 값들을 더하고 뺀 모든 결과를 찾는다.

2. 최종 결과 값 중에서 target의 값과 일치한 경우의 수들을 합친다.

모든 배열 numbers의 값을 더하기 위해 sum 인자 생성

마지막 배열에 도달 했는지 확인하기 위해 count 인자 생성

dfs로 각각의 위치한 결과를 합치기 위해 answer을 &로 접근하여 저장

풀이 코드

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


void dfs(vector<int> numbers, int target, int sum, int count, int& answer)
{
	if (count == numbers.size())
	{
		if (target == sum)
			answer++;
		return;
	}
	dfs(numbers, target, sum + numbers[count], count + 1, answer);
	dfs(numbers, target, sum - numbers[count], count + 1, answer);
}
int solution(vector<int> numbers, int target)
{
	int answer = 0;
	int count = 0;
	dfs(numbers, target, 0, 0, answer);
	return answer;
}


int main()
{
	vector<int> v(5, 1);
	
	cout << solution(v, 3);
}