백준 풀이 알고리즘 템플릿 - cpp

Intro..

참고

  • 현재 Java로 알고리즘을 풀고 있어서 “알고리즘 템플릿 - JAVA” 가 훨씬 잘 정리되어있다.

  • 아래는 C++ 기준으로 작성되었으며 옛날에 작성했다보니 내용이 많이 부실하다. JAVA 꺼 보는걸 추천


사용할 알고리즘들의 템플릿들을 정리하겠다.

물론 약간의 알고리즘 해석만을 동반하며, 자세한 해석은 아래 링크를 달아두겠다.

  • 참고 링크 : 바킹독, 구글링 등등
  • 코드들만 기록할랬는데,,, 정리하다보니 해석을 좀 많이했네,,

공부하면서 바킹독님의 유튜브, 블로그의 도움을 많이 받았습니다!!



문자열 - string

주의사항

  • c++에서 string은 문자열을 이어붙일때 잘못 사용하면 O(N^2) 복잡도를 발생시킬 수 있다.
    • s+'a' 라는 새 문자열 객체를 만든후 s에 더하기 때문에 s+'a' 만큼 매번 추가로 길이가 필요하기 때문이다.
  • 따라서 반드시 아래 방식으로 사용해야한다 - O(N)
    • 'a' 만 생성되어서 s 에 더하기 때문에 a 만큼 길이만 추가로 필요하기 때문에 빠르다.
    • 물론 char[]을 써도 되지만 string이 매우 편리
  • 문자열이라기보단 memset, fill 메소드 설명
    • 배열이나 이런 숫자를 하나로 초기화하는 로직 작성은 하다보면 귀찮다.
    • 이를 쉽게 해주는게 memset 함수와 fill 함수이며 fill 함수는 algorithm 선언이 필요하다.
    • fill 함수를 사용하면 된다. memset은 0, -1 초기화에만 주로 사용한다. (정확히는 구글링참고)
int main() {
    string s;
    for(int i = 0 ; i<100000; i++) {
        // 1. O(N^2) 복잡도 코드
        s=s+'a';
        s=s+"ab";
        // 2. O(N) 복잡도 코드
        s+='a';
        s+="ab";
    }
}


아래 문법들은 기본적으로 암기

int main() {
	string s = "hello";
	s += " BKD!"; // hello BKD!
	cout << s.size() << '\n'; // 10
	cout << s.substr(2, 3) << '\n'; // llo
	cout << s[1] << '\n'; // e
	s.replace(6, 4, "guys"); // hello guys
	cout << s << '\n';
	int it = s.find("guys"); // 6
	s.replace(it, 4, "everyone"); // hello everyone
	cout << s << '\n';
	s.erase(7, 6); // hello ee
	cout << s << '\n';
	s[6] = 'm'; // hello me
	cout << s << '\n';
	s.insert(0, "say "); // say hello me
	cout << s << '\n';
	if (s.find("to") == string::npos) // string::npos == -1
		cout << "'to' is not in string 's'\n";
}


c++ string에서 split 함수는 지원하지 않으므로 직 접 구 현

// vector, string 등등은 반드시 주소로 넘겨야 값 복사하는 복잡도 안생김
vector<string> split(string& inStr, string& sep) {
	vector<string> ret;
	int cur = 0;
	while (cur < inStr.size()) {
		int nxt = inStr.find(sep, cur); // cur 부터 검색 시작
		if (nxt == -1) nxt = inStr.size(); // end
		if (nxt - cur > 0) // 없어도 잘 동작하지만, substr로 나눌 문자열이 길이가 0이면 안되긴 하니까
			ret.push_back(inStr.substr(cur, nxt - cur));
		cur = nxt + sep.size(); // sep(구분자)만큼 추가로 이동
	}
	return ret;
}



BFS, DFS

BFS(넢이우선검색), DFS(깊이우선검색)은 정말 단골 문제들이다.

  • BFS를 우선으로 사용하며, DFS는 DFS로만 풀리는 문제에 사용하면 된다.
  • BFS는 큐 를 활용하고, DFS는 스택 또는 재귀(필자는 주로 재귀)를 활용한다.
  • 주의할점은 BFS에서 큐에 집어넣는 시점에 방문기록을 남긴다.


BFS 기본형태 4방향

// 입력이 좌상을 0,0 으로 좌표계 형성하게끔 들어왔다 가정
int dx[4] = { 0, 1, 0, -1 }; // 행 : 우,하,좌,상
int dy[4] = { 1, 0, -1, 0 }; // 열 : 우,하,좌,상
void bfs(int x, int y) {
	queue<pair<int, int>> qu;
	visited[x][y] = true; // 방문 표시 (x,y는 처음 BFS 순회할 좌표)
	qu.push({ x, y });

	while (!qu.empty()) {
		int cx = qu.front().first;
		int cy = qu.front().second;
		qu.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx<0 || ny<0 || nx>N-1 || ny > M-1) continue; // 범위 내 체크
			if (visited[nx][ny]) continue; // 방문 여부 체크
			if (inArr[nx][ny] == 1) {
				// 땅이 있는 경우(=1) 스택에 추가한다.
				visited[nx][ny] = true; // 방문 표시
				qu.push({ nx,ny });
			}
		}
	}
}


BFS 시작점이 여러 개

  • BFS를 동시에 동작하듯이 해야하는 경우에 해당된다.
  • 같이 시작할 시작점들을 while문 돌리기전 큐에 전부 삽입후 평소처럼 BFS를 진행한다.
  • 큐의 특성상 들어온 순서대로 진행할거기 때문에 가능한 것이다.


BFS 거리측정 + 시작점이 두 종류

  • BOJ 4179번 : 불! 문제를 예시로 들겠다.
    • 위처럼 시작점 여러개를 적용을 하는 부분이 초기에 진행된다.
    • 그리고 두 종류로 BFS를 따로 동작하는 형식이다.
// BOJ 4179번 : 불!
void bfs() {
	queue<pair<int, int>> qu1; // J (지훈)
	queue<pair<int, int>> qu2; // F (불)
	// J, F 위치 찾아서 push
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (inArr[i][j] == 'J') {
				qu1.push({ i,j });
				dist1[i][j] = 0; // 지훈이 거리 기록(분)
			}
			else if (inArr[i][j] == 'F') {
				qu2.push({ i,j });
				dist2[i][j] = 0; // 불 거리 기록(분)
			}
		}
	}

	// F를 BFS
	while (!qu2.empty()) {
		int cx = qu2.front().first;
		int cy = qu2.front().second;
		qu2.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx<0 || ny<0 || nx>N - 1 || ny > M - 1) continue; // 범위 내 체크
			if (inArr[nx][ny] == '#') continue; // 벽 체크	
			if (dist2[nx][ny] == -1) {
				dist2[nx][ny] = dist2[cx][cy] + 1; // 거리(분) 기록
				qu2.push({ nx,ny });
			}
		}
	}

	// 불이 언제 어디서 퍼지는지 다 알고난 후 J를 BFS 한다.
	// 이때 핵심은 J가 범위를 벗어난 경우 탈출 성공이라 했었다.
	// => 불이 퍼지기 전에 탈출인지만 마지막에 체크하면 됨.
	while (!qu1.empty()) {
		int cx = qu1.front().first;
		int cy = qu1.front().second;
		qu1.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			// 범위 내 체크
			if (nx<0 || ny<0 || nx>N - 1 || ny > M - 1) {
				// 불보다 먼저인지 체크
				// dist2[cx][cy] == -1 의 의미는 F(불)이 사방에 갇혀서 못나온 경우다.
				if (dist1[cx][cy] < dist2[cx][cy] || dist2[cx][cy] == -1) {
					cout << dist1[cx][cy]+1;
					return;
				}
			}
			if (inArr[nx][ny] == '#') continue; // 벽 체크	
			if (dist1[nx][ny] == -1) {
				dist1[nx][ny] = dist1[cx][cy] + 1; // 거리(분) 기록
				qu1.push({ nx,ny });
			}
		}
	}
	cout << "IMPOSSIBLE";
}


1차원에서의 BFS (즉, 4방향이 아니라)

  • dx,dy 배열을 통해서 for(int i=0; i<4; i++)에서 nx, ny 를 구하는 것이,
  • 4방향이 아니라 필요에따라 for (auto nx : inArr[cx]) 형태로 바뀐다던지 이런식으로도 응용한다는 것이다.


