구이팔이

시간 복잡도

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

빅오 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. 상황에 맞는 자료구조와 알고리즘을 사용

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

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