구이팔이

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;
}

아나그램이란?

- 한 단어의 철자를 분해해 다른 단어, 혹은 다른 문장으로 바꾸는 놀이를 의미

- 같은 영어 알파벳을 가지고도 다른 뜻을 가지는 단어를 만들수 있다는 것이죠.

God save us all(신은 우리 모두를 구하신다) → Salvaged soul(구원받은 영혼)

두개의 string을 비교하여 같은 수의 알파벳이 존재하면 true를 리턴 아닐 시 false 리턴

처음 접근 한 방법은 일단 최대한 쉽게 정답을 도출하고 더 좋은 방법을 생각하고자

무작정 2중 포문을 사용하여 전체를 비교하는 방법으로 접근하는 도중

string을 정렬하여 비교하는 방법을 떠올라 사용하였다.

정렬 후에 각각의 길이를 비교하여 for문을 들어가기전에 길이가 다를 경우

false를 반환하여 조금이라도 더 빠르게 계산할 수 있도록 하였다

기록으로 남기려고 집에서 visual studio로 작성하다보니 for문을 사용하지않고 비교하면 된다는걸

1분도 안되어 알게되어서 많이 후회되었다 좀 더 침착하게 풀어볼껄... 손코딩이여서 그랬을까..

막히던 순간에 방법이 갑자기 생각나서 답을 찾았다는 기쁨에 더욱 신중하게 접근하지 못한 것이 문제였던 것 같다...

스스로 생각하는 최종 코드

였는데...

시간 복잡도에 대하여 고민하다 보니

최종적으로 고친 코드에서 두개의 길이를 비교하는 과정을 생략해주어도 될 것같다는

생각이 나왔다 첫번째 코드에서는 for문으로 하나씩 비교하는 과정을 조금이라도 줄이기 위해

길이를 비교하여 1차적으로 확인하여 for문을 들어가기 전에 길이가 다르면 for문을 돌리지 않고 결과를

반환하는 것이였는데 수정한 코드는 for문을 돌지 않으니 그 과정 또한 필요하지 않다고 생각하게 되었다.

총 코드

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

bool IsAnagram(string a, string b)
{
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	if (a == b)
		return true;
	return false;
}

//bool IsAnagram1(string a, string b)
//{
//	sort(a.begin(), a.end());
//	sort(b.begin(), b.end());
//	if (a.size() != b.size())
//		return false;
//	for (auto i = 0; i < a.size(); i++)
//	{
//		if (a[i] != b[i])
//			return false;
//	}
//	return true;
//}
int main()
{
	string a = { "aabbcc" };
	string b = { "bwccaa" };

	if (IsAnagram(a, b) == true)
		cout << "true" << endl;
	else
		cout << "false" << endl;
}

시간 복잡도

시간복잡도란 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미

빅오 O() 표기법

- 최악의 경우를 계산하는 방식

- 아무리 많은 시간이 걸려도 이 시간 안에는 끝난다

O(1) 상수형

- 입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘

O(log₂ n) 로그형

- 입력 데이터의 크기가 커질수록 처리 시간이 로그 만큼 짧아지는 알고리즘

- 이진탐색, 재귀가 순기능으로 이루어지는 경우

- 데이터가 10배가 되면 처리시간은 2배

O(n) 선형

- 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘

- for문 하나의 경우

- 데이터가 10배가 되면 처리시간도 10배

O(n log₂ n) 선형 로그형

- 입력 데이터의 크기가 커질수록 처리 시간이 로그 배만큼 늘어나는 알고리즘

- 병합 정렬, 퀵정렬의 경우

- 데이터가 10배가 되면 처리시간은 20배

O(n²) 2차제곱형

- 입력 데이터의 크기가 커질수록 처리시간이 급수적으로 늘어나는 알고리즘

- for문 두개의 경우

- 데이터가 10배가 되면 처리시간은 100배

O(2ⁿ) 지수형

- 입력 데이터의 크기가 커질수록 처리시간이 기하급수적으로 늘어나는 알고리즘

- 재귀의 역기능으로 이루어지는 경우

O(n!) 팩토리얼형

- 처리시간이 기하급수적으로 늘어나는 알고리즘

시간 복잡도를 줄이는 방법

1. 반복문을 최소화