DFS : 큐->스택 변경시 동일하게 동작하며, 아래 그래프 쪽 파트에서 재귀 방식도 참고(백트래킹에서 많이 사용)



재귀(Recursion)

절차지향적 사고 -> 귀납적 사고 가 반드시 필요!!!

절차적으로 이해하지 마라!! 귀납적으로 그냥 이렇게 되겠구나라고 생각만 하라!! 도미노를 생각!!

  • 수학적 귀납법
    • 1번 도미노가 쓰러진다.
      k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.
      • 참(true) : 1번 도미노가 쓰러진다, k번 도미노가 쓰러지면(가정)
      • 두 문장이 참이므로 k+1번 도미노.. 또한 귀납적으로 참
    • 예시1) 아래 코드의 예시
      • func1(1)이 1을 출력한다.
        func1(k)가 k,k-1,k-2…1을 출력하면 func1(k+1)은 k+1,k,k-1,k-2…1을 출력한다.
    • 예시2) 하노이 탑 이동 순서(n개 원판을 기둥 1 -> 기둥 3 으로 이동)
      • n-1개의 원판을 1->2 이동
        n번 원판을 1->3 이동
        n-1개의 원판을 2->3 이동
        => 규칙이 큰 원판 위에 작은 원판을 두는것이기 때문에 반드시 n-1개 원판이 기둥 2에 있고,
        n번 원판이 기둥 1-> 기둥 3 으로 이동하는 경우의 존재는 생각해보면 자명하다.
      • 원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.
        원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다.
  • 재귀 함수의 조건
    • Base condition : 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함
    • 모든 입력은 Base condition으로 수렴
  • 재귀에 대한 정보
    • 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함
      • 모든 재귀 함수는 for문으로 만들 수 있음
      • 재귀는 for문 보다 메모리/시간에서 손해를 봄(함수 호출량 때문)
    • 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음(계산 중복 때문)
      • 예 : 피보나치 수열 => 해결법(DP로 중복 계산 재사용을 통해서 해결)
    • 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨
      • 100000 정도 호출했을 때 정상동작 하지 않으면 구글 검색을 통해 스택 메모리 제한을 해제할 것


재귀로 로직 작성 순서

​ 1. 함수의 정의

​ 2. base condition

​ 3. 재귀 식

void func1(int n) {
    if(n==0) return; // base condition
    cout << n << ' ';
    func1(n-1);
}



백트래킹(Backtracking)

상태 공간트리 를 그려가면서 문제를 이해하고, 재귀 형태로 풀어나가면 된다.

깊이우선검색(=DFS)을 기반으로 검색을 진행하며, 각 마디가 유망하지 않으면 그 마디의 부모 마디로 돌아가서 다시 검색을 계속하는 방식이다.

  • 참고 : 백트래킹 은 깊이우선검색(DFS)을 기반으로 하지만, 분기한정법 은 여러 검색 방법들을 지원하는 차이가 있다.


N과 M(1) - 대표적인 템플릿

// N과 M(1) : 1부터 N까지 자연수 중에서 `중복 없이(=visited 활용)` M개를 고른 수열
// 즉, (1 2) (1 3) 은 가능하지만 (1 1)은 불가
#include <bits/stdc++.h>
using namespace std;

int n,m;
int outArr[10];
bool visited[10];

void func(int depth) {
    if(depth == m) { // base condition
        for(int i = 0 ; i<depth; i++) cout << outArr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i<=n; i++) {
        if(!visited[i]) {
            outArr[depth] = i;
            visited[i] = true;
            func(depth+1); // 재귀
            visited[i] = false; // backtracking
        }
    }
}


N과 M 시리즈 - dfs 방식 백트래킹 사고력 확장

// 참고 : 1~N 순서대로 자연수가 들어왔기 때문에 수열을 구하면 사전순(오름차순)으로 출력
// 그러나, 랜덤 값이 들어온 경우엔 수열 구하기전에 sort작업이 필요

// `i > preValue`로 구하는 값 오름차순 (즉, 현재값 > 이전값)
for (int i = 1; i <= N; i++) {
    if (!visited[i] && i > preValue) { // 만약 비내림차순은? `i>=preValue`
        visited[i] = true;
        outArr[depth] = i;
        dfs(depth + 1, i);
        visited[i] = false; // backtracking
    }
}

// 1부터 N까지 자연수 중에서 `중복 허용(=visited 활용X)` M개를 고른 수열
for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
        //visited[i] = true;
        outArr[depth] = i;
        dfs(depth + 1);
        //visited[i] = false; // backtracking
    }
}

// 애초에 입력이 1 2 3 4 가 아닌 1 1 2 3 이런식으로 중복으로 들어올 경우 처리방법 소개
// `tempNum != inArr[i]` 이 핵심
int tempNum = 0; // 이전값 기록해둬서 중복 수열 생성되지 않도록 하기 위함
for (int i = 1; i <= N; i++) {
    if (!visited[i] && tempNum != inArr[i]) {
        tempNum = inArr[i];
        visited[i] = true;
        outArr[depth] = inArr[i];
        dfs(depth + 1, inArr[i]);
        visited[i] = false;
    }
}

// 마지막으로 시간초과를 해결하는 TIP => 아래 동작만 필요한 경우들에 사용!!
for (int i = index; i < chicken.size(); i++) { // 반드시 index부터 시작해야 시간초과 안전
    p = chicken[i];
    if (visited[p.first][p.second]) continue;
    visited[p.first][p.second] = true;
    outArr[depth] = i; // 선택된 치킨집 index 기록
    dfs(depth + 1, i); 
    visited[p.first][p.second] = false; // backtracking
}


부분수열의 합 - 응용(사고력 확장)

// 이 문제도 위 코드와 같은 형태로 해결할 수 있지만, 좀 더 간단하게 해결할 수도 있다.
// 위 코드의 경우 하나의 형태로만 재귀를 한것이다.
// 하지만, 이 문제를 상태 트리 그려보면 값을 더한경우 안더한경우로 나눠 볼 수 있다.
// 즉, 2개 형태로 재귀를 할 수 있고 훨씬 코드도 간결해진다.
void func(int depth, int sum) {
	if (depth == N) { // base condition
		if (sum == S) result++;
		return;
	}
	func(depth + 1, sum); // 안더함
	func(depth + 1, sum + inArr[depth]); // 더함
}


STL next_permutation - 수열과 조합에 유용(N과 M같은 문제들)

  • 배열 범위는 sort 처럼 end쪽 주소는 배열 사이즈 크기의 주소

image-20230429035204359

// next_permutation : 순열을 나타낸다. do-while 형태로 사용
// 조합 구하는 예시로 5C2를 예로 들면,
// 만약 치킨집이 5개이고 M이 2라고 하면 brute는 {0, 0, 1, 1, 1} 로 0이 치킨집 2개 선택 의미
void permutation() {
	// 조합 구하기 위한 setting
    // M=2라면, {0,0,1,1,1...}
	vector<int> vc(chicken.size(), 1);
	int brute[55];
	for (int i = 0; i < chicken.size(); i++) brute[i] = 1; // 전체 1로 세팅후
	for (int i = 0; i < M; i++) brute[i] = 0; // M개만큼 0으로 세팅
	int mn = 10000000;
	do {
		int dist = 0;
		for (auto h : home) {
			int tmp = 10000000;
			for (int i = 0; i < chicken.size(); i++) {
				if (brute[i] == 0) // 선택된 경우
					tmp = min(tmp, abs(chicken[i].first - h.first) + abs(chicken[i].second - h.second));
			}
			dist += tmp;
		}
		mn = min(mn, dist);
	} while (next_permutation(&brute[0], &brute[chicken.size()]));
	result = mn;
}



Branch-and-Bound(분기한정법)

