기록을

#include <bits/stdc++.h>
using namespace std;

bool cmp(int a, int b) { //정렬
	//return a > b;
	if (a > b)
		return true;
	else
		return false;
}

void vectorPrac(){ //벡터
	vector<int> v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(-1);

	sort(v.begin(), v.end(), cmp); //정렬 함수 사용자 정의

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	cout << '\n';

	v.erase(v.begin() + 1); //특정 인덱스 원소 제거

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}


	vector<string> strv;
	strv.push_back("abc\n");
	cout << strv[0];

	string a = "abcdef";
	string subs = a.substr(1, 3); //1번째부터 시작해서 길이 3만큼
	cout << subs << '\n';
}


void stackPrac(){ //스택
	stack<int> stk;
	stk.push(1);
	stk.pop();
	stk.push(5);
	stk.push(4);
	cout << "스택크기 = " << stk.size() << '\n';
	while(!stk.empty()){
		cout << stk.top() << ' ';
		stk.pop();
	}
	cout << '\n';
}

void queuePrac(){ //큐
	queue<int> q;
	q.push(1);
	q.push(2);
	cout << "큐 크기 = " << q.size() << '\n';
	while(!q.empty()){
		cout << q.front() << ' ';
		q.pop();
	}
	cout << '\n';
}

void mapPrac(){
	map<string, int> mp;
	mp.insert({"abc", 1});
	mp.insert({"def", 2});
	mp.insert({"abc", 3}); //이미 존재하는 key에 대해서 insert 하면 무시된다
	mp["abc"] = 3; //하지만 이렇게 수정하면 반영된다.
	for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
		cout << itr->first << " " << itr->second << '\n';
		cout << itr->first << " " << mp[itr->first] << '\n';
	}
	cout << "맵 크기 = " << mp.size() << '\n';
	
}

void setPrac(){
	vector<int> v = {4,4,4,5,1,1,1,2,3};
	for(int i = 0 ; i < v.size() ; i++){
		cout << v[i] << ' ';
	}
	cout << '\n';
	
	set<int> st;
	for(int i = 0 ; i < v.size() ; i++){
		st.insert(v[i]);
	}
	for(auto itr = st.begin() ; itr != st.end() ; itr++){
		cout << *itr << ' ';
	}
	cout << '\n';
	
	set<int, greater<int> > bigSt;
	for(int i = 0 ; i < v.size() ; i++){
		bigSt.insert(v[i]);
	}
	for(auto itr = bigSt.begin() ; itr != bigSt.end() ; itr++){
		cout << *itr << ' ';
	}
	cout << '\n';
}
void priority_queuePrac(){
	priority_queue<int, vector<int>, less<int> > pq; //내림차순으로 나오는
	pq.push(9);
	pq.push(1);
	pq.push(4);
	pq.push(5);
	pq.push(2);
	while(!pq.empty()){
		cout << pq.top();
		pq.pop();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vectorPrac();
	stackPrac();
	queuePrac();
	mapPrac();
	setPrac();
	priority_queuePrac();
	
}

퀵소트: 

평균 nlogn, 

최악 n^2(데이터가 이미 거의 정렬되어 있는 경우)

머지소트: 

평균: nlogn보장

단점: 메모리 비효율적이라는 문제-> 힙소트로 해결

힙소트:

일단 데이터를 가지고 힙구조를 만들어야함. 이 부분의 복잡도 == NlogN

그리고, 루트의 값을 맨 뒤로 보내면서, 보낸 값을 제외하고 다시 힙을 만드는 비용이 logN. 이걸 N번 반복하니까 NlogN

결국 합치면 총 시간 복잡도는 NlogN이 된다.

장점: 메모리 효율적.

삽입 정렬에 대해 정리해보자.

삽입 정렬은, 선택 정렬 그리고 버블 정렬과 함께 대표적인 시간 복잡도 O(n^2) 알고리즘이다.

하지만 삽입 정렬은, 필요할 때까지만 삽입(스왑)이 일어나기 때문에, 정렬할 배열이 거의 정렬되어 있는 상태라면 다른 선택 정렬, 버블 정렬보다 훨씬 빠른 속도를 보여준다.

버블 정렬 알고리즘에 대해 정리해보자.

이름에서도 알 수 있듯이, 하나의 원소와, 인접원소를 한 칸씩 움직이면서 비교해가는 모습이 거품이 생기는 것 같아서 버블 정렬이다.

굉장히 비효휼적인 알고리즘이고, 시간 복잡도가 O(n^2)이다.

가장 먼저 정리할 정렬 알고리즘은 선택 정렬(insertion sort) 알고리즘이다.

이름에서도 알 수 있듯이, 오름차순으로 정렬한다고 하면, 매 수행에서 가장 작은 값을 선택해서 가장 앞으로 보내는 것이다.

시간 복잡도는 O(n^2)이다.

다음은 특정 배열을 오름차순으로 정렬하는 코드이다.

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 따라서 인덱스로 해당 원소에 접근할 수 있으므로, 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)의 시간 복잡도로 해당 원소에 접근할 수 있다. (Random access 가능)