2. 상황에 맞는 자료구조와 알고리즘을 사용

Circle Queue 원형큐란?

- 원형큐의 단점을 보완한 자료구조

- FIFO (First In First Out) 선입선출

선형큐와 모두 같고 선형큐의 단점인

- 데이터 공간 낭비을 해결한 것이 원형큐이다.

- 데이터가 꽉 차지않는 이상 데이터 공간 낭비없이 계속적으로 데이터를 삽입, 삭제 할 수 있다.

Enqueue == 데이터 삽입

Dequeue == 데이터 삭제

- 데이터 삽입시 front의 뒤쪽에 삽입하고 rear이 가르킨다.

- 데이터 제거시 front를 한칸 앞으로 전진하여 가르킨다 

- rear과 front가 같은 위치 일때 데이터가 꽉찬 것이다.

Linear Queue 선형 큐란?

- FIFO(First In First Out) 구조, 선입선출, 선형 데이터 구조

- 데이터를 받는 순서대로 저장하고 받은 순서대로 출력

- 배열, 연결리스트로 구현하는 방법 존재

- c++ STL에서 #include<queue> 추가하여 사용가능

시간 복잡도

삽입, 삭제의 시간 복잡도는 O(1)

장점

- 데이터 접근, 삽입, 삭제가 빠르다.

단점

- 스택의 앞쪽에만 접근 가능, 탐색 불가능

- front와 rear이 증가되는 방식으로 front 앞의 공간이 있어도 삽입 불가 (원형큐로 해결가능) 

사용

- BFS 알고리즘

- 순서대로 처리하는 작업이 필요할 때

front == 큐의 앞쪽 (데이터가 없다)

rear == 큐의 뒤쪽 (마지막에 들어온 데이터)

삽입된 순서 : A -> B -> C -> D

출력시 순서 : A -> B -> C -> D

stack 이란?

- LIFO (Last In First Out) 후입선출 선형 데이터 구조

- 데이터를 받는 순서대로 정렬하고 받은 역순으로 처리

- 배열, 연결리스트로 구현하는 방법 존재

- c++ STL에서 #include<stack> 추가하여 사용가능

시간 복잡도

스택 상단의 위치의 데이터 삽입, 삭제의 시간 복잡도는 O(1)

장점

- 데이터 접근, 삽입, 삭제가 빠르다.

단점

- 스택 상단에만 접근 가능, 탐색 불가능

사용

- 재귀 알고리즘

- DFS 알고리즘

- 역순의 작업이 필요할 때

스택 하단 == 스택의 제일 아래

스택 상단 == 스택의 제일 위

요소 == 스택에 저장되는 데이터

삽입된 순서 : A -> B -> C -> D

출력시 순서 : D -> C -> B -> A

프로그래머스 여행경로 문제

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

문제를 푸는데

count++;

count = count +1;

dfs(count++)

dfs(++count) 를 하면 실패하고

dfs(count+1) 을 하면 성공한다 

이유는 아직 찾지 못했는데 계속 찾아봐야겠다

총코드

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

bool check[10000];
vector<string> result;


bool dfs(string begin, vector<vector<string>> tickets,int count)
{
	//vector<vector<string>> v = { { "ICN", "SFO" },{ "ICN", "ATL" },{ "SFO", "ATL" },{ "ATL", "ICN" },{ "ATL", "SFO" } };
	if (count == tickets.size())
		return true;
	for (unsigned int i = 0; i < tickets.size(); i++)
	{
		if (check[i] == false && begin == tickets[i][0])
		{
			result.push_back(tickets[i][1]);
			check[i] = true;
			if (dfs(tickets[i][1], tickets, count + 1) == true)
				return true;
			check[i] = false;
		}
	}
	result.pop_back();
	return false;
}

vector<string> solution(vector<vector<string>> tickets) {
	
	sort(tickets.begin(), tickets.end());
	string begin = "ICN";

	result.push_back(begin);

	dfs(begin, tickets, 0);

	for (auto i : result)
		cout << i << endl;
	return result;
}

int main()
{
	vector<vector<string>> v = { {"ICN", "SFO"},{"ICN", "ATL"},{"SFO", "ATL"},{"ATL", "ICN"},{"ATL", "SFO"} };
	solution(v);
}

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

문제 출처 : 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);