이건 이런게 있다란 개념만 이해해두자. 분기한정법-개념

  • 분기한정법 : Backtracking + 다른 탐색들(DFS,BFS,우선순위큐 등)

    • Bound : 마디가 유망한지 여부를 결정하기 위해서 한계치(bound) 계산

    • So far the best : 현재까지 찾은 최적의 답

  • 최적화 문제의 SST 비교

    • 최적화 문제의 SST 비교 최소화 문제(예: TSP)
      • 트리 깊어질수록 BOUND값이 절대 작아질 수 없음(Low Bound를 구함)
    • 최적화 문제의 SST 비교 최대화 문제(예: 0-1냅색)
      • 트리 깊어질수록 BOUND값이 절대 커질 수 없음(Upper Bound를 구함)



시뮬레이션(구현)

존나 풀어라… 단, 구현인 만큼 코드 작성 전 꼭 도식화를 진행

  • 존나 풀어라 : 구현(실버급 인기 순)
  • 자주 나오는 로직은 그냥 외우자
    • 예로 2차원 배열 회전 로직은 B[x][y]=A[N-1-y][x] 
// 90도 회전 함수
void rotate() {
    // 1. tmp에 복제
	int tmp[12][12]; 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			tmp[i][j] = inArr[i][j];
		}
	}
	// 2. 배열요소 swap
	for (int i = 0; i < N; i++) { 
		for (int j = 0; j < M; j++) {
			inArr[i][j] = tmp[N-1-j][i]; // B[x][y]=A[N-1-y][x]
		}
	}
    // 3. 배열크기 swap
    swap(N,M);
}



정렬(Sort)

STL sort 이용 - O(NlogN)

  • 응용을 예시 들면, 정렬 때 같은 수는 인접하는 성질을 이용해 중복 원소 제거도 가능
    • 정렬은 아니지만 숫자를 바로 index와 매칭해서 받는 로직도 잘 기억
  • 주의사항 : 혹시나 string 같은 클래스 객체 전달시 반드시 reference 를 사용
#include<algorithm>
#include<vector>
vector<int> inArr[10000];
for i..N, order[x]=i; ... 
등등 선언을 가정

// 비교하는 함수를 따로 커스텀!!!
bool comp(const int a, int b) { // 당연히 const 안써도 됨
	return order[a] < order[b]; // inArr값을 order배열로 비교하게끔 커스텀
} // a가 b의 앞에 와야할 때 true, 그렇지 않을 때 false

sort(inArr[i].begin(), inArr[i].end(), comp); // end()는 마지막 index + 1
sort(&inArr[i][0], &inArr[i].back()+1, comp); // back()은 마지막 index



다이나믹 프로그래밍(DP)

DP란 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

참고로 DP는 정말 대표하는 문제들이 많고 유형들도 가지각색이라서 많은 경험이 필요


DP를 푸는 과정 - 테이블 잡고 식 찾는 연습이 매우매우 중요

​ 1. 테이블 정의하기

​ 2. 점화식 찾기

​ 3. 초기값 정하기


EX) 1로 만들기 BOJ : 1463번

  • 테이블 정의하기
    • D[i]는 i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
  • 점화식 찾기
    • D[12]는 ??
      3로 나누면 (D[12] = D[4] + 1)
      2로 나누면 (D[12] = D[6] + 1)
      1을 빼면 (D[12] = D[11] + 1)
      => D[12] = min(D[4]+1, D[6]+1, D[11]+1)
    • D[k] = ?
      => D[k] = min(D[k/3]+1, D[k/2]+1, D[k-1]+1)
  • 초기값 정의하기
    • D[1] = 0
int d[1000005];
int n;
int main() {
    cin >> n;
    d[1] = 0;
    for(int i = 2; i<=n; i++) {
        d[i] = d[i-1]+1;
        if(i%2 == 0) d[i] = min(d[i], d[i/2]+1);
        if(i%3 == 0) d[i] = min(d[i], d[i/3]+1);
    }
    cout << d[n];
}



그리디(Greedy)

그리디란 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘

구현자체는 굉장히 간단해서 따로 정해진 코드 탬플릿은 X

단, 코테에서 추천 전략은 문제가 100% 그리디 풀이란게 확신하면 짜서 제출 및 틀리면 빠르게 손절
100% 확신이 없으면, 일단 넘어가고 마지막에 남은 시간에 코딩 시작



수학(Math)

자세한 개념은 반드시 알고리즘 기초1 - 수학, 바킹독 - 수학 게시물을 함께 참고


1. 소수

개선시킨 소수판정과 소인수분해는 모두 O(√n)

1부터 n까지의 수 중에서 소수 목록을 구하는건 에라토스테네스의 체를 사용

  • 소수 판정법 - O(√n)
    • 합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다.
      • EX) N=18 : 2<=√18, N=25 : 5<=√25, N=21 : 3<=√21
// √N 이하까지만 확인해도 소수 판별이 가능하므로 복잡도 N -> √N 개선
bool isPrime(int n) {
    if(n == 1) return 0;
    for(int i = 2; i*i<=n; i++) { // √N 이하까지 돈다.
        if(n%i == 0) return 0;
    }
    return 1;
}


  • 소수 목록 - 에라토스테네스의 체
    • 소수는 자신보다 작은 수들의 배수값과 동일한게 있으면 안되는 특징을 이용
    • 예로 2의 경우??
      • 처음 prime[2]는 소수로 그대로 있고, prime[4, 6, 8...] 배수들은 소수가 아닌것으로 걸러지는 형태이다.
// 에라토스테네스의 체
// prime배열 의미 : false면 소수, true면 소수아님 => 초기값 false로 초기화(전역배열)

p = 2; 
while (p * p <= N) {
    if (prime[p] == false) {
        for (i = p * p; i < N + 1; i += p) { // i+=p 는 p의 배수들 걸러내려고
            prime[i] = true;
        }
    }
    p++;
}


  • 소인수분해
    • 소인수분해 : 자연수를 소인수(약수들 중 소수)들의 곱으로 표현하는 것
      • EX) 60 = 2 x 2 x 3 x 5
    • 방법1) N 이하의 모든 소수를 에라토스테네스의 체로 다 찾은 다음에 그 소수들로 N을 나누어보는 방법
    • 방법2) 하지만, 이보다 더 괜찮은 방법이 존재(루트N 복잡도)
      • i를 2,3,4,5… 올라가면서 N을 나누어 떨어질때마다 소인수 목록에 기록하는 방법
for(int i = 2; i*i<=n; i++) { // √N 이하까지 돈다.
    while(n%i == 0) {
        cout << i << '\n'; // 구한 소인수
        n/=i; // n이 1이 될때까지 갱신
    }
    if(n!=1) cout << n; // 마지막에 n이 1이 안될경우도 있는데, 그땐 n으로 나누면 1이 됨
}
  • 참고) 팩토리얼 수에서 특정 수의 개수 구할때 유용한 특징 : 10!의 경우 5의 개수를 구하기 위해 5를 10으로 나누면, 1~10 곱한 값 사이의 5가 나온 개수가 출력된다.


2. 최대공약수, 최소공배수(GCD, LCM)

  • 최대 공약수(GCD), 최소 공배수(LCM) - 유클리드 호제법
    • 유클리드 호제법 : 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(단, a> b), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
      • (a, b) = (b, r)
      • EX) 10 20 : (10, 20) = (20, 10) = (10, 0) = 10
// 최대공약수 -> (a, b) = (b, r)
int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}
// 최소공배수 -> A X B = GCD(A,B) X LCM(A,B)
int lcm(int a, int b) {
    return a / gcd(a,b) * b; // overflow 방지 위해 나누기 먼저(곱셈이라 가능)
}


3. 연립합동방정식

아래 그림에서 조건에 만족한 학생 수를 구하기 위해 0~29 학생 수 때의 상황을 테이블로 나타냈고,
정답은 27명임을 알 수 있으며 이런 문제를 연립합동방정식 이다.

image-20230430191943232


다만, 이렇게 0~29 명 때를 전부 찾아보는게 아닌 5개만 확인하면 되는 효율적인 방법을 소개한다.

  • N%6==3 인 수들이 필요하고, 이는 처음 3부터 시작해서 +6인 3,9,15,21,27이다.
  • 이 5개의 수들 중에서 N%5==2 를 찾기만 하면 된다.

image-20230430192200486

int chk() {
    for(int i = 3; i<30; i+=6) { // N%6==3 인 경우들만 접근
        if(i % 5 == 2) return i;
    }
    return -1;
}


4. 이항계수(조합)

