알고리즘 수업 최종 정리

이전 내용

https://gbleem.tistory.com/87

1, 2 주차 알고리즘 정리

 

 

1. 정렬

---

https://gbleem.tistory.com/98

버블, 선택, 삽입 정렬 + 퀵 정렬

 

버블 정렬

• 앞에서부터 시작하여, 자기 자신과 비교하여 자신보다 작은 값이 나온 순간 swap해주는 과정을 통한 정렬
• 한번 순환을 하면, 맨 뒤의 값이 가장 큰 값이 된다.
• O(N^2)

선택 정렬

• 자기 자신과 비교하여, 가장 작은 값과 자신을 swap하는 과정을 통한 정렬
• 한번 순환을 하면, 맨 앞의 값이 가장 작은 값이 된다.
• O(N^2)

삽입 정렬

• 현재 값(i)과 다음 값(i+1)을 비교하여, 만약 i+1값이 
  • 작으면 0~i 값과 비교하면서 i+1에 해당하는 값보다 작은 값 뒤로 이동
  • 크면 i를 하나 증가시켜 반복

퀵정렬

• 피벗을 기준으로 피벗의 왼쪽은 피벗보다 작은 값, 오른쪽은 큰 값으로 나눠 정렬하는 방식 (재귀)
• 최적의 경우 O(NlgN)의 시간 복잡도가 된다. (최악은 O(N^2))

 

 

2. 해시테이블

---

https://gbleem.tistory.com/89

Hash 함수 및 충돌 처리

해시 함수

• 키를 특정한 규칙에 따라 변환하여 배열의 인덱스를 생성하는 함수

해시 충돌

• 해시 테이블을 사용할 때 동일한 해시 값이 여러 개의 키에 대해 발생하는 것
• 해시 충돌 방지
  • 체이닝 : 링크드 리스트 사용
  • 개방 주소법 : 충돌이 발생한 데이터를 새로운 위치에 저장하는 방식
    • 선형 탐사 : 충돌 발생시 일정 간격을 더하면서 빈 공간 찾기
    • 이중 해싱 : 두 개의 해시 함수 사용하여, 충돌 시 다른 간격으로 이동하기

STL

unordered_map<key type, value type>
unordered_set<value type>

 

 

3. 브루트포스

---

모든 가능한 경우의 수를 다 해보는 방식

 

대표적인 방식

• 중첩 반복문 (시간 복잡도가 점점 복잡해짐)
• 비트 마스킹
• STL
• 백트래킹

https://gbleem.tistory.com/119

비트 마스킹

비트마스킹 중요한 부분

• &연산
  • 둘다 참인 경우 참을 리턴
  • 예시) 1&1 -> 1
• << 연산
  • 자릿수를 하나 밀어주는 연산 
  • 예시) 1 << 4 -> 2^4
• 예시
  • i의 j번째 비트가 1인지를 확인하는 코드
  • 모든 경우의 수를 뽑을 때 사용 가능

if(i & (1 << j))

 

 

 

4. 백트래킹

---

https://gbleem.tistory.com/124

백트래킹

https://gbleem.tistory.com/150

백트래킹 2

 

재귀를 사용하여, 모든 경우의 수를 다 해보는 방식

 

템플릿 코드

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

int n, m;
int isused[10];
vector<int> answer;

void Choose(int cur)
{
	//길이가 m 이 되면 종료
	if (cur == m)
	{
		for (const auto& a : answer)
			cout << a << " ";
		cout << "\n";
		return;
	}
    
    //1 ~ n 의 숫자 중 하나를 선택
	for (int i = 1; i <= n; ++i)
	{
		if (!isused[i])
		{
			isused[i] = 1;
			answer.push_back(i);
			Choose(cur + 1);
			isused[i] = 0;
			answer.pop_back();
		}
	}
}

int main()
{
	cin >> n >> m;
	
	Choose(0);	
}

 

 

5. 트리 & 그래프

---

https://gbleem.tistory.com/92

이진 트리

 

5 - 1. 트리

여러개의 노드가 부모-자식 관계로 연결되어 있는 자료구조

 

이진 트리

• 각 노드가 두 개의 자식만 가질 수 있는 트리

이진 탐색 트리

• 탐색에 최적화된 트리 구조
• 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값
• 삽입, 탐색, 삭제가 O(lgN) 시간에 가능

 

5 - 2. 그래프

정점과 간선으로 이루어진 "비선형 데이터" 구조

 

종류

• 가중치 그래프 / 비가중치 그래프
• 방향성 존재 / 방향성 존재하지 않음

구현 방법