• 삽입/삭제의 경우, O(1)에 접근은 할 수 있지만, 삽입/삭제 이후에 대부분의 상황에서 원소들을 shift 해주어야 하기 때문에, 이 shift 비용이 최악의 경우 O(n)이 된다.

LinkedList

• 논리적 저장 순서와 물리적 저장 순서가 관계가 없다.

• Random access가 불가능하다. 즉 특정 원소에 접근하고자 할 때, 처음부터 하나씩 찾아가야 한다. 따라서 검색 시 최악의 시간 복잡도는 O(n)이다.

• 삽입 혹은 삭제를 하는 경우에는, 일단 검색을 통해서 원하는 위치에 접근을 한 이후에는, 연결만 해주거나 끊어주면 되기 때문에 검색을 제외한 삽입/삭제의 시간 복잡도는 O(1)이다.

• 결국 처음부터 삽입/ 삭제를 해야하는 경우 시간 복잡도는 O(n)이다.

• Tree의 근간이 되는 자료구조이다.

배열의 경우에 데이터 삽입을 하려고 하는데 처음에 잡은 배열 크기의 범위를 벗어난다면, 새로이 할당을 하여 크기를 키워줘야 한다. 연결리스트는 이러한 과정이 필요 없다.

결론적으로 데이터의 삽입과 삭제가 빈번하게 일어난다면 연결리스트를 사용하면 된다.

그렇지 않고 미리 정해둔 데이터에서 검색만 빈번히 일어난다면 배열을 사용하는 것이 좋다.

하지만 대부분의 알고리즘 문제를 풀이할 경우에는, 메모리와 변수의 입력크기 범위가 주어지기 때문에, 그 한계치로 배열 크기를 잡아두고 사용하면 빠르게 사용할 수 있다.

또한 연결리스트의 경우, 원소 추가 과정마다 메모리의 할당이 발생하고, 삭제 시에는 메모리 해제가 발생하는데, 이러한 system call이 사용되는 부분에서 시간이 걸린다.

정의

속성과 기능을 포함한 프로그램 단위로 프로그램의 구성 요소를 객체화하는 것. 객체의 핵심은 기능을 제공하는 것이며, 기능들을 오퍼레이션이라고 부른다.

인터페이스: (코딩에서 인터페이스 말고)

객체가 제공하는 모든 오퍼레이션 집합을 객체의 인터페이스라고 부른다. 객체 사용을 위한 명세 의미

메시지

오퍼레이션의 실행을 요청하는 것을 메시지를 보낸다라고 표현. 자바나 파이썬에서 메서드를 호출하는 것이 메시지를 보내는 과정에 해당된다.

책임