방법1) 조합의 공식 : nCr = n!/[(n-r)!r!] 을 이용하는 방법

방법2) 조합 성질 : nCk = (n-1)C(k-1) + (n-1)Ck 를 이용해서 DP로 구하는 방법(추천!!)

  • 점화식 : d[i][j] = d[i-1][j-1] + d[i-1][j]


5. A진법 to B진법의 변환(관계)

필자는 이것을 A진법 -> 10진법 -> B진법 의 변화로 해결하고 있다.

백준11576 풀이 게시글 참고!!

  • A진법 -> 10진법
    • 예로 2진법이라면??
      • 먼저, 10진수 값이 10 이였다면 이를 2진법으로 표현 했을때는 1010이다.
        • 1010 의 일의 자리 수를 10진수로 표현하면 0*2^0 = 0 이다.
        • 1010 의 십의 자리 수를 10진수로 표현하면 1*2^1 = 2 이다.
        • 1010 의 백의 자리 수를 10진수로 표현하면 0*2^2 = 0 이다.
        • 1010 의 천의 자리 수를 10진수로 표현하면 1*2^3 = 8 이다.
      • 마지막으로 1010 을 10진수로 표현한다면??
        • 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3 = 0 + 2 + 0 + 8 = 10
  • 10진법 -> B진법
    • 10진수를 기수 B로 계속 나누어서 나머지 값을 거꾸로 출력하는 방식이다.
    • 그림으로 참고(추천 URL) : 10진수 A,B 진법 관계



이분탐색

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

  • STL binary_search 함수를 활용 : 찾는 수가 등장했는지 안했는지를 알려줌(오름차순에 사용)
  • 분할정복처럼 st, en, mid 인덱스 활용하며 mid=(st+en)/2 가 기본
    • 반드시 st,en을 1차이 두게 0,1로 가정하던지 해서 무한루프에 빠지는지 체크도 중요!!
      • 무한루프에 빠지게 되는경우 mid=(left+right+1)/2 사용을 권장


이분탐색 자료구조 binary_search 기본 사용법

#include<algorithm>
int main() {
    for(int i = 0 ; i<n;i++) cin >> a[i]; // 배열에 수들을 입력받는다
    cin>>t; // 찾을 target 수를 입력받는다
    cout<<binary_search(a,a+n,t)<<'\n'; // t/f를 반환해줌
}


이분탐색으로 target의 왼쪽, 오른쪽 위치 구하는 함수 lower_bound, upper_bound

// a배열 = {1,2,2,2,3} 인 경우, t=2 가정
cout << upper_bound(a,a+n,t) - lower_bound(a,a+n,t) << '\n'; // 중복수의 개수 : 3
cout << upper_bound(a, a + n, t) - a << '\n'; // index 출력 : 4
cout << lower_bound(a, a + n, t) - a << '\n'; // index 출력 : 1


1. 좌표압축

나중에 문제를 풀다보면 입력값의 범위는 1에서 10^9 정도로 굉장히 큰데 그거를 배열 인덱스처럼 쓰고 싶을 수 있습니다.
그러면 뭔가 크기 순으로 번호를 0번부터 매기고 싶다는 생각이 들텐데 이런 일을 하는게 좌표압축입니다.

  • 좌표압축 방법 : 정렬 -> 중복 제거 -> 이후 이분탐색 수행
    • STL unique 함수는 중복제거하고 원소들을 앞으로 모아준다, return은 시작주소를 반환
sort(uni.begin(), uni.end()); // 정렬
uni.erase(unique(uni.begin(), uni.end()), uni.end()); // 중복 제거
for(int i = 0 ; i<n;i++) // 이분탐색
    cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';


좌표압축 다른 예

// 문자 -> index로 변환 함수(좌표압축 함수)
int getID(char c) { 
	if (c <= 'Z')
		return c - 'A';
	return c - 'a' + 26; // 26은 A~Z 이후에 자리를 두기 위함
} // 아스키코드는 A가 a보다 작음



투 포인터

투 포인터는 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘

  • 이분 탐색으로 투 포인터 문제를 풀던가, 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우가 많다.
  • 예시로 수 고르기 를 풀어본다.
    • 아래 코드는 2개의 포인터를 적절히 조건에 맞게 움직여서 해를 구하는 모습이다.
for(int st = 0 ; st<n; st++){ // 총 N복잡도
    while(en < n && a[en] - a[st] < m) en++; // 총 N복잡도
    if(en == n) break;
    mn = min(mn, a[en] - a[st]);
} // N+N=2N => O(N) 복잡도
cout << mn;



해시

해시 함수 : 임의 길이의 데이터를 고정될 길이의 데이터로 대응시키는 함수 (5135:Kim,…)

해시 테이블 : 아래 그림

  • 같은 키가 삽입될 수 있어서 충돌은 어쩔 수 없다.
  • 대표적인 충돌회피 방법은 Chaining, Open Addressing 이 존재한다.
    • Chaining : 연결리스트로 회피
    • Open Addressing : Probing 방식으로 데이터 저장해서 회피
      • Linear Probing : 충돌 발생 시 오른쪽으로 1칸씩 이동
        • 단점 : Clustering(군집화) 발생
      • Quadratic Probing : 충돌 발생 시 오른쪽으로 1,3,5,… 칸씩 이동
        • 단점 : 약하긴 하지만 Clustering(군집화) 발생
      • Double Hashing : 충돌 발생 시 이동 칸의 수를 새로운 해시함수로 계산하는 방식
        • 단점 : 적중률이 낮아짐

image-20230430212318397


해시 자료구조로 이루어진 STL

  • unordered_set, unordered_multiset, unordered_map 이며, multiset의 경우 중복을 허용
    • Python 의 set, dict 자료구조랑 유사
    • 사실 unordered_multimap 도 존재하는데 사용할 일이 거의 없음
  • 이름이 비슷한 BST 자료구조인 set, multiset, map 과 구분할 것
    • 근데 해시보단 set, map 들 사용을 추천
    • 왜?? insert, erase, find update 동작이 해시는 O(1), RBT는 O(logN) 이지만,
    • RBT는 원소가 크기 순으로 정렬되어 있다는 큰 장점이 있다. 즉, lower_bound같은걸 logN에 바로 구할 수 있다.
#include <unordered_set>
#include <unordered_map>
// unordered_set
void unordered_set_example() {
	unordered_set<int> s;
	s.insert(-10); s.insert(100); s.insert(15); // {-10, 100, 15}
	s.insert(-10); // {-10, 100, 15}
	cout << s.erase(100) << '\n'; // {-10, 15}, 출력:1
	cout << s.erase(20) << '\n'; // {-10, 15}, 출력:0
	if (s.find(15) != s.end()) cout << "15 in s\n";
	else cout << "15 not in s\n";
	cout << s.size() << '\n'; // 2
	cout << s.count(50) << '\n'; // 0 => 수가 몇개있는지 카운트
	for (auto e : s) cout << e << ' ';
}

// unordered_multiset
// 중복 허용이며 erase를 그냥쓰면 전체 삭제 되기 때문에 조심
void unordered_multiset_example() {
	unordered_multiset<int> ms;
	ms.insert(-10); ms.insert(100); ms.insert(15); // {-10, 100, 15}
	ms.insert(-10); ms.insert(15); // {-10, -10, 100, 15, 15}
	cout << ms.size() << '\n'; // 5
	for (auto e : ms) cout << e << ' ';
	cout << '\n';
	cout << ms.erase(15) << '\n'; // {-10, -10, 100}, 출력:2 => 삭제 개수
	ms.erase(ms.find(-10)); // {-10, 100} => 1개는 이렇게 삭제해줘야 함
	ms.insert(100);
	cout << ms.count(100) << '\n'; // 2 => 수가 몇개있는지 카운트
}

// unordered_map
// python의 dict처럼 쓰면 됨
void unordered_map_example() {
	unordered_map<string, int> m;
	m["hi"] = 123;
	m["bkd"] = 1000;
	m["gogo"] = 165; // {"hi", 123}, {"bkd", 1000}, {"gogo", 165}
	cout << m.size() << '\n'; // 3
	m["hi"] = -7; // {"hi", -7}, {"bkd", 1000}, {"gogo", 165}
	if (m.find("hi") != m.end()) cout << "hi in m\n";
	else cout << "hi not in m\n";
	m.erase("bkd"); // {"hi", -7}, {"gogo", 165}
	for (auto e : m)
		cout << e.first << ' ' << e.second << '\n';
}