• 인접 행렬
  • 구현이 단순하지만, 노드 수가 많으면 메모리 낭비가 생긴다는 단점이 있다.
  • 간선의 존재 여부는 O(1) 
• 인접 리스트
  • 필요한 정보를 저장하기 때문에 메모리 절약 가능

코드 템플릿

 

vector<int> adj[N];

adj[u].push_back(v);
adj[v].push_back(u);

 

 

6. DFS & BFS

---

https://gbleem.tistory.com/117

그래프 (재귀, 비재귀 DFS)

 

DFS 코드 템플릿 (재귀)

void dfs(int cur)
{
	vis[cur] = 1;

	for (int nxt : adj[cur])
	{
		if (vis[nxt])
			continue;
		dfs(nxt);
	}
}

 

BFS 코드 템플릿

void bfs(char cur)
{
	queue<char> q;
	q.push(cur);
	vis[cur] = 1;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (auto nxt : board[cur])
		{
			if(vis[nxt])
            			continue;
			q.push(nxt);			
           		vis[nxt] = 1;
		}
	}
}

 

 

7. 힙 & 다익스트라

---

7 - 1. 힙

priority queue 를 구현할 때 사용되는 자료구조

• 최대 힙 : 루트가 가장 큰 값
• 최소 힙 : 루트가 가장 작은 값

알고리즘

• 버블업 (max heap)
  • 힙에 새로운 데이터가 추가되면, 버블업을 통해 힙을 다시 구성한다.
  • 새로운 요소가 추가되었는데, 만약 부모보다 큰 경우 swap을 진행하면서 위로 올라가는 방식
• 힙 정렬
  • 값이 삽입되거나 삭제되어도 루트가 가장 큰 값이 되도록하는 정렬

STL

• priority_queue
• make_heap
• sort_heap

 

7 - 2. 다익스트라

https://gbleem.tistory.com/134

최단 경로 구하기 (다익스트라, 벨만-포드)

 

가중치가 있는 그래프에서 가장 짧은 경로를 탐색하는 과정에서 최소 비용의 정점을 선택하는 방식

 

구현

• 구현에 있어서 배열을 통해 구현하거나 우선순위 큐를 통해 구현할 수 있다.
• 문제를 풀어본 결과 배열을 통한 다익스트라는 시간초과가 발생하는 경우가 있으므로, 우선순위 큐를 사용하는 방식을 기억하자

템플릿 코드

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

int v, e, st;

vector<pair<int, int>> adj[20005];
const int INF = 1e9 + 10;
int dist[20005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> v >> e >> st;
	fill(dist, dist + v + 1, INF);

	while (e--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w, v });
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	//시작점 처리
	dist[st] = 0;

	//pq에 시작점 넣기
	pq.push({ dist[st], st });
	while (!pq.empty())
	{
		//w가 가장 작은 값을 cur로 설정함
		auto cur = pq.top();
		pq.pop();

		if (dist[cur.second] != cur.first)
			continue;
		for (auto nxt : adj[cur.second])
		{
			//dist에 적혀있는 값보다 새롭게 갱신할 값이 더 크면 continue;
			if (dist[nxt.second] <= dist[cur.second] + nxt.first)
				continue;
			//갱신할 값이 작은 경우 dist 업데이트
			//1 - > 2 인 경우
			//INF > 0 + 3 이므로 dist[2] = 3으로 업데이트
			dist[nxt.second] = dist[cur.second] + nxt.first;
			//업데이트 된 경우는 pq에 값 추가
			pq.push({ dist[nxt.second], nxt.second });
		}
	}
	for (int i = 1; i <= v; ++i)
	{
		if (dist[i] == INF)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}
}

 

 

8. 문자열

---

문자열 뒤집기

#include <algorithm>
...

string str = "abcdefg";
reverse(str.begin(), str.end());
...

 

단어 추출

• 기본적으로 >> 를 통해서 공백을 기준으로 단어를 나눠준다.
• getline을 통해 원하는 단어를 기준으로 단어를 나눠준다.

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

int main() 
{
    string str = "Hello, good night";
    string str2 = "Hello,good,night";
    
    istringstream iss(str);
    istringstream iss2(str2);

    vector<string> words;
    vector<string> words2;
    
    string token;
    
    while(iss >> token)
        words.push_back(token);

    string token2;
    while (getline(iss2, token2, ','))
        words2.push_back(token2);
    
    for(const auto& w: words)
        cout<<w<<"\n";
    
    cout<<"\n\n";
    
    for(const auto& w: words2)
        cout<<w<<"\n";
    
    return 0;
}