객체가 자신이 제공하는 기능으로써 정의된다는 것은, 객체는 어떤 기능에 대한 책임을 진다는 것이다.

객체마다 이러한 책임의 크기가 작을수록 좋다. 즉, 하나의 객체가 제공하는 기능이 적은 것이 좋다.

하나의 객체에 너무 많은 기능이 포함되어서 그 객체의 책임이 커지는 경우에, 그 기능과 관련된 데이터들이 전부 한 객체로 몰리게 된다. 또한 기능들이 그 데이터를 공유하는 방식으로 프로그래밍이 될 수도 있는데, 이는 절차 지향 방식과 다를 것이 없다. 이를 잘 표현한 것이 SRP이다.

의존성

한 객체가 다른 객체에 의존한다는 것은, 특정 객체에서 다른 객체의 메소드를 호출하거나 하는 것을 의미한다. 이러한 의존은, 꼬리에 꼬리를 물며 전파될 수도 있는데, 결국 자기 자신에게까지 영향을 미치게 되는 것을 순환 의존이라고 한다. 이는 DIP 방식으로 해결한다.

캡슐화

객체가 내부적으로 기능을 어떻게 구현하는지를 감추는 것이다. 내부 구현이 변경되더라도, 그 기능을 사용하는 코드는 영향을 받지 않도록 해야 한다. 내부 구현 변경의 유연함을 가져다주는 기법이 캡슐화이다.

OOP에서는 캡슐화를 통해, 어떤 한 곳의 변화가 다른 곳에 미치는 영향을 최소화 한다.

이때 두 개의 규칙이 있다.

1. Tell, Don't ask -> 데이터를 읽으려고 하지 말고 기능을 실행하라는 것이다. 즉 데이터를 읽더라도 메서드를 통해 데이터를 반환하도록 구현하는 것. 데이터를 읽는 것은 데이터를 중심으로 코드를 작성하게 만드는 원인이 된다.

2. 데미테르 법칙

메서드에서 생성한 객체의 메서드만 호출

파라미터로 받은 객체의 메서드만 호출

필드로 참조하는 객체의 메서드만 호출

객체 지향 설계 과정

1. 제공할 기능을 세분화하고, 기능을 적절한 객체에 구현(할당)한다.

2. 필요 데이터를 객체에 추가한다.

3. 그 데이터를 활용하는 기능을 추가한다.

4. 이때 최대한 캡슐화하여 구현한다.

5. 객체 간에 메시지를 어떻게 주고받을지 결정한다.

OOP의 전반적인 장점

OOP 방식으로 코드를 작성하면, 사전에 작성한 코드에 대한 재사용성이 높아지게 된다. 자주 사용되는 로직(기능, 코드)를 라이브러리 혹은 모듈화 해서 사용할 수 있으며, 이것이 사전에 제대로 만들어졌다는 가정하에 신뢰성을 확보할 수 있다.

또한 라이브러리를 각종 예외 상황에 대비하여 잘 만들어두었다면, 컴파일 단계에서 에러를 잡아낼 수 있기 때문에 버그 발생이 줄어든다? -> (이 부분은 피부로 잘 와 닿지 않는다)

아무튼 라이브러리화 해서 사용하면, 그것을 가져다 쓰는 개발자는, 그 라이브러리가 어떻게 작동하는지 내부적인 작동 원리를 모르고도 그 기능을 가져다 쓸 수 있기 때문에, 생산성이 높아진다.

또한 객체 단위로 코드를 나눠서 작성하기 때문에, 유지 보수와 디버깅에 용이하다.

또한 데이터 모델링 시에 객체와 매핑하는 것이 수월하기 때문에, 요구사항을 보다 명확하게 파악하여 프로그래밍할 수 있다. -> (이 부분도 명확히 와 닿지 않음)

OOP의 단점(문제점)

객체 간의 정보 교환이 모두 메시지 교환을 통해 일어나는데, 이는 시스템에 많은 overhead를 준다.