이진 검색, 레드-블랙 트리(BST, RBT)

c++에서 STL에는 이진 검색 트리 + 자가 균형을 이루는 RBT 자료 구조로 정의되어서 제공한다.

참고로 BST를 구현을 해야할 것 같을때는 배열로는 구현X, 차라리 class로 구현하자.

해시에서 비교를 했기 때문에 자세한 설명은 생략

  • prev, next나 lower_bound 이런게 필요할 때 유용
  • 개념 정리 게시글 참고 : 고급트리 개념 
#include<set>
#include<map>
void set_example() {
	set<int> s;
	s.insert(-10); s.insert(100); s.insert(15); // {-10, 15, 100}
	s.insert(-10); // {-10, 15, 100}
	cout << s.erase(100) << '\n'; // {-10, 15}, 1
	cout << s.erase(20) << '\n'; // {-10, 15}, 0
	if (s.find(15) != s.end()) cout << "15 in s\n";
	else cout << "15 not in s\n";
	cout << s.size() << '\n'; // 2
	cout << s.count(50) << '\n'; // 0
	for (auto e : s) cout << e << ' ';
	cout << '\n';
	s.insert(-40); // {-40, -10, 15}
	set<int>::iterator it1 = s.begin(); // {-40(<-it1), -10, 15}
	it1++; // {-40, -10(<-it1), 15}
	auto it2 = prev(it1); // {-40(<-it2), -10, 15}
	it2 = next(it1); // {-40, -10, 15(<-it2)}
	advance(it2, -2); // {-40(<-it2), -10, 15}
	auto it3 = s.lower_bound(-20); // {-40, -10(<-it3), 15}
	auto it4 = s.find(15); // {-40, -10, 15(<-it4)}
	cout << *it1 << '\n'; // -10
	cout << *it2 << '\n'; // -40
	cout << *it3 << '\n'; // -10
	cout << *it4 << '\n'; // 15
}

void multiset_example() {
	multiset<int> ms;
	// {-10, 15, 100}
	ms.insert(-10); ms.insert(100); ms.insert(15); // {-10, -10, 15, 15, 100}  
	ms.insert(-10); ms.insert(15);
	cout << ms.size() << '\n'; // 5
	for (auto e : ms) cout << e << ' ';
	cout << '\n';
	cout << ms.erase(15) << '\n'; // {-10, -10, 100}, 2
	ms.erase(ms.find(-10)); // {-10, 100}
	ms.insert(100); // {-10, 100, 100}
	cout << ms.count(100) << '\n'; // 2
	auto it1 = ms.begin(); // {-10(<-it1), 100, 100}
	auto it2 = ms.upper_bound(100); // {-10, 100, 100} (<-it2)
	auto it3 = ms.find(100); // {-10, 100(<-it3), 100}
	cout << *it1 << '\n'; // -10
	cout << (it2 == ms.end()) << '\n'; // 1
	cout << *it3 << '\n'; // 100
}

void map_example() {
	map<string, int> m;
	m["hi"] = 123;
	m["bkd"] = 1000;
	m["gogo"] = 165; // ("bkd", 1000), ("gogo", 165), ("hi", 123)
	cout << m.size() << '\n'; // 3
	m["hi"] = -7;  // ("bkd", 1000), ("gogo", 165), ("hi", -7)
	if (m.find("hi") != m.end()) cout << "hi in m\n";
	else cout << "hi not in m\n";
	m.erase("bkd"); // ("gogo", 165), ("hi", 123)
	for (auto e : m)
		cout << e.first << ' ' << e.second << '\n';
	auto it1 = m.find("gogo");
	cout << it1->first << ' ' << it1->second << '\n'; // gogo 165
}



우선순위 큐

우선순위 큐는 pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐이다.

힙(최대 힙, 최소 힙) 자료구조를 사용해서 만든 우선순위 큐

  • 원소 추가 - O(logN)
  • 우선순위 높은 원소 확인 - O(1)
  • 우선순위 높은 원소 제거 - O(logN)
  • 배열 자료구조 + 우선순위 큐의 경우 => 순서대로 O(1), O(N), O(N)
  • set 도 최소값과 최대값을 빼고, 원소 추가하고 다 가능하고 복잡도도 심지어 동일하다.
    • 그래도 굳이 priority_queue 를 사용하는 이유는 같은 O(logN)이라고 해도 set 보다 빠르고, 공간도 적게 차지한다.
    • 따라서 priority_queue 의 기능만 딱 필요할 경우엔 set이 아닌 priority_queue 를 사용해주자!


힙을 배열로 나타낼 때

  • x번지의 왼쪽, 오른쪽 자식 : 2x, 2x+1
  • x번지의 부모 : x/2


최소 힙, 최대 힙 특징

  • 최소 힙 : 부모가 자식보다 작음
  • 최대 힙 : 부모가 자식보다 큼


STL priority_queue 제공!!

#include <queue>
int main() {
    priority_queue<int> pq; // 최대 힙 (기본값)
    // priority_queue<int, vector<int>, greater<int>>로 선언시 최소 힙
    pq.push(10); pq.push(2); pq.push(5); pq.push(9); // {10, 2, 5, 9}
    cout << pq.top() << '\n'; // 10
    pq.pop(); // {2, 5, 9}
    cout << pq.size() << '\n'; // 3
    if (pq.empty()) cout << "PQ is empty\n";
    else cout << "PQ is not empty\n";
    pq.pop(); // {2, 5}
    cout << pq.top() << '\n'; // 5  
    pq.push(5); pq.push(15); // {2, 5, 5, 15}
    cout << pq.top() << '\n'; // 15  
    return 0;
}



그래프

그래프는 인접행렬과 인접리스트(list보다 vector가 더 편함)로 표현할 수 있다.

  • 보통 인접리스트 사용이 많고, E가 V^2보다 훨씬 작을 때(sparse=희소) 사용한다.
  • 모든 간선 길이가 동일하면 BFS로 거리를 구할 수 있고, 길이가 다르다면 플로이드나 다익스트라 알고리즘을 활용해야 한다.


그래프를 BFS, DFS

// 연결 그래프 BFS 순회
// 만약, 노드들 중에 연결 그래프 아닌것도 순회하고 싶으면 그냥 모든 노드를 돌리면 됨
// 즉, 아래 코드를 전체 for문으로 감싸고, 1 대신 for문의 i로 변경
vector<int> vc[10];
bool visited[10];
void bfs() {
	queue<int> qu;
	qu.push(1);
	visited[1] = true;
	while (!qu.empty()) {
		int cur = qu.front();
		qu.pop();
		cout << cur << ' ';
		for (auto next : vc[cur]) {
			if (visited[next]) continue;
			qu.push(next);
			visited[next] = true;
		}
	}
}

// 연결 그래프 BFS 거리
vector<int> vc[10];
int dist[10];
void bfs() {
    fill(dist, dist+10, -1);
	queue<int> qu;
	qu.push(1);
	dist[1] = 0;
	while (!qu.empty()) {
		int cur = qu.front();
		qu.pop();
		for (auto next : vc[cur]) {
			if (dist[next]!=-1) continue;
			qu.push(next);
			dist[next] = dist[cur]+1;
		}
	}
}

// DFS 재귀 (비재귀는 위 BFS에서 큐->스택)
vector<int> vc[10];
bool visited[10];
void dfs(int cur) {
    visited[cur] = true;
    cout << cur << ' ';
    for(auto next : vc[cur]) {
        if(visited[next]) continue;
        dfs(next);
    }
}

// 필자가 항상 작성하던 DFS 재귀 방식 (최대 depth(깊이)를 지정했었음)
// 장점 : 원하는 개수만큼 만 접근이 가능
void dfs(int depth, vector<int> val) {
	if (depth == 4) { // base condition
		result = 1;
		return;
	}
	
	for (auto next : val) {
		if (!visited[next]) {
			visited[next] = true;
			dfs(depth + 1, inArr[next]);
			// visited[next] = false; // backtracking
		}
	}
}



트리