총 코드

#include<iostream>
using namespace std;

#define MAX 256

class Node
{
private:
	int val;
	Node* link;
public:
	Node(int val, Node* link);
	~Node();
	int GetVal();
	void SetVal(int value);
	Node* GetLink();
	void SetLink(Node* node);

};

Node::Node(int val, Node * link)
{
	this->val = val;
	this->link = link;
}

Node::~Node()
{
}

int Node::GetVal()
{
	return val;
}

void Node::SetVal(int value)
{
	val = value;
}

Node* Node::GetLink()
{
	return link;
}

void Node::SetLink(Node* node)
{
	link = node;
}


class AdjListGraph
{
	int size;
	char vertex[MAX];
	Node* adjList[MAX];
public:
	AdjListGraph();
	~AdjListGraph();
	void InsertVertex(char name);
	void InserEdge(int u, int v);
	char GetVertex(int i) { return vertex[i]; }
	void Display();
};

AdjListGraph::AdjListGraph()
{
	size = 0;
}

AdjListGraph::~AdjListGraph()
{
}

void AdjListGraph::InsertVertex(char name)
{
	vertex[size] = name;
	adjList[size++] = NULL;
}

void AdjListGraph::InserEdge(int u, int v)
{
	adjList[u] = new Node(v, adjList[u]);
	adjList[v] = new Node(u, adjList[v]);
}

void AdjListGraph::Display()
{
	cout << "vertex size: " << size << endl;
	for (int i = 0; i < size; i++)
	{
		cout << GetVertex(i) << " : ";
		Node* head = adjList[i];
		while (head != NULL)
		{
			cout << GetVertex(head->GetVal()) << " ";
			head = head->GetLink();
		}
		cout << endl;
	}
}

int main()
{
	AdjListGraph graph;

	graph.InsertVertex('a');
	graph.InsertVertex('b');
	graph.InsertVertex('c');
	graph.InsertVertex('d');

	graph.InserEdge(0, 1);
	graph.InserEdge(0, 2);
	graph.InserEdge(1, 2);
	graph.InserEdge(2, 3);

	graph.Display();
}

총 코드

#include<iostream>
using namespace std;

#define MAX 256

class AdjMatrixGraph
{
private:
	int size;
	char vertex[MAX];
	int edge[MAX][MAX];
public:
	AdjMatrixGraph() {};
	~AdjMatrixGraph() {};
	void Init();
	char GetVertex(int i) { return vertex[i]; }
	void SetVertex(char ch) { vertex[size++] = ch;  }
	int GetEdge(int i, int j) { return edge[i][j]; }
	void SetEdge(int i, int j, int val) { edge[i][j] = val; }
	void InsertVertex(char name);
	void InsertEdge(int u, int v);
	void Display();
};

void AdjMatrixGraph::Init()
{
	size = 0;
	for (auto i = 0; i < MAX; i++)
	{
		for (auto j = 0; j < MAX; j++)
		{
			SetEdge(i, j, 0);
		}
	}
}

void AdjMatrixGraph::InsertVertex(char name)
{
	if (size > MAX)
	{
		cout << "Graph Vertex FULL ERROR" << endl;
		return;
	}
	SetVertex(name);
}

void AdjMatrixGraph::InsertEdge(int u, int v)
{
	SetEdge(u, v, 1);
	SetEdge(v, u, 1);
}

void AdjMatrixGraph::Display()
{
	cout << "Vertex size : " << size << endl << endl;
	cout << "  ";
	for (auto i = 0; i < size; i++)
	{
		cout << vertex[i] << " ";
	}
	cout << endl;
	for(auto i = 0; i < size; i++)
	{
		cout << vertex[i] << ":";
		for (auto j = 0; j < size; j++)
		{
			cout << GetEdge(i,j) << " ";
		}
		cout << endl;
	}
}

int main()
{
	AdjMatrixGraph graph;
	graph.Init();
	graph.InsertVertex('A');
	graph.InsertVertex('B');
	graph.InsertVertex('C');
	graph.InsertVertex('D');

	graph.InsertEdge(0, 1);
	graph.InsertEdge(0, 2);
	graph.InsertEdge(1, 2);
	graph.InsertEdge(1, 3);
	graph.InsertEdge(2, 3);

	graph.Display();
}