알고리즘 : 2016년
a, b를 입력받아 a월 b일은 몇요일인가를 출력하는 알고리즘이다.
윤년이라 2월은 29일이다 1/1은 금요일부터 시작한다.
string solution(int a, int b)
{
vector<string> vecDay = {"THU", "FRI", "SAT" ,"SUN","MON", "TUE", "WED" };
int days = 0;
for (int i = 1; i < a; ++i)
{
if (i == 2)
days += 29;
else if (i % 2 == 0 && i < 7 || i > 7 && i % 2 == 1)
days += 30;
else
days += 31;
}
days += b;
days %= 7;
return vecDay[days];
}해당 알고리즘은 이렇게 완성시켜놓았다 반복문 안에서 총 일수를 계산하고 총일수를 7로 나눈 값을 출력하는 방식이다 풀이를 보니 더 직관적으로 풀이한 방법이 있어서 적어 두고자한다. 좋은 코드란 단순하고 직관적이고 속도가 빨라야 한다고 생각한다. 물론 반복문 돌려도 속도차이는 크지 않겠지만 직관적인가 라는 생각이든다. switch문을 활용하여 풀이한 것을 개량해서 해봤는데 만족스러웠다.
string solution(int a, int b) {
vector<string> vecDay = {"THU", "FRI", "SAT" ,"SUN","MON", "TUE", "WED" };
int days = 0;
switch (a)
{
case 12: days += 30;
case 11: days += 31;
case 10: days += 30;
case 9: days += 31;
case 8: days += 31;
case 7: days += 30;
case 6: days += 31;
case 5: days += 30;
case 4: days += 31;
case 3: days += 29;
case 2: days += 31;
case 1: days += b;
default:
break;
}
days %= 7;
return vecDay[days];
}같은 총 일수를 스위치문을 활용한 로직은 break문을 쓰는게 불만이였는데 역순으로 case를 놓으면 break문 없이 모든 일수를 구할 수 있다. 아름답지 않은가 단순하고 if문을 통한 예외처리도 없어서 더 빠르다. 하드코딩이 이렇게 아름 다울 수 있다는 것에 감동받았다.
시간복잡도
프로그램 수행 성능을 최악의 경우를 가정하여 정량화 하는 방법이다.
문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화 하는 것.
int find_max_num(const vector<int>& arr)
{
for (int i = 0; i < (int)arr.size(); i++)
{ // arr의 길이만큼 아래 연산이 실행
bool isMax = true;
for (int j = 0; j < (int)arr.size(); j++)
{ // arr의 길이만큼 아래 연산이 실행
if (arr[i] < arr[j])
{ // 비교 연산 1번 실행
isMax = false;
break;
}
}
if (isMax)
{ // 비교 연산 1번 실행하지만 미미하므로 편의상 실행시간엔 포함시키지 않을게요!
return arr[i];
}
}
}시간복잡도 = 수행하는데 걸리는 시간과 입력의 함수관계이다.
- 입력 : array의 원수 개수 N
- 시간 : array의 원소 개수 * aaray의 원소 개수만큼 비교 연산 = N * N
따라서 N^2만큼의 시간이 소요된다고 볼 수 있다.
시간복잡도는 Big-O 표기법으로 표시하며, 이 경우엔 O(N^2)의 시간 복잡도를 가진다고 한다.
#include <iostream>
#include <vector>
using namespace std;
int find_max_num_linear(const vector<int>& arr)
{
int max_num = arr[0]; // 대입연산 1번
for (int num : arr)
{
if (num > max_num) // 비교연산 1번
{
max_num = num; // 대입연산 1번
}
}
return max_num;
}
int main()
{
cout << "정답 = 6 / 현재 풀이 값 = " << find_max_num_linear({3, 5, 6, 1, 2, 4}) << "\n";
cout << "정답 = 6 / 현재 풀이 값 = " << find_max_num_linear({6, 6, 6}) << "\n";
cout << "정답 = 1888 / 현재 풀이 값 = " << find_max_num_linear({6, 9, 2, 7, 1888}) << "\n";
}위 함수의 시간복잡도 계산은 다음과 같다.
- 입력 : array 원소 N
- 실행 시간
- max_num 대입 연산 = 1번
- max_num 대입 연산 1번 + array의 길이 * (비교연산 1번 + 대입연산 1번) = 1 + 2N
시간복잡도는 2N+1 된다. BigO표기법에서는 N의 지수부분만 유효하게 쓰이고 나머지는 절삭하므로
O(N)이 된다.
공간복잡도
시간복잡도와 다르게 공간복잡도는 문제를 해결하는데 필요한 메모리의 상관관계를 말하낟.
N개의 입력이 주어지면, 메모리를 얼마나 사용하는지 나타내는 것이다.
#include <iostream>
#include <vector>
#include <algorithm> // max_element 사용
using namespace std;
int largest_product(const vector<int>& arr) {
vector<int> products; // 배열은 벡터를 쓸겁니다!
for (int a : arr)
{
for (int b : arr)
{
// products 배열에 원소가 들어가는 이 연산은 (a * b)번이 실행되겠죠? 2중 루프!
products.push_back(a * b);
}
}
// products의 최대값을 찾는 함수
int maxVal = *max_element(products.begin(), products.end());
// 따라서, products의 공간 복잡도는 O(N^2)
return maxVal;
}
int main()
{
vector<int> myList = {1, 3, 5, 7, 9};
cout << largest_product(myList) << "\n";
}입력 arr의 문제를 해결하기 위한 배열 products슬 생성 products의 원소는 arr을 2중루프로 a*b를 원소로 취하고 있다 따라서 공간 복잡도는 O(N^2)이 된다.
자료구조
배열
배열은 매우 자연스럽게 사용할 수 있는 자료구조다. 배열의 각 요소는 동일한 타입이어야 하며, 컴파일 시점에 타입이 결정된다. 인덱스를 통한 접근이 가능하기에 조회시간은 O(1) 을 가진다. 랜덤한 인덱스의 접근하더라도 값을 바로 가져올 수 있기에 장점이 많다.
그러나 삽입&삭제의 경우 배열의 끝단에서 재할당을 하지 않았을 때 삽입 및 삭제를 할 경우 시간복잡도는 O(1)이 되지만 중간에서 삽입 및 삭제를 할 경우 O(N)이 된다.
vector<int> arr = {1, 2, 3, 4, 5};
arr.insert(arr.begin() + 2, 7);
// 결과: {1, 2, 7, 3, 4, 5}중간에서 삽입 삭제할 경우 다음과 같은 과정이 일어난다.
- 새로운 공간 확보.
- 삽입할 인덱스부터 원소를 한칸씩 뒤로 이동
- 해당 인덱스의 값 복사
정렬
어떤 알고리즘을 사용 하느냐에 따라 시간복잡도가 다르다.
std::stort의 경우 O(N log N)의 시간복잡도를 가진다.검색
- 일반적으로 O(N)이다 원소 시작부터 끝까지 봐야 하기 때문이다.
- 정렬된 배열의 경우 이진검색을 사용하면 O(Log N)이 가능하다.
Linked List
데이터를 담고 있는 노드의 양끝단에 다른 노드들을 연결한 형태의 자료구조이다.
배열이 조회에 강점을 가졌다면 링크드리스트는 삽입 삭제에 강점을 가졌다.
조회성능은 O(N)이다. 삽입삭제 O(1)
아래는 linked List를 구현한 예제이다.
template <typename T>
class Node
{
template<typename T>
friend class LinkedList;
private:
Node() : m_next(nullptr), m_prev(nullptr) {}
~Node() {}
private:
Node* m_prev;
T m_Data;
Node* m_next;
};
template <typename T>
class LinkedList
{
private:
typedef Node<T>* PNODE;
typedef Node<T> NODE;
public:
LinkedList()
{
m_Size = 0;
m_Head = new NODE;
m_Tail = new NODE;
m_Head->m_next = m_Tail;
//m_Tail->m_next = m_Head;
m_Tail->m_prev = m_Head;
//m_Head->m_next = m_Tail;
}
~LinkedList()
{
PNODE Node = m_Head;
while (Node != nullptr)
{
PNODE Next = Node->m_next;
delete Node;
Node = Next;
}
}
private:
PNODE m_Head;
PNODE m_Tail;
int m_Size;
public:
void append(const T& Data);
PNODE getNode(int Index);
void addNode(int Index, const T& Data);
};
template<typename T>
inline void LinkedList<T>::append(const T& Data)
{
PNODE Node = new NODE;
PNODE Prev = m_Tail->m_prev;
Node->m_Data = Data;
m_Tail->m_prev = Node;
Node->m_next = m_Tail;
Prev->m_next = Node;
Node->m_prev = Prev;
++m_Size;
}
template<typename T>
inline Node<T>* LinkedList<T>::getNode(int Index)
{
if (m_Size < Index)
return m_Tail;
PNODE Node = m_Head;
for (int i = 0; i < m_Size; ++i)
{
Node = m_Head->m_next;
}
return Node;
}
template<typename T>
inline void LinkedList<T>::addNode(int Index, const T& Data)
{
if (m_Size < Index)
return m_Tail;
PNODE Node = getNode(Index);
PNODE Next = Node->m_next;
PNODE NewNode = new NODE;
NewNode->m_Data = Data;
NewNode->m_next = Next;
Next->m_prev = NewNode;
NewNode->m_prev = Node;
Node->m_next = NewNode;
}TobeContinue