트리는 무방향이고 사이클이 없는 연결 그래프이다.

  • 트리의 순회방식 - BFS&DFS 순회, 이진 트리의 순회
  • 여러가지 트리 - Segment
  • 참고로 BST, RBT는 위에서 이미 정리 그리고 우선순위 큐에 사용한 힙도 이진트리임


1. 트리의 BFS, DFS 순회

  • 트리를 BFS 할 때 root부터 하므로 임의의 노드에서 그 노드의 부모는 이미 방문한거고, 자식들만 방문을 안한 상태인 것이다.
  • 따라서 따로 visited배열이 필요없이 p배열(부모) 을 알고 있으면 된다.
// DFS는 큐->스택 바꾸면 동일하게 동작
vector<int> vc[10];
int p[10];
int depth[10];
void bfs(int root) {
    queue<int> qu;
    qu.push(root);
    while(!qu.empty()) {
        int cur = qu.front();
        qu.pop();
        cout << cur << ' ';
        for (int next : vc[cur]) {
            if(p[cur] == next) continue; // 부모는 방문한 상태라서 continue
            qu.push(next);
            p[next] = cur; // parent 기록
            depth[next] = depth[cur] + 1; // dist배열 채우듯이 동일
        }
    }
}


2. 이진 트리의 순회

  • 레벨 순회 : 높이 순서대로 방문한다.
    • 기존이랑 동일. root를 시작점으로 bfs 돌리면 높이 순서대로 위에서부터 차례로 순회한다.
  • 전위, 중위, 후위 순회
    • 전위 : 위 -> 왼 -> 오
    • 중위 : 왼 -> 위 -> 오
    • 후위 : 왼 -> 오 -> 위
  • 구현 쉬워서 코드 생략


3. Segment Tree(구간합)

여러개의 데이터가 연속으로 있을때 배열 에서는 그 구간의 합을 구할때 복잡도가 N이 걸리는데, 이걸 세그먼트 트리 를 이용해서 logN으로 개선시키려는 목적

  • 리프 노드: 배열의 연속된 값 그 자체
  • 내부 노드: 왼쪽 자식과 오른쪽 자식의 합


/*
아래 코드는 "구간 합 구하기" 백준 문제를 풀었던 코드를 예시로 가져옴

구간 합 구하는 함수 : segmentSum
트리의 노드 수정하는 함수 : segmentUpdate
*/

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

long long inArr[2000010];
long long outArr[5000010];

// 재귀함수(세그먼트 트리 만드는)
long long segmentBuild(int start, int end, int node) {
	if (start == end) { // base condition
		outArr[node] = inArr[start];
		return outArr[node]; // 종료시점
	}

	int mid = (start + end) / 2; // mid 구해서 왼, 오 구간 나눔
	outArr[node] = segmentBuild(start, mid, node * 2) + segmentBuild(mid + 1, end, node * 2 + 1);
	return outArr[node]; // base condition (사실 바로 위 코드에 return 같이 적어도됨)
}


// 구하는 합 구간 left, right
// node가 담당하는 구간 start, end
long long segmentSum(int start, int end, int node, long long left, long long right) {
	// 1. 겹치지 않는 경우 (left, right가 start, end의 왼쪽이거나 오른쪽 구간인 경우)
	if ((left < start && right < start) || (left > end && right > end)) return 0;
	
	// 2. 완전히 포함하는 경우 (left, right가 start, end를 완전히 포함하는 경우)
	if (left <= start && right >= end) return outArr[node];

	// 3. 나머지 경우 (자식 트리 탐색)
	int mid = (start + end) / 2;
	return segmentSum(start, mid, node * 2, left, right) + segmentSum(mid + 1, end, node * 2 + 1, left, right);
}

// node가 담당하는 구간 start, end
// 수정할 노드 index, 수정할 값 dif
void segmentUpdate(int start, int end, int node, long long index, long long dif) {
	// 1. 겹치지 않는 경우 (왼쪽이거나 오른쪽 구간인경우)
	if ((start < index && end < index) || (start > index && end > index)) return;
	// 2. left, right가 start, end를 완전히 포함하는 경우
	if (start <= index && index <= end) outArr[node] += dif;
	
	// 무조건 종료시점(무한루프 안걸리게)
	if (start == end) return;
	// 3. 나머지 경우 (자식 트리 탐색)
	int mid = (start + end) / 2;
	segmentUpdate(start, mid, node * 2, index, dif);
	segmentUpdate(mid + 1, end, node * 2 + 1, index, dif);
}

int N, M, K;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		cin >> inArr[i];
	}
	segmentBuild(0, N-1, 1); // outArr 수정(index 1부터 저장)

	long long a = 0;
	long long b = 0;
	long long c = 0;
	for (int i = 0; i < M + K; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
            // b번째 수에 c를 더하는게 아닌,
			// b번째 수를 c로 바꿔야 하는건 `c-inArr[b-1]` 로 바꿔야 한다는 의미이다.
			segmentUpdate(0, N-1, 1, b-1, c-inArr[b-1]);
			inArr[b - 1] = c; // b->c로 변환 (`c-inArr[b-1]` 에 사용되니까 바꿔줘야함)
		}
		else if (a == 2) {
			cout << segmentSum(0, N-1, 1, b-1, c-1) << '\n';
		}
	}

	return 0;
}



위상 정렬

위상 정렬(Topological Sort) : 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬

image-20230506001732475

vector<int> adj[10];
int deg[10];
int n; // N개의 정점있고 번호는 1~indexed

queue<int> qu;
vector<int> vc; // result
for(int i=1; i<= n; i++)
    if(deg[i] == 0) qu.push(i);
while(!qu.empty()){
    int cur = qu.front(); qu.pop();
    vc.push_back(cur);
    for(int next : adj[cur]) {
        deg[next]--;
        if(deg[next] == 0) qu.push(next);
    }
}
if(vc.size() != n)
    cout << "cycle exists";
else {
    for(auto x : vc) cout << x << ' ';
}



최소 신장 트리

  • 바킹독 : https://blog.encrypted.gg/1024
  • 예전에 정리한 개념글 : MST-Prim,Kruskal


크루스칼, 프림 알고리즘이 대표적

크루스칼 알고리즘은 Union Find라는 알고리즘을 선행학습 하고 아래 코드를 이해할 것.

image-20230506012547858


프림 알고리즘은 우선순위 큐를 이용해서 구현을 하는데, 구현이 좀 복잡하다. 따라서 pass



최단 경로 트리

  • 바킹독 : https://blog.encrypted.gg/1035, https://blog.encrypted.gg/1037
  • 예전에 정리한 개념글 : Floyd, Dijkstra


플로이드 알고리즘은 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘이라 O(n3)의 큰 복잡도를 가진다.
다만, 구현이 3중 for문으로 간단히 할 수 있으며 n이 1000정도면 이 알고리즘을 써도 된다.

  • 최단 거리 테이블(2차원) 이 채워진다 => 코드보면 d배열 관련인데 생각보다 쉬운 로직!
  • 근데, 경로까지 구하고싶으면 테이블 하나 더 만들어서 기록해놔야 한다 => nxt배열에 기록

image-20230506013350391

image-20230506013359812


다익스트라 알고리즘 은 하나의 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이므로 복잡도는 플로이드보다 한단계 작은 O(n2) 이다.

  • 참고 : 가중치가 음의 값이 있으면 이 알고리즘 사용 불가
  • 동작원리는 간단한데 한 정점에서 갈 수 있는 최단 거리 정점을 택하면서 갱신해나가면 된다.
  • 여기서 개선된 알고리즘이 있는데 우선순위 큐를 활용한 알고리즘이다. 이 로직을 기억
    • 우선순위 큐에 거리를 다 넣어둔다음 매번 최소인걸 선택하는 로직
    • 물론 경로까지 구하는 방법은 플로이드 알고리즘 때와 유사

image-20230506014449754

image-20230506015237505

image-20230506015246272



?? KMP, 트라이 남음



컴퓨터그래픽스 관련

CCW, 교차여부, 다각형 면적, 다각형 포함, 볼록 껍질(외피=Convex Hull), 평면 소거법(직사각형 합집합=Plane Sweeping) 관련


1. 기본 기하 연산(between, intersect)