하지만 이 부분은 하드웨어의 발전으로 상당 부분 보완되었다고 한다.

치명적인 단점은, 함수형 프로그래밍 패러다임의 등장 배경을 통해서 알 수 있다. 문제는 객체가 상태를 갖는다는 것이다. 어떤 변수가 존재하고, 그 변수를 통해서 객체가 예측할 수 없는 상태를 갖게 되어 애플리케이션 내부에서 버그를 발생시킨다는 것이다. 이러한 문제로, 최근 함수형 패러다임이 주목받고 있다.

상속을 통한 재사용의 단점

1. 상위 클래스의 변경이 어렵다

많은 클래스가 상속하고 있는 상위 클래스가 변경되면, 하위 클래스에 영향이 퍼지게 된다.

2. 기능 확장을 하면서 클래스의 개수가 증가한다. -> 근데 이걸 피하려면 하나의 클래스 안에 많은 기능을 넣어야 하는데, 충돌하는 거 아닌가?

상속에서 나오는 문제를 해결하는 것이 조립(Composition)

단점: 런타임 구조가 복잡해진다.

상속보다 구현이 어렵다.

구조 / 구현이 복잡하더라도, 변경의 유연함이 상속보다 크기 때문에 먼저 고려된다.

상속을 사용할 때는, 재사용의 관점이 아니라 기능 확장의 관점에서 적용해야 한다.

객체 지향적 설계 원칙

1. SRP(Single Responsibility Principle) : 단일 책임 원칙

  클래스는 단 하나의 책임을 가져야 한다. 또한 클래스를 변경하는 이유는 단 하나의 이유이어야 한다.

2. OCP(Open-Closed Principle) : 개방 - 폐쇄 원칙

  확장에는 열려 있어야 하고, 변경에는 닫혀 있어야 한다.

3. LSP(Liskov Substitution Principle) : 리스코프 치환 원칙

  상위 타입의 객체를 하위 타입의 객체로 치환하더라도, 상위 타입을 사용하는 프로그램은 정상 동작해야 한다.

4. ISP(Interface Segregation Principle) : 인터페이스 분리 원칙

  인터페이스는 그 인터페이스를 사용하는 클라이언트를 기준으로 분리해야 한다.

5. DIP(Dependency Inversion Principle) : 의존 역전 원칙

  고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

참고한 링크

https://asfirstalways.tistory.com/177, https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Development_common_sense#%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

https://www.acmicpc.net/problem/15688

위 문제를 counting sort로 구현해 봤다.

주어지는 수의 절댓값이 1,000,000 이하이기 때문에 배열의 인덱스를 활용할 때 음수 처리를 위해 1000000을 더해준 인덱스에 저장한다.

1의 갯수는 1000001에 저장되는 것이다. 

따라서 출력할 때, 1000000을 빼고 출력해주면 된다.

먼저 최대 공약수 gcd는 재귀로도 구현할 수 있고, 아래와 같이 반목문으로 구현할 수도 있다.

어느쪽이 큰 수인지 지정해줘야 한다.

이후에 큰수를 작은수로 나누고, 나눈 수를 다음에 나눠질 수로 정한다. 나머지는 다음에 나눌 수가 된다.

0으로 나눌 수는 없기 때문에 루프를 빠져 나간다고 외워도 좋고, 나머지가 0이 되었다는 것은 약수를 찾았다는 뜻이니까 루프를 빠져 나간다고 기억해도 좋겠다.

( ll은 long long 타입을 의미한다)