/*
ccw 함수(cw : counter clockwise = 시계방향)
leftTurn, rightTurn, collinear 함수 : 좌,우,일직선 검사
direction 함수 : 세점의 회전방향 검사에 따라서 1,-1,0 반환
between 함수 : 점 c가 선분 (a,b)에 위치하는가 검사
intersectProp 함수 : 교차여부를 구하는데, 선분의 끝점이 교차점 허용하지 않는 경우
intersect 함수 : 교차여부를 구하는데, 선분의 끝점이 교차점 허용하는 경우

이 중에서 between, intersect 가 중요

자료형 왠만하면 long long 쓰자
*/

#include<iostream>
using namespace std;

struct point {
	long long x;
	long long y;
};
typedef point Point;

// OP벡터, OQ벡터 (O는 원점)
// det(행렬식) => q가 p에 어느 방향인지 출력
long long ccw2(Point p, Point q) {
	return p.x * q.y - p.y * q.x;
}

// RP벡터, RQ벡터 => 시점R을 원점으로 만들어서 계산
// 시점을 원점으로 이동 : p-r, q-r
int ccw(Point r, Point p, Point q) {
	p.x -= r.x;
	p.y -= r.y;
	q.x -= r.x;
	q.y -= r.y;
	return ccw2(p, q);
}

// 세점 a,b,c의 회전방향이 좌,우,일직선인가 검사
bool leftTurn(Point a, Point b, Point c) {
	return ccw(a, b, c) > 0; // 좌회전 검사
}
bool rightTurn(Point a, Point b, Point c) {
	return ccw(a, b, c) < 0; // 우회전 검사
}
bool collinear(Point a, Point b, Point c) {
	return ccw(a, b, c) == 0; // 일직선 검사
}

// 선분 교차 검사를 위해 회전 방향에 따른 값 출력
// 좌 : 1, 우 : -1, 일 : 0
int direction(Point a, Point b, Point c) {
	if (leftTurn(a,b,c)) return 1;
	if (rightTurn(a,b,c)) return -1;
	if (collinear(a,b,c)) return 0;
}

// 점 c가 선분 (a,b)에 위치하는가
bool between(Point a, Point b, Point c) {
	if (!collinear(a, b, c)) return false; // 일직선 상에 없으면 false
	// 아래부턴 일직선 상에 있으니까 범위제한만 주면 된다.
	if (a.x != b.x) { // 수직선 아니면
		
		return (a.x <= c.x && c.x <= b.x) || (b.x <= c.x && c.x <= a.x);
	}
	else { // 수직선 이면
		return (a.y <= c.y && c.y <= b.y) || (b.y <= c.y && c.y <= a.y);
	}
}

// 선분 교차 검사 (교차점 허용) => 선분 ab, cd
int intersect(Point a, Point b, Point c, Point d) {
	// (a,b,c)*(a,b,d) ==-1 && (c,d,a)*(c,d,b)==-1 성립하면 교차
	// 추가조건 때문에 <=0로 판별
	if (direction(a, b, c) * direction(a, b, d) <= 0 && direction(c, d, a) * direction(c, d, b) <= 0) {
		// direction함수는 방향만을 나타내기 때문에 만약 0인 경우 일직선상인 건데,
		// 두 직선이 서로 접하는지 범위제한을 줘서 판단할 필요가 있음(between 함수 활용)
		if (direction(a, b, c) * direction(a, b, d) == 0 && direction(c, d, a) * direction(c, d, b) == 0) {
			// 점 c또는 d가 a,b직선 상에 존재하나 판단
			// 점 a또는 b가 c,d직선 상에 존재하나 판단
			if (between(a, b, c) || between(a, b, d)|| between(c, d, a) || between(c, d, b)) {
				return 1;
			}
			else
				return 0;
		}
		return 1;
	}
	else
		return 0;
}

// 선분 교차 검사 (교차점 제외) => 선분 ab, cd
bool intersectProp(Point a, Point b, Point c, Point d) {
	return direction(a, b, c) * direction(a, b, d) < 0 && direction(c, d, a) * direction(c, d, b) < 0;
}


2. 다각형 면적과 포함 계산

/*
area 함수 : 다각형 면적 구하기
insidePolygon 함수 : 다각형 포함 구하기
*/

// 다각형 면적 구하기 (외전 전부 더하면 됨)
double area(vector<Point> p) {
	int ret = 0;
	int n = p.size(); // 다각형 p의 정점 개수
	for (int i = 0; i < n; i++) {
		int j = (i + 1) % n; // 마지막에 index n->0으로 바뀜
		ret += (p[i].x * p[j].y - p[i].y * p[j].x);
	}
	return abs(ret) / 2.0;
}

// 다각형 포함 문제 (교차점 홀수면 내부 포함 인정)
bool insidePolygon(Point q, vector<Point> P) {
	int n = P.size();
	int crossings = 0;
	for (int i = 0; i < n; i++) {
		int iPlus1 = (i + 1) % n; // 마지막에 index n->0으로 바뀜
		// 1. 점 q가 다각형 에지(표면)에 있나 먼저 확인
		if (between(P[i], P[iPlus1], q)) return false;
		// 2. 교차점 판별 => crossings에 +1
		if((P[i].y<q.y&&P[iPlus1].y>=q.y&&leftTurn(P[i],P[iPlus1],q)) ||
			(P[iPlus1].y<q.y&&P[i].y>=q.y&&leftTurn(P[iPlus1],P[i],q)))
			crossings++;
	}
	if (crossings % 2 != 0) return true; // 홀수라면 true !!
	return false;
}


3. 볼록 외피(Convex Hull)

O(NlogN ) 방법 소개 - 참고 사이트 : https://www.crocus.co.kr/1288

/*
1. 우선 기준점을 잡는다. (보통 기준점은 y좌표가 가장 작은 것을 기준으로 한다.)
=> y좌표, x좌표 기준 오름차순 정렬해서 기준점을 P[0]으로 바로 잡자

2. 그리고 이 기준점으로 하여 다른 점들을 반시계 방향으로 정렬한다.
=> 각도에 따라 정렬 핵심 (참고 : 원점 이동한 상대위치로 각도 구함)

3. 컨벡스 헐 알고리즘(그라함 스캔(Graham's Scan) 알고리즘)을 이용한다.
=> 사이트 그림보면 이해하기 쉬움
*/

#include<iostream>
#include<algorithm>
#include<cmath> // atan2 (아크탄젠트 - 두점사이 절대각도 구함)
#include<stack>
using namespace std;

struct point {
	int x, y;
	int p, q;
};
typedef point Point;

double getAngle(Point p) {
    return atan2(p.q, p.p);
}

// 1. 각도 비교 사용시 각도 비교를 우선으로 정렬
// 2. 각도 비교 사용 안할시 y기준 정렬, x기준 정렬
bool comp(Point a, Point b) {
    // p, q 사용시 아래 조건문 만족하게 됨
    // p, q 사용안하면 0으로 초기화 되어있어서 아래 조건문 불만족
    if (getAngle(a) != getAngle(b)) return getAngle(a) < getAngle(b);
    
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

Point P[100];

int main() {
    int n; // 점 개수
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        P[i] = { x,y };
    }

    // y좌표, x좌표 기준 오름차순 정렬
    sort(P, P + n, comp);

    // 기준점(=P[0])기준 상대위치 기록 (따라서 i=1부터)
    for (int i = 1; i < n; i++) {
        P[i].p = P[i].x - P[0].x; // 기준점 빼서 원점으로 이동
        P[i].q = P[i].y - P[0].y;
    }

    // 구했던 상대위치 값으로 반시계 방향 정렬(기준점 제외. 따라서 p+1부터)
    // => 기준점에서 각도 비교로 반시계 정렬하면 됨
    sort(P + 1, P + n, comp);

    // 1st, 2st로 바로 초기값 사용 가능
    stack<int> st;
    st.push(0); st.push(1); // 0, 1 index 푸시

    // 전처리 과정 끝
    // 알고리즘 시작
    int next = 2; // next는 index 2부터 판단 시작
    while (next < n) { // 0부터 시작했으므로 next가 최종 n까지 가면 1바퀴 다 돈것이다
        while (st.size() >= 2) {
            int first, second;
            second = st.top();
            st.pop();
            first = st.top();

            // first, second, next가 좌회전 ( > 0 )이라면 second push 하고 next 이동
            // 우회전( < 0 )이라면 위의 while문 계속 반복 (즉, 이전 first,second상태로 되돌아감)
            if (ccw(P[first], P[second], P[next]) > 0) { // leftTurn써도 됨
                st.push(second);
                break;
            }
        }

        // next push
        st.push(next++);
    }

    cout << st.size(); // 볼록외피 좌표 index들 담겨있음

    return 0;
}


4. 평면 소거법(Plane Sweeping) => 합집합

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

struct Rectangle {
	int x1, y1, x2, y2;
};

vector<Rectangle> inArr;
int Q[10]; // 직사각형 x좌표 정렬해서 기록
int S[10]; // 직사각형 y좌표 정렬해서 기록
int counts[10]; // 겹쳐진 사각형 수
int m1 = 8; // events - Q size
int m2 = 8; // S size

// 합집합의 면적 계산 (합집합이므로 중복 면접 제외)
int UnionArea() {
	int sweepLine = 0; int delta = 0; int area = 0; // 면적
	for (int i = 0; i < m1; i++) {
		sweepLine = Q[i];
		Rectangle R = { 0,0,0,0 };
        // 0. 사용할 사각형 선택(x값 겹칠때 마다 선택)
		for (int j = 0; j < inArr.size(); j++) {
			if (inArr[j].x1 == Q[i] || inArr[j].x2 == Q[i]) {
				R = inArr[j];
				break;
			}
		}

        // 1. counts배열 구하기(y값 활용)
		// sweepLine이 만나는 사각형의 왼쪽 가로선만 +1, 오른쪽 가로선은 -1
		if (sweepLine == R.x1) delta = 1;
		else delta = -1;

		int y1 = R.y1; int y2 = R.y2;
		for (int j = 0; j < m2; j++) {
			if (y1 <= S[j] && S[j] < y2) {
				counts[j] += delta; // S[j]~S[j+1] 구간에 겹쳐진 사각형의 수
			}
		}
        
        // 2. 면적 계산 시작 
        // 현재 내부면적 세로줄(S[j + 1] - S[j])
		int curlength = 0; 
		for (int j = 0; j < m2; j++) {
			if (counts[j] > 0) { // counts배열 있는 값만(사각형 있는 경우에만)
				curlength += S[j + 1] - S[j];
			}
		}
        
		// 현재 내부면적 가로줄(Q[i+1]-Q[i])
		if ((i + 1) < m1) {
			area += curlength * (Q[i + 1] - Q[i]); // 현재 구한 면적 더함
		}
	}
	return area;
}


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> inArr[i].x1 >> inArr[i].y1 >> inArr[i].x2 >> inArr[i].y2;
		Q[i * 2] = inArr[i].x1; Q[i * 2 + 1] = inArr[i].x2;
		S[i * 2] = inArr[i].y1; S[i * 2 + 1] = inArr[i].y2;
	}
	m1 = N * 2; // 총 x축 개수
	m2 = N * 2; // 총 y축 개수
	
    // x축, y축 기록한 배열들 꼭 오름차순으로 정렬 후 사용
	sort(&Q[0], &Q[m1]);
	sort(&S[0], &S[m2]);

	cout << unionArea();

	return 0;
}



Network Flow(=Max-Flow, Min-Cut, 이분 매칭)

Ford-Fulkerson(DFS.복잡도:flow), Edmonds-Karp(BFS.복잡도:VE^2), Dinic’s Algorithm(BFS,DFS.복잡도:EV^2) 가 있으며 여기서 Dinic's 만 암기해도 충분

  • Ford-Fulkerson과 Edmonds-Karp는 DFS, BFS만 다르며 나머지는 로직이 정확히 동일
  • Dinic’s 는 BFS,DFS 뭘 쓰든 상관없는데 본인은 BFS로 레벨트리 구하고, DFS(재귀)로 연산을 진행
  • 중요한 점
    • “이분 매칭” 문제를 “Max-Flow” 문제로 치환해서 풀 수 있다.
    • “Min-Cut” 문제는 그냥 “Max-Flow” 로 풀었을 때 답과 동일하다.
    • 보통 문제를 푸는 방식은 문제에 적합하게 “그래프” 를 설계한 후 풀어나간다.
      • “그래프” 그리는 TIP
        • 그래프에는 에지를 그릴텐데 반드시 유량이 아닌 용량을 적어줄 것
          • 햇갈리면 안되는게 유량은 나중에 계산할때 값 생기기 시작
        • 멀티 Source, Sink의 경우?? 외부에 S, T 노드를 임의로 추가해서 사용
          • Max Flow는 S->T 로 흐르는 최대 유량을 구하는 형태이기 때문
          • 임의로 S, T를 추가했으므로 그래프 그릴때 용량을 잘 설정해야함
        • 복잡한 문제들은 에지를 안주고 직접 에지를 구해야 할때도 존재
          • 예시 문제 : Jerry and Tom
          • 참고 : 해당 예시에서는 에지를 직접 구해야하며, 해당 에지는 “선분교차” 여부에 따라 구해진다.


/*
BOJ 14286 문제. Min-Cut 문제 => "Max-Flow"
*/
#include<iostream>
#include<vector> // tree
#include<queue> // bfs
#include<algorithm> // fill
#define INF 987654321
using namespace std;

int c[505][505]; // 용량
int f[505][505]; // 유량
vector<int> vc[505]; // tree
int level[505]; // 레벨 그래프
int work[505];

int N, M, S, T; // 정점 수, 에지 수, 시작 노드, 끝 노드

bool bfs() {
	// init
	fill(level, level + 505, -1);
	queue<int> qu; // bfs
	level[S] = 0;
	qu.push(S);
	while (!qu.empty()) {
		int cur = qu.front();
		qu.pop();

		for (int i = 0; i < vc[cur].size(); i++) {
			int nxt = vc[cur][i];
			if (c[cur][nxt] <= f[cur][nxt] || level[nxt] != -1) continue;
			// 레벨이 아직 정해지지 않았고 잔여용량이 0이상은 계속 진행
			level[nxt] = level[cur] + 1; // level 기록 (그냥 깊이 기록임)
			qu.push(nxt);
		}
	}
	return level[T] != -1; // -1 이면 false 반환(종료 의미)
}

int dfs(int cur, int flow) {
	// base condition
	if (cur == T) return flow; // cur -> depth로 이해

	for (int i = work[cur]; i < vc[cur].size(); i++) {
		int nxt = vc[cur][i];
		if (level[nxt] - level[cur] != 1 || c[cur][nxt] <= f[cur][nxt]) continue;
		// 레벨 차가 1이고, 잔여용량이 0이상은 계속 진행

		// 최소 유량 탐색
		int minF = dfs(nxt, min(c[cur][nxt] - f[cur][nxt], flow));

		// 유량 update
		if (minF > 0) {
			f[cur][nxt] += minF;
			f[nxt][cur] -= minF;
			work[cur] = i; // index 기록해서 시간 단축
			return minF;
		}
	}
	work[cur] = vc[cur].size();
	return 0;
}

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

	// input
	cin >> N >> M;
	int n1, n2, w;
	for (int i = 0; i < M; i++) {
		cin >> n1 >> n2 >> w;
		vc[n1].push_back(n2);
		vc[n2].push_back(n1); // 양방향
		c[n1][n2] += w; // 양방향 간선이므로, 양쪽으로 용량 할당
		c[n2][n1] += w;
	}
	cin >> S >> T;

	// run
	int maximumFlow = 0; // 제거된 최소 간선 가중치 합
	while (true) {
		if (!bfs()) break; // 종료

		fill(work, work + 505, 0);
		int flow = dfs(S, INF);

		// 최대 유량 update
		maximumFlow += flow;
	}

	// output
	cout << maximumFlow;
	return 0;
}



참고

set, unordered_set, priority_queue 의 경우에 무슨 자료구조를 언제 사용할까를 정해두려고 한다.

  • 우선 set 을 우선으로 사용하되 prev, next, lower_bound 같은 동작들이 필요없고 priority_queue 가 사용하는 동작만 필요하다면 priority_queue 를 사용하자.

댓글남기기

참고