int gcd(ll a, ll b) {
    if (a < b) swap(a, b); //a를 큰수로
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

다음으로, gcd를 활용해서 최소 공배수 lcm을 구하는 과정도 간단하게 구현할 수 있다.

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

최소 공배수의 정의대로, 두 수의 곱을 최대 공약수로 나눠주면 된다.

이를 활용해서, 여러개의 숫자의 최소 공배수를 구하는 과정을 보자.

ll finY = Y[0];
    for (int i = 1; i < Y.size(); i++)
        finY = lcm(finY, Y[i]);

finY에 벡터 Y의 원소들의 최소 공배수가 들어가게 된다. 먼저 벡터 Y의 0번째 값으로 finY를 초기화 한다.

그리고 다음 원소와 lcm을 구해서 저장하고, 또 저장한 lcm과 다음 원소의 lcm을 구하는 과정을 반복해주면 된다.

*기하

그라함 스캔 과정

1. 극값 찾기(y값 작은거, 같다면 x값 작은거)

2. 극값기준 각도순 정렬

3. n번 루프돈다. 스택 크기 2이상 유지하면서 b[i] 0이하이면 pop. 밖에서 push

4. 필요에 맞게 마지막에 처음점 추가(다각형의 선분으로 무언가 할 때)

볼록껍질 최단거리 찾는법

1. 그라함 스캔을 돌려서 볼록 껍질을 형성한다. (마지막에 첫점 추가)

2. n번 루프돈다. j=1부터, j가 1이랑 다를때만 방향벡터 ccw가 양수이면 j++해준다.

j==s.size()-1이 되면 0으로 낮춰준다.

3. 양수가 아니게 되면 i와 j의 거리를 비교해서 최대인지 확인한다

-----------------------------------------------------------------------

*그래프

플로이드 와샬

1. n <= 500일때만 사용하자.

2. 바깥부터 k i j 순으로 루프 돌리고, k거쳐가는거랑 그냥가는거 길이 비교해서

작은 값으로 갱신해준다.

3. 모든 정점사이의 비용 계산에 용이 -> 모든 정점의 연결상태 파악 가능

벨만포드 -> 시작점 존재

0. 초기에 비용 무한대로 초기화. 시작점 비용은 0으로

1. 음수가중치가 존재할 때 사용. 사이클이 없어야한다.

2. 가장 바깥에서 n번 돌린다.(n번째에 갱신이 발생하면 음수사이클 존재)

3. 그 안쪽에서 정점 개수만큼 루프를 돈다.

4. 정점마다 연결된 간선 크기만큼 루프 돌면서, 목적지가 갖고 있는 거리가,

이곳에서 그 정점으로 가는 거리보다 크다면 갱신한다.

5. 이걸 확인할 때, 현재 위치까지의 비용이 무한이 아니어야 한다.

다익스트라

1. 가중치가 양수인 그래프의 최단거리를 젤 수 있다.

2. 방문처리와 우선순위큐가 필요하다(민힙), pii 배열의 인덱스가 시작점, first 비용, sec 목적지 

3. 비용을 무한대로 초기화해주고, 시작점은 0으로 만든다.

4. 시작점을 pq에 넣고, pq가 빌 때까지 실행한다.

5. pq에서 확인하는 지점을 방문처리 한다.(top)

6. 그 지점과 연결된 간선들을 확인할 것인데, 그 연결된 지점이 방문한 지점이면 스킵한다.

7. 거리비교해서 갱신조건 만족할 때만 push한다.

LCA (최소공통조상)

1. DFS로 각 노드의 깊이 계산, 2^0번째 부모 계산

2. 2^k번째 부모는 2^k-1번째 부모의 2^k-1번째 부모임을 이용해서 배열 채우기

3. 비교하고자 하는 노드의 높이를 같게 맞추기(탑다운으로) (뭐가 깊고 뭐가 얕은 노드인지 구분해서)

4. 이때 최대 높이는 (int)floor(log2(n))

5. 높이차이가 2^k보다 커질때마다 깊은점을 k번째 부모로 갱신

6. 높이를 맞춘 이후에, 두 노드가 같다면 그게 답

7. 이번에도 kmax부터 내려오면서 deep과 swall의 부모가 다르다면 둘다 k번째 부모로 갱신

8. 루프를 빠져나오면 0번째 부모가 답