너무나 중요한 알고리즘

알고리즘.md

알고리즘

목차

1. 강의링크(Link)

2. 팁/키워드정리(Tip/Keywords)

3. 구현 (Implementation)

4. 수학/숫자 (Mathematics/Numerical)

5. 문자열 (Strings)

6. 정렬 (Sorting)

7. 재귀 (Recursion)

8. 동적 프로그래밍=DP (Dynamic Programming)

9. 탐색 (Search)

10. 그래프 (Graph)

11. 그리디 (Greedy)

1 강의링크

T아카데미 기초 : https://youtu.be/4E3i3uYHKeA

T아카데미 중급 : https://youtu.be/Cc-YlbLOaqY?list=PL9mhQYIlKEhcqOXxPOhs6pNpq681RDK4J

Jake Lee : https://youtu.be/mzM3S5FtKuw?list=PLl5LpJCoD2mCIRn0Fkt8z07EK320ZmHgY

권오흠 교수님 알고리즘 : https://www.youtube.com/watch?v=ln7AfppN7mY&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l

권오흠 교수님 자료구조 : https://www.youtube.com/watch?v=-XbHQQ8pUQY&list=PL52K_8WQO5oXIATx2vcTvqwxXxoGxxsIz

동빈나(안경잡이개발자) https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz

삼성 swea : https://www.swexpertacademy.com/main/learn/course/courseList.do

인프런 : https://www.inflearn.com/

백준(코드플러스) : https://code.plus/

2 팁 키워드정리

■ 문자 코드(Ascii/Unicode)

대문자 > 소문자

32 - space(공백)
65 - A
90 - Z
97 - a
122 - z

■ Swap 알고리즘

장점 : 간지남. 한줄코딩가능 ex) if(A > B) A ^= B ^= A ^= B;
단점 : 코드를 이해하기 어렵다.

int A = 5;
int B = 23;

A = A ^ B;
B = A ^ B;
A = A ^ B;

3 구현 (Implementation)

■ 야근지수

최고값을 줄어야하는 문제 일때 내가 생각한 방법인데 최고값 순으로 정렬 후 계단을 잘라가는 식으로 그 비용이 줄일 수 있는 값보다 작으면 한번에 싹둑한 후 비용이 클 때 for문 나와서 남은 줄일 수 있는 수를 사람들이 생각하는 -1 씩 줄이고 오름차순 정렬하고를 반복했음 (최대값을 찾아서 빼는게 더 효율적이긴하겠지만) 요점은 계단식 줄이기

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    int wSize = works.size();
    int gonnaWorkTime;
    long long workValue;

    sort(works.rbegin(), works.rend());
    
    for(int i=1; i<wSize; i++)
    {
        gonnaWorkTime = (works[i-1] - works[i])*i;
        if(gonnaWorkTime > n) break;
    
        for(int k=0; k<i; k++)
            works[k] = works[i];
    
        n -= gonnaWorkTime;
    }
    
    while(n>0)
    {
        if(works[0]==0) break;
        works[0] -= 1;
        sort(works.rbegin(), works.rend());
        n--;
    }
    
    for(int i=0; i<wSize; i++)
    {
        workValue = works[i];
        answer += workValue * workValue;
    }
    
    return answer;
}

■ 원의 교집합 구하기 (NumberOfDiscIntersections)

평면 상의 디스크들의 접점의 수를 구하라

가장 단순하게 각 디스크의 Left/Right가 다른 디스크의 Left, Right 사이에 포함되는 지 비교했다. 당연하게도 O(N^2)의 복잡도로는 O(N * lg(N))의 성능 테스트를 통과할 수 없었다.

Left와 Right가 각각 정렬되어 있을 때, 가장 작은 Right(O 마크)보다 작은 Left(V 마크)들은 반드시 가장 작은 Right(O 마크)보다 큰 Right를 갖는다. 즉, 접점을 갖는다. O 마크의 Right가 가장 작으니까 당연히 나머지 Right들은 그보다 크다.

이 작업을 각 Right마다 새로 하는 것이 아니라 Accumulate하게 진행한다.

R > L 인 L의 수(current)를 구한다. –current; current는 반드시 자기 자신을 포함한다. 또한 다음 R에서 겹치지 않을 수 있는 경우의 수를 제거한다. current는 초기화하지 않고 계속해서 사용한다.

[코드]

#include <vector>
#include <algorithm>

int solution(vector<int> &A) 
{
	unsigned int N = A.size();
	std::vector<long long>left(N), right(N);
    // 계산되는 값들의 타입을 맞춰주도록 한다
	for (unsigned long long i = 0; i < N; ++i)
	{
		left[i] = i - A[i];
		right[i] = i + A[i];
	}

	std::sort(left.begin(), left.end());
	std::sort(right.begin(), right.end());
	
	long long result{}, current{};
	unsigned long long lIndex{}, rIndex{};
	for (auto i = 0; i < N; ++i)
	{
		while (lIndex < N && left[lIndex] <= right[rIndex])
		{
		    ++current;
			++lIndex;
		}
		--current;
		result += current;
		++rIndex;
	    std::cout << current << " ";
		if (result > 10000000)
			return -1;
	}
	return result;
}

4 수학 숫자 (Mathematics Numerical)

■ 소수 (Prime number)

자기 자신보다 작은 수들을 나누어봐서, 하나라도 나누어지면 소수가 아닌 것

확장하기 > 입력받은 수보다 작은 수의 소수들만 나누어보면 되는 것이다. (ArrayList에 소수를 넣어놓고 나누어보는 방식으로~) n까지의 소수를 다 구해야할 때 더 유리한 코드가 된다.

public class PrimeNumber1 {
	public static void getPrime(int num, ArrayList<Integer> prime) {
		prime.add(2); 
		for (int i = 2; i <= num; i++) {
			for (int j = 0; prime.size() > j; j++) {
				if (i % prime.get(j) == 0) break; // 소수가 아닌 경우 pass
				if (j + 1 == prime.size()) // 소수일 때
					prime.add(i);
			}
		}

		for (Integer result : prime) {
			System.out.println(result);
		}
	}

	public static void main(String[] args) {
		ArrayList<Integer> prime = new ArrayList<Integer>();
		long start = System.currentTimeMillis();
		getPrime(30000, prime);
		long end = System.currentTimeMillis();
		System.out.println("수행시간 : " + (end - start));
	}
}

확장하기 > 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.
수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.
즉, 2부터 N의 제곱근 까지 나눠보면 된다.

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;
    bool isPrime = true;

    // 2부터 N의 제곱근까지의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
    for (int i=2; i<=sqrt(num); i++) {
        if (num % i == 0) {
            isPrime = false;
            break;
        }
    }

    if(isPrime) {
        cout << num << "은 소수입니다." << endl;
    }
    else {
        cout << num << "은 소수가 아닙니다." << endl;
    }

    return 0;
}

확장하기 > 에라토스테네스의 체 (Sieve of Eratosthenes) 나눌 필요가 없이 배수를 체크하는 식으로 진행

void getChe(int num) {
    int *arr;
    arr = (int *)malloc(sizeof(int) * num);
    int i = 2;
    
    // 입력받은 수 만큼 배열에 모두 초기화 해둔다
    for (i = 2; i <= num; i++) {
        arr[i] = i;
    }

    for (i = 2; i <= num; i++) { 
        if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다
            continue;
        //소수 찾았을때     
        for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크
            arr[j] = 0;
        }
    }

    // print
    for (i = 2; i <= num; i++) {
        if (arr[i] != 0)
            cout << arr[i] << " ";
    }
}

프로그래머스 소수 찾기 - n까지의 소수 개수 구하기 (내 코드)

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int arr[1000000];
    int i = 2;
    
    for(i=2; i<=n; i++)
        arr[i] = i;
    
    for(i=2; i<=n; i++)
    {
        if(arr[i]==0) continue;
        answer++;
        for(int j=i+i; j<=n; j+=i)
            arr[j] = 0;     
    }
        
    return answer;
}

■ 약수 (Divisor)

% 나눠서 나머지가 0이면 약수.

확장하기 > n의 1/2 제곱까지만 측정해서 i * i 제곱약수 걸러주고 그 외는 n/i로 약수의 짝을 구하면 반복문을 줄일 수 있다.

#include<cmath>
int sum = 0;
  for(int i=1; i<=sqrt(n); i++) if(n%i==0) { sum += i; if(n!=i*i) sum += n/i; }
return sum;

확장하기 > 소수 구해서 n = 2^a * 3^b * 5^c일때 약수의 총합은 (a+1)(b+1)(c+1)이다.

■ 최대공약수 (GCD)

확장하기 > 유클리드 호제법
만약(a>b일 때) f(a,b)=f(b, a mob b)=f(a mob b, b mob (a mob b)) ... f(x, y)나머지가 0이 되었을 때 그 수 y는 a,b의 최대공약수다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

(54, 24) (24, 54/24..6) (6, 24/6..0) -> 6

예제) #1

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> gcdlcm(int a,int b)
{
	vector<int> answer;
    if(min(a,b)==a) swap(a,b);
    int mod = a%b;
    int c = a;
    int d = b;
    while(mod>0) {
        c = d;
        d = mod;
        mod = c%d;
    }
    answer.push_back(d);
    answer.push_back(a*b/d);
	return answer;
}

#2

int main()
{
	int a=3, b=12;
	vector<int> testAnswer = gcdlcm(a,b);

	cout<<testAnswer[0]<<" "<<testAnswer[1];
}

int Euclidean(int a, int b)
{
    return b ? Euclidean(b, a%b) : a;
}

vector<int> gcdlcm(int a,int b)
{
    vector<int> answer;
    // 유클리드 호제법
  answer.push_back(Euclidean(a,b));

■ 최소공배수 (LCM)

LCM = A * B / 최대공약수(GCD)

N개의 최소공배수 구하기

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int euclidean(int a, int b)
{
    return b ? euclidean(b, a%b) : a;
}

int lcm(int a, int b)
{
    return a*b/euclidean(a,b);
}

int solution(vector<int> arr) {
    sort(arr.begin(),arr.end(),greater<int>());
    int answer = arr[0];
    int arrSize = arr.size();
    
    for(int i=1; i<arrSize; i++)
        answer = lcm(answer, arr[i]);
        
    return answer;
}

■ 피보나치 수열 (Fibonacci Sequence)

• 2, 1짜리로 n을 체우는 경우의 수 문제는 피보나치 수열로 풀 수 있다고 보면 된다.
• ex) 점프 2,1 n칸 건너기, 타일링 2x1 짜리로 n칸 체우기

1. 재귀형식
   0, 1, 1, 2, 3, 5, 8, ... 이므로 n이 1보다 작으면 n을 아니면 점화식 따라간다.

int fibonacci(int n){
    if(n<=1) return n;
    else return fibonacci(n-2)+fibonacci(n-1);
}

이렇게 만들어진 형식은 아무래도 함수 호출당 함수 호출 수가 각 2배씩 늘어나므로 O(2^n) 시간복잡도.

2. 재귀 + 저장을 이용한 방식
   재귀적인 호출에서 중복으로 호출이 되는 fibonacci 함수들이 있다.
   예를 들면 f(4)를 호출했을 때 f(3)과 f(2)가 호출되고, f(3)에서 f(2), f(1)이 호출
   여기까지만 봐도 f(2)가 두 번 등장함 값을 저장해 놓고, 다음 호출에서는 값을 호출
   시간이 많이 줄어듬, n인 경우 f(0)부터 f(n-1)까지 한번씩만 계산이 될것이므로 시간복잡도는 O(n) (중복된 호출은 O(1)시간에 끝나기 때문)

int fibonacci(int n){
    if(n<=1) return n;
    else if(m[n]) return m[n];
    else return m[n] = fibonacci(n-1)+fibonacci(n-2);
}

3. For-loop을 이용한 방식
   이 방식은 위의 재귀 + 저장 방식을 unroll한 방식.
   피보나치 수열의 일반항을 그대로 0번째 부터 쭉 계산해 나가는 방식.
   이 방법 역시 시간복잡도는 O(n)

int fibonacci(int n){
    int f[n+1] = {0, 1};
    for(int i = 2; i <= n; i++){
        f[i] = f[i-1]+f[i-2];
    }
    return f[n];
}

4. 큰 피보나치 수의 나머지(피사노 주기)
   문제 중에는 구하려는 수가 너무 커서 일정한 숫자 K의 나머지로 구하라는 문제가 있다.
   [피사노 주기]
   피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 된다. 이 주기를 피사노 주기.
   특히 K가 10의 m승이고, m>2라면 주기는 15 x K/10.
   만약 K = 1,000,000 이라면 m = 6 이고 주기는 1,500,000.
   즉 1,500,000번째까지 나머지만 잘 구해놓으면 그 이상의 수는 주기성을 이용하여 금방 구할 수 있게 됨.

#define P 1500000
#define K 1000000
int fibonacci(long long n){
    n %= P;
    int f[n+1] = {0, 1};
    for(int i = 2; i <= n; i++){
        f[i] = f[i-1] +f[i-2];
        f[i] %= K;
    }
    return f[n];
}

5. 피보나치 관계식의 행렬표현
   나머지 연산을 하라는데 10의 거듭제곱이 아니라면?
   그럴땐 관계식을 행렬로 표현하는 방식을 사용.
   => F_n+2 = F_n+1 + F_n, n>= 0
   => F_n+2 = (1 1)(F_n+1
   F_n )
   => (F_n+2 = (1 1 (F_n+1
   F_n+1) 1 0) F_n )
   => (F_n = (1 1 ^n-1 (F_1
   F_n-1) 1 0) F_0) , n>=1

결론

(F_n+1 F_n = (1 1 ^n
(F_n F_n-1) 1 0) , n>=1

{{1,1},{1,0}}의 n승의 성분을 통해 피보나치 수를 알아낼 수 있다.
이렇게 할 경우 O(n)

추가적으로 거듭제곱의 계산은 거듭제곱 수 n의 이진표현을 통해 빠르게 계산할 수 있는데 이 경우 시간복잡도는 O(log(n))
x^n/2 + x^n/2 = x^n 이므로 n이 홀수일 때 해당 x를 곱해주는 것 여기선 res{{1,0}{0,1}}

#include<cstdio>
#include<vector>
#define mod 1000000007LL
using namespace std;
typedef vector<vector<long long> > matrix;

matrix operator*(matrix&a, matrix&b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for(int k = 0 ; k < n; k++){
                c[i][j] += a[i][k] * b[k][j];
            }
            c[i][j] %= mod;
        }
    }
    return c;
}

int main() {
    long long n;
    matrix res = { {1, 0},{0, 1} };
    matrix x = { {1, 1},{1, 0} };
    scanf("%lld", &n);
    while (n) {
        if (n % 2 == 1) {
            res = res * x;
        }
        x = x*x;
        n *= 0.5;
    }
    printf("%lld\n", res[0][1]);
    return 0;
}

프로그래머스 풀면서 내가 정리한 c++코드

#include<vector>

using namespace std;
typedef vector<vector<long long>> matrix;

matrix operator* (matrix &a, matrix &b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<n; k++)
                c[i][j] += a[i][k] * b[k][j];
    return c;
}

long long solution(int N) {
    long long answer = 0;
    matrix res = {{1, 0},{0, 1}};
    matrix fib = {{1, 1},{1, 0}};
    
    while(N) {
        if(N&1) res = res * fib;
        fib = fib * fib;
        N *= 0.5;
    }
    
    return answer= res[0][1];
}

■ 삼각 수 (Triangular Number)

삼각 수는
A+B>C, A+C>B, B+C>A 모두 만족했을 때 그 3수를 삼각 수라고 하는데
쉽게 삼각 수를 판별하기위해 A, B, C를 오름차순으로 정렬 후
A+B>C만 만족하면 삼각 수라는 것을 구할 수 있다.

해커랭크에 문제가 있던걸로 기억

■ 하샤드 수 (Harshad Number)

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 한다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수

핵심포인트는 정수형에서 10의 나머지로 마지막 자리수를 구하고 나서
다음 자리수를 구하기 위해 10으로 나눠주는 것.

프로그래머스 내 코드는

using namespace std;

bool solution(int x) {
    int sumX = 0;
    int numX = x*10;
    
    for(int i=0; i<5; i++)
        sumX += (numX/=10)%10;
    
    return x%sumX==0 ? true : false;
}

■ 셀프 넘버 (Self Number)

인도 수학자 D.R Kaprekar
양의 정수 n에 대해서 d(n)을 n과 n의 각자리 수를 더하는 함수. d(75) = 75+7+5 = 87 이다.
n,d(n),d(d(n)) ... 무한 수열을 만들 수 있다. n을 d(n)의 생성자라고 하는데 생성자가 한 개보다 많은 경우도 있다.
101은 생성자가 2개 91, 100이 있다.
생성자가 없는 숫자를 셀프 넘버라고 한다.
100보다 작은 셀프 넘버는 총 13개 1,3,5,7,9,20,31,42,53,64,75,86,97
10000보다 작은 셀프 넘버를 찍어봐라

백준 문제

규칙 모르겠음.. 9 19 29 39 49 59 ... 의 d(n)을 구해서 +2 하는데 99 199 299..10번 마다 전에 (89, 189, 289..의 +2)한 걸로 대체 1자리는 13579 하지만 아님...

그냥 노가다..

#include <iostream>
#include <vector>

using namespace std;

vector<bool> selfNum(10100, true);

int dN(int n) {
	int res = n;
	n*=10;
	do { res+=(n/=10)%10; } while(n>0); 
	
	return res;

}

int main() {
	for(int i=1; i<=10000; i++) {
		selfNum[dN(i)]=false;
	}
	
	for(int i=1; i<=10000; i++) {
		if(selfNum[i]) cout<<i<<endl;
	}

	return 0;

}

■ 콜라츠 추측

1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

핵심포인트는 자료형의 범위였다. 626331 이정도의 숫자도 콜라츠의 추측시 21억을 넘는 값이 나와 int가 아닌 long값으로 계산해야한다.

내 코드

using namespace std;

int solution(int num) {
    int answer = 0;
    long Num = num;
    
    while(Num!=1)
    {
        if(Num%2==0) Num*=0.5;
        else Num=Num*3+1;
        
        if(++answer>500) { answer= -1; break; }
    }
    
    return answer;
}

■ 홀수/짝수 간단한 코드

num & 1 ? "Odd" : "Even";

■ 자리수 합 간단한 코드

using namespace std;

int solution(int n)
{
    int answer = 0;

    n*=10;
    while(n>9)
        answer += (n/=10)%10;
    
    return answer;
}

■ 가우스 알고리즘

짝수개 : (Max+Min) * 전체의 반
홀수개 : (Max+Min) * (전체의 반) #단, 소수점을 살린다. 가운데 값을 위해

■ 행렬

두 행렬 A, B가 있을 때 이것이 각각 P * Q 형태와 Q * R형태여야 행렬 간 곱셈이 가능하고 결과 행렬은 P * R형태가 된다. 예를 들어 52 행렬과 36 행렬은 서로 곱할 수 없고 53 행렬과 36 행렬은 곱할 수 있다. 그리고 결과물은 5*6이 된다.

■ 최솟값 만들기

두 집합에서 각각 숫자를 뽑아 곱해서 모든 수를 더한게 최소가 되려면 그냥 한 쪽 오름차순 내림차순 정렬 후 가장 작은 수와 큰 수를 곱하는 식일 때 최솟값이 된다.

■ 연속된 덧셈으로 표현된 숫자

이거 내가 발견한건데 그냥 그 수의 약수중에 홀수의 개수를 구하면 된다. 이유는 모르겠다. 규칙 생각해서 해봤는데 됨. 15 -> 1,3,5,15 4가지 표현방식이 있을 것 12345, 345, 78, 15 10 -> 1,2,5,10 2가지 표현방식이 있을 것 1234, 10

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    int answer = 0;
    for(int i=1; i<=sqrt(n); i++)
        if(n%i==0) 
        {
            if(i&1) answer++;
            if(n!=i*i&&(n/i)&1) answer++;
        }
    return answer;
}

■ Bit의 수 구하기

int bitCount(int n)
{
    int count =0;
    while(n>0)
    {
        if(n&1) count++;
        n >>=1;
    }
    return count;
}

■ 소괄호만 옳은지 아닌지 체크하는 알고리즘

#include <string>

using namespace std;

bool solution(string s)
{
    int openCnt=0;
    int totCnt = s.length();
    char c;

    for(int i=0; i<totCnt; i++)
    {
        c = s[i];
        if(c==')') 
        {
            if(openCnt==0) return false;
            openCnt-=1;
        }
        else
        {
            openCnt++;
            if(totCnt-i-1<openCnt) return false;
        }
    }
    if(openCnt!=0) return false;
    return true;
}

■ 가장 큰 사각형 찾는 알고리즘

1행 1열을 제외하고 (1,1)인덱스부터 반복문을 돌리는데 현재 값이 1이상일 때 왼쪽, 위, 왼쪽위의 값 중의 최소값에 +1더 한 값을 현재 값에 넣는다.
이런식으로 돌리면 가장 큰 숫자가 나온 위치 왼쪽위로 사각형이 가장 큰 사각형인거다.
0 0 0 0 0 0
0 1 1 1 1 0
0 0 1 2 2 1
1 0 1 2 3 0
1 0 1 0 1 1
1 0 0 1 0 0

변의 길이가 3 이 가장 큰 사각형

■ 0이 없는 ?진수로 표현하기

124 일 경우
3진수를 0을 3으로 바꾸고 3을 4로 그런데 한가지 문제가 있었는데, 그것은 1, 2, 4로만 숫자를 표시해야하기
때문에 3으로 나누어 떨어졌을 때 자리수를 나타내줄 0이 없다. 그러므로 1씩 낮춰줘야한다.

String answer = "";  
        int[] arr = {4, 1, 2};  
        int a;
        while (n > 0) {
            a = n % 3;
            n = n / 3;
            if (a == 0) {
                n -= 1;
            }
            answer = arr[a] + answer;
        }
        return answer;

■ 땅따먹기 사다리타며 최댓값 찾기

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.
위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아
16점이 최고점이 되므로 16을 return 하면 됩니다.

해결책은 위에서부터 0열부터 3열까지 i+1행에 i행의 3개의 열(자기자신 열 빼고)의 최대값을 찾아서 더해주면된다.
그럼 결국 마지막행에 도착했을 때 4개 열 값 중에 가장 높은게 최고점임.

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;
    int height = land.size();
    
    for(int i=0; i<height-1; i++)
    {
        land[i+1][0] += max(land[i][1],max(land[i][2],land[i][3]));
        land[i+1][1] += max(land[i][0],max(land[i][2],land[i][3]));
        land[i+1][2] += max(land[i][0],max(land[i][1],land[i][3]));
        land[i+1][3] += max(land[i][0],max(land[i][1],land[i][2]));
    }
    
    sort(land[height-1].rbegin(),land[height-1].rend());
    
    return answer=land[height-1][0];
}

5 문자열 (Strings)

■ 특정 문자기준 스트링 정렬

-방법) 그 문자를 때어서 처음에 붙인다음 정렬하고 나서 그 문자를 빼준다.
-방법) 정렬함수에서 특정 조건을 만드는 것을 찾아본다.
-방법) 이중 포문 반복문을 사용해서 버블정렬한다.
-방법) 페어를 쓰는데 한쪽문자, 한쪽 문자열 해서 정렬 두개다 보고 소트되니까 문자->문자열 순으로 정렬됨.

■ 팰린드롬 Palindrome 알고리즘 O(n^2)

for문 돌면서 해당 문자를 가운데 문자라 생각하며 k를 둬서 왼쪽과 오른쪽으로 증가시켜가며 값이 같은지 체크,
다시 돌려 aa, bb를 있는지 체크 후 있으면 k또 반복 최대값을 구하면 됨. (이 부분을 대체하기 위해선 #같은걸 삽입해서 홀짝구분없이 만든다.)
#a#a#b#a#a# -> 5가 최대

#include <string>

using namespace std;
int solution(string s)
{
    int answer=1;
    int sSize = s.length();
    int resSize;
    int maxPalin=0;
    string res = "";
    
    for(int i=0; i<sSize; i++)
    {
        res += "*";
        res += s[i];
    }
    
    res += "*";
        
    resSize = res.length();
    for(int i=0; i<resSize; i++)
    {
        for(int k=1; k<resSize*0.5; k++)
        {
            if(i-k<0||i+k>resSize) break;
            if(res[i-k]==res[i+k]) maxPalin++;
            else break;
        }
        if(maxPalin>answer) answer = maxPalin;
        maxPalin=0;
    }
    
    return answer;
}

해결) Manacher's 알고리즘 O(n)
http://namnamseo.tistory.com/entry/%EC%A0%84%EC%B2%B4-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%97%90%EC%84%9C-palindrome%EC%9D%98-%EA%B0%AF%EC%88%98-%EC%84%B8%EA%B8%B0-ON https://tarokuriyama.com/projects/palindrome2.php https://www.crocus.co.kr/1075

■ KMP 알고리즘(Knuth, Morris, Prett이기 때문에 앞글자를 하나씩 따서 KMP알고리즘)

텍스트 "ABCABABCDE"에서 패턴 "ABC"가 어디서 등장하는지 찾을때 패턴 "ABC"를 한자리씩 옮기면서 같은지 비교한다.

KMP알고리즘은 O(N+M)으로 위의 무식한 방법 O(NM)보다 빠르다.

접두사(prefix)와 접미사(suffix)
<banana의 접두사>
b
ba
ban
bana
banan
banana
이 6개가 banana의 접두사(prefix)

<banana의 접미사>
a
na
ana
nana
anana
banana
이 6개가 banana의 접미사(suffix)

pi[i]는 주어진 문자열의 0i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이
(이때 prefix가 0i 까지의 부분 문자열과 같으면 안된다.)

"ABAABAB"의 pi배열의 최대값은 3이다. ABA ABA일 때

텍스트 "ABCDABCDABEE"에서 패턴 "ABCDABE"를 찾는 상황을 생각해보자.
첫번째 시도에서 패턴의 0~5부분 문자열("ABCDAB")는 텍스트와 일치했지만 6번째 인덱스의 E가 텍스트와 일치하지 않는다.
무식한 방법은 0-5부분이 일치했다는 정보를 무시한다. KMP는 이를 활용한다.

"ABCDABE"의 pi[5] =2 (AB CD AB)이기에 pi[5]의 값이 2이니까 6-2 4인덱스 부터 시작해서 AB가 같을걸 알기에 C(i지점)부터 비교하면된다.

ABCDABCDABEE
ABCDABE
i

[구현코드]

vector<int> getPi(string p){  
    int m = (int)p.size(), j=0;  
    vector<int> pi(m, 0);  
    for(int i = 1; i< m ; i++){
        while(j > 0 && p[i] !=  p[j])
            j = pi[j-1];
        if(p[i] == p[j])
            pi[i] = ++j;
    }
    return pi;
}
vector<int> kmp(string s, string p){
    vector<int> ans;
    auto pi = getPi(p);
    int n = (int)s.size(), m = (int)p.size(), j =0;
    for(int i = 0 ; i < n ; i++){
        while(j>0 && s[i] != p[j])
            j = pi[j-1];
        if(s[i] == p[j]){
            if(j==m-1){
                ans.push_back(i-m+1);
                j = pi[j];
            }else{
                j++;
            }
        }
    }
    return ans;
}

[다른구현코드]

void getpi(){
    pi.resize(b.length());
    int j = 0;
    for (int i = 1; i < b.length(); i++){
        while (j > 0 && b[i] != b[j])    
            j = pi[j - 1];        //불일치가 일어날 경우
        if (b[i] == b[j])
            pi[i] = ++j;        //prefix가 같은 가중치만큼 pi를 정해줍니다.
    }
}

void kmp(){
    int j = 0;
    for (int i = 0; i < a.length(); i++){
        while (j > 0 && a[i] != b[j])        //현재 j만큼 찾았는데 이번에 비교하는 문자가 다른 경우
            j = pi[j - 1];        //문자열 B를 failure function 이후 부터 비교를 해줍니다.
        if (a[i] == b[j]){            //비교하는 문자가 같은 경우
            if (j == b.length() - 1){    //문자열 B를 전부 탐색하였기 때문에 답에 위치를 넣어줍니다.
                res.push_back(i - b.length() + 1);
                j = pi[j];    //다음 탐색을 위하여 이번에도 failure function 이후 부터 비교를 해줍니다.
            }
            else
                j++;    //문자열 B의 다음 단어를 비교해줍니다.
        }
    }
}

■ 문자열 정렬 문제 - 파일명 정렬 (카카오 블라인드 테스트)

여기서 느꼈던 것은

• 정렬의 종류를 알아야한다는 점
  안정정렬과 불안정정렬이 있고
  기본적인 퀵정렬은 불안정정렬이라는 점.
  stable_sort()같은 함수를 써서 비교하는데 대부분 정렬을 위한 조건 함수가 있어 그부분을 사용해서 구현하면 쉬운 문제였다.

■ 문자열 판단 문제 - 방금그곡 (카카오 블라인드 테스트)

여기서 느꼈던 것은

• 치환을 사용하자
  C와 C#을 구분하기 위해 '#을 해서~' 이거보다 치환하는 생각을 하자 C와 c를 구분하기만하면됨
  C# -> c

• 문제를 잘 읽어야한다.

■ 매칭점수 (카카오 블라인드 테스트)

케이스 9번에서 오류나면 meta 정보 조건에 나온대로 케이스 잡아줘야한다.

#include <bits/stdc++.h>

using namespace std;

int solution(string word, vector<string> pages) {
    int answer = 0;
    vector<pair<double, int>> totPoint;
    vector<double> dPoint(pages.size(),0), lPoint(pages.size(),0);
    vector<int> lCnt(pages.size(),0);
    vector<string> lList;
    vector<vector<int>> toTarget(pages.size()); 
    string s;
    string::size_type start;
    string::size_type end;
    

    transform(word.begin(), word.end(), word.begin(), ::toupper);
    
    for(int i=0; i<pages.size(); i++) {
        int cnt = 0;
        start = 0;
        end = 0;
        
        transform(pages[i].begin(), pages[i].end(), pages[i].begin(), ::toupper);
    
        while ((start = pages[i].find(word, start)) != string::npos) {
            if(isupper(pages[i][start-1])||isupper(pages[i][start+word.length()])) { start += word.length(); continue; }
            ++cnt;
            start += word.length();
        }
        
        dPoint[i] = cnt;
        
        //cout<<cnt<<endl;
        
        start = 0;
        end =0;
        s = "<META PROPERTY=\"OG:URL\" CONTENT=\"";
        start = pages[i].find(s, start);
        if(start==0) {lList.push_back("NULL"); continue; }
        start += s.length();
        end = pages[i].find("\"",start);
        lList.push_back(pages[i].substr(start,end-start));
    
        //cout<<start<<"m"<<end<<lList[i]<<endl;
    }
    
    for(int i=0; i<pages.size(); i++) {
        start = 0;
        end =0;
        s = "<BODY>";
        start = pages[i].find(s, start);
        start += s.length();
        s = "<A HREF=\"";
        string webL;
        vector<string>::iterator w;
        while((start = pages[i].find(s, start)) != string::npos) {
            start = pages[i].find(s, start);
            start += s.length();
            end = pages[i].find("\"",start);
            webL = pages[i].substr(start,end-start);
            if((w = find(lList.begin(), lList.end(), webL)) != lList.end()) {
                toTarget[i].push_back(distance(lList.begin(),w));
            }
            lCnt[i]++;
            
            //cout<<i<<","<<webL<<","<<toTarget[i].size()<<endl;
        }
    }
    
    for(int i=0; i<pages.size(); i++) {
        for(int j=0; j<toTarget[i].size(); j++) {
            lPoint[toTarget[i][j]]+=dPoint[i]/lCnt[i];
        }
        
    }
    
    for(int i=0; i<pages.size(); i++) {
        totPoint.push_back({dPoint[i]+lPoint[i],i});
        
        //cout<<totPoint[i].first<<","<<totPoint[i].second<<endl;
    }
    
    sort(totPoint.begin(), totPoint.end(), [](const pair<double, int>& a, const pair<double, int>& b) { 
        if(a.first==b.first) return a.second<b.second;
        return a.first>b.first;
    });
    answer = totPoint[0].second;
    
    return answer;
}

■ 다음 순열 알고리즘

1,2,3,4 -> 1,2,4,3 -> 1,3,2,4 이렇게 다음 순열로 변경하는 문제 결국 n!번 횟수를 갖게되는데
k번째 형태를 구할려면 (n-1)!을 구해서 'k/(n-1)! = 인덱스-1' 과 같으므로 나눈 결과에 +1 해준다음 끌어오면 첫번째 요소를 구할 수 있다.
단, k%(n-1)! == 0 나머지가 0일때는 'k/(n-1)! = 인덱스' 이므로 인덱스 하나 빼줘야한다.
이 조건을 유지하며 n을 1씩 낮춰주면서 반복하면 k번째 순열을 구할 수 있다.

#include <vector>
#include <iostream>

using namespace std;

long long fac(int n)
{

    return n<=1 ? 1 : n*fac(n-1);
}

vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> nList;
    long long nSub;
    long long index;
    long long mod;

    for(int i=0; i<n; i++)
        nList.push_back(i+1);
    
    while(n>0)
    {
        nSub = fac(n-1);
        index = k/nSub;
        mod = k%nSub;
        if(mod==0) { index -= 1; k= nSub; }
        else k = mod;
    
        answer.push_back(nList[index]);
        nList.erase(nList.begin()+index);
        n--;
    }


    return answer;
}

■ 하노이의 탑 알고리즘

재귀호출

1. [1:n-1] 원판을 A에서 B로 옮긴다. 똑같은 과정이 [1:n-2]의 원판에 대해 필요하다. (재귀 호출) ​ 1-1) [1:n-2] 원판을 A에서 C로 옮긴다.
   ​ 1-2) [n-2] 원판을 A에서 B로 옮긴다.
   ​ 1-3) [1:n-2] 원판을 C에서 B로 옮긴다.
2. n 원판을 A에서 C로 옮긴다.
3. [1:n-1] 원판을 B에서 C로 옮긴다.

hanoi(3, A, B, C)를 호출한 경우를 생각해보자.

1. hanoi(3, A, B, C) > hanoi(2, A, C, B) > hanoi(1, A, B, C)
   : 탈출 조건에 의해 "1 원판을 A에서 C로 옮긴다." 출력
2. hanoi(3, A, B, C) > hanoi(2, A, C, B)
   : #2번 과정에 의해 "2 원판을 A에서 B로 옮긴다." 출력
3. hanoi(3, A, B, C) > hanoi(2, A, C, B) > hanoi(1, C, A, B)
   : "1 원판을 C에서 B로 옮긴다." 출력
4. hanoi(3, A, B, C)
   : #2번 과정에 의해 "3 원판을 A에서 C로 옮긴다." 출력
5. hanoi(3, A, B, C) > hanoi(2, B, A, C) > hanoi(1, B, C, A)
   : "1 원판을 B에서 A로 옮긴다." 출력
6. hanoi(3, A, B, C) > hanoi(2, B, A, C)
   : #2번 과정에 의해 "2 원판을 B에서 C로 옮긴다." 출력
7. hanoi(3, A, B, C) > hanoi(2, B, A, C) > hanoi(1, A, B, C)
   : "1 원판을 A에서 C로 옮긴다." 출력

// hanoi 함수 : N개의 원판을 A에서 C로 옮긴다. B를 사용할 수 있다.

hanoi(N, A, B, C) {  
   if( N == 1) {  
      // 원판을 A에서 C로 옮긴다. 탈출 조건으로 작용한다.  
      print "<1> 원판을 <A>에서 <C>로 옮긴다."  
   } else {  
      //1. [1:N-1] 원판을 A에서 B로 옮긴다.  
      hanoi(N-1, A, C, B)  
      //2. [N] 원판을 A에서 C로 옮긴다.  
      print "<N> 원판을 <A>에서 <C>로 옮긴다."  
      //3. [1:N-1] 원판을 B에서 C로 옮긴다.  
      hanoi(N-1, B, A, C)  
}  

#include <vector>

using namespace std;

vector<vector<int>> answer;
int count=0;

void hanoi(int n, int from, int by, int to);
void move(int from, int to);

vector<vector<int>> solution(int n) {
    hanoi(n,1,2,3);
    
    return answer;
}

void hanoi(int n, int from, int by, int to)
{
    if(n==1) move(from, to);
    else 
    {
        hanoi(n-1, from, to, by);
        move(from, to);
        hanoi(n-1, by, from, to);
    }
}

void move(int from, int to)
{
    answer.push_back(vector<int>());
    answer[count].push_back(from);
    answer[count].push_back(to);
    count += 1;
}

8 동적 프로그래밍 (Dynamic Programming)

■ dp 알고리즘

거스름돈 알고리즘을 효율성 문제로 통과하지 못했다.

#include <vector>
#include <algorithm>
#define mod 1000000007LL

using namespace std;

long long ableNum = 0;
int mList = 0;
vector<int> maxMoneyList;
vector<int> moneyValue;

void ableCount(int totMoney, int idx);

int solution(int n, vector<int> money) {
    int answer = 0;
    int totMoney = n;
    

    mList = money.size();
    
    sort(money.rbegin(), money.rend());
    
    moneyValue = money;
    
    for(int i=0; i<mList; i++)
        maxMoneyList.push_back(n/money[i]);
    
    for (int i=0; i<mList; i++) {
        if(i==mList-1) {
            if(totMoney==maxMoneyList[i]) ableNum++;
            break;
        }
        for (int j=1; j<=maxMoneyList[i]; j++) {
            totMoney -= moneyValue[i]*j;
            if(totMoney==0) { ableNum++; continue; }
            else if(totMoney<0) break;
            ableCount(totMoney, i+1);
            totMoney = n;
        }
        totMoney = n;
        ableNum %= mod;
    }
    
    ableNum %= mod;
    
    return answer=ableNum;
}

void ableCount(int totMoney, int idx)
{
    int totMoneyOri = totMoney;
    for(int i=0; i<maxMoneyList[idx]; i++)
    {
        totMoney -= moneyValue[idx]*i;
        if(totMoney==0) { ableNum++; return; }
        else if(totMoney<0) return;
        else if(idx!=mList) ableCount(totMoney, idx+1);
        totMoney = totMoneyOri;
    }
}

DP로 풀었더니 가능

큰 것 부터 생각했는데 경우의 수 줄여가며 나머지가 없이 딱 맞을 때를 생각했는데,
작은 것부터 생각해서 나머지 생각 없이 나눠서 더해주는 방식으로 가면되는 것.

#include <vector>
#include <algorithm>
#define mod 1000000007L

using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    int mSize = money.size();
    
    long *dp = new long[n+1];
    
    sort(money.begin(), money.end());
    
    for(int i=0; i<=n; i++)
        dp[i] = (i%money[0]==0) ? 1 : 0 ;
    
    for(int i=1; i<mSize; i++)
        for(int j=money[i]; j<=n; j++)
            dp[j] += dp[j-money[i]];
    
    return answer= (int)(dp[n] % mod);
}

■ 카카오 코드 캠핑 사각형 만들기 (내부에 점 있으면 안되는) 개수

x,y 중복된 값 제거 후 c++에선 unordered_set이라는 게 있다.
넓이가 상관없기 때문에 인덱스 압축을 시킨다. 그 후 dp로 내부 사각형안에 점 개수를 먼저 구하고, 압축한 사각형에서
사각형을 만들고 길이가 1인 경우 제외(정답에 추가) 그 외의 경우 dp를 참고해서 카운트가 0 내부에 없으면 정답에 추가

■ 카탈란 수 (Catalan number) 알고리즘 binomial = 조합

오일러가 "(n+2)-각형을 n개의 삼각형으로 나눌 수 있는 경우의 수"를 세는 문제를 제안하면서 처음 나타났다.
벨기에의 수학자 카탈란의 이름을 따서 정해졌다.

x = binomial(bin, 2n, n) - binomial(bin, 2n, n+1)
0이상의 n에대해서 x= (2n)!/n!(n+1)!
m.factorial(2*n) / (m.factorial(n+1) * m.factorial(n))

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 ...
0번째 부터

• 괄호의 개수구하기 문제
• 최적의 길 개수구하기
• 산만들기
• 대각선 피해가기
• 다각형을삼각형으로 나누기

long[][] dp = new long[31][31];
for(int i=0;i<=30;i++) 
	dp[i][0]=1;

for(int i=1;i<=30;i++)
	for(int j=1;j<=i;j++) 
		dp[i][j]=dp[i][j-1]+dp[i-1][j];

결과
1: 1
2: 1 2
3: 1 3 5
4: 1 4 9 14
5: 1 5 14 28 42
6: 1 6 20 48 90 132
7: 1 7 27 75 165 297 429
8: 1 8 35 110 275 572 1001 1430

long[] dp = new long[31]
for(f[1]=1,i=2;i<=30;i++)
	f[i]=(f[i-1]*(4i-2))/(i+1);

결과
1 2 5 14 42 132 429 1430 4862 . . . . .

for (int i = 1;i<=n;i++){
    dp[i] = dp[i-1]*((4*i-2) / (i+1));
}

http://blog.epthy.com/catalan-number/

■ 선입선출

-코어 비용의 LCM을 구해서 최대 그 범위안에서 for문 돌려도 효율성 문제에서 걸린다.
LCM이 n보다 클 경우 무의미하고 더 상황만 악화시키기 때문..
파라메트릭 서치 => 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것
바이너리 서치(이분 탐색)와 비슷한 것, 결과값을 미리 찍어놓고 이 결과가 올바른지 확인하는 방법.

#include <vector>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

int lcm(int a, int b) {
    if(b>a) a ^= b ^= a ^= b;
    return a * b / gcd(a, b);
}

int solution(int n, vector<int> cores) {
    int answer = cores[0];
    short cSize = cores.size();
    unsigned int timer = 0;
    int coresLCM = cores[0];
    int LCMperWork = 0;
    int i;

    if(n==0) return answer;
    
    for(i=1; i<cSize; i++)
        coresLCM = lcm(coresLCM, cores[i]);
    
    for(i=0; i<cSize; i++)
        LCMperWork += coresLCM/cores[i];
    
    if(n%LCMperWork==0) n=LCMperWork;
    else n%=LCMperWork;
    
    cout<<LCMperWork<<endl;
    
    while(n>0)
    {
        for(i=0; i<cSize; i++) {
            if(timer%cores[i] == 0) { 
                if(--n==0) { answer=i+1; break; }
            }
        }
        timer ++;
    }
    
    return answer;
}

수정 코드

#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

int lcm(int a, int b) {
    if(b>a) a ^= b ^= a ^= b;
    return a * b / gcd(a, b);
}

int solution(int n, vector<int> cores) {
    int answer = cores[0];
    short cSize = cores.size();
    unsigned int timer = 0;
    int coresLCM = cores[0];
    int LCMperWork = 0;
    int i;
    int j;
    vector<int> sortedCores;
    unsigned int passTime =0;
    unsigned int preCoreperWork = 0;
    unsigned int CoreperWork = 0;

    sortedCores = cores;
    sort(sortedCores.rbegin(), sortedCores.rend());


    
    if(n==0) return answer;
    
    for(i=1; i<cSize; i++)
        coresLCM = lcm(coresLCM, cores[i]);
    
    for(i=0; i<cSize; i++)
        LCMperWork += coresLCM/cores[i];
    
    if(n%LCMperWork==0) n=LCMperWork;
    else n%=LCMperWork;
    
    for(i=0; i<cSize; i++)
    {
        while(CoreperWork<n)
        {
            preCoreperWork = CoreperWork;
            CoreperWork=0;
​            passTime += sortedCores[i];
​            for(j=0; j<cSize; j++)
​            {
​                CoreperWork += passTime/cores[j];
​                if(passTime%cores[j]!=0) CoreperWork++;
​                if(CoreperWork>=n) break;
​            }
​        }
​        CoreperWork = preCoreperWork;
​        passTime -= sortedCores[i];
​    }
​    
​    timer = passTime;
​    n -= CoreperWork;
​    
​    while(n>0)
​    {
​        for(i=0; i<cSize; i++) {
​            if(timer%cores[i] == 0) { 
​                if(--n==0) { answer=i+1; break; }
​            }
​        }
​        timer ++;
​    }
​    
​    return answer;
}

■ 백트래킹 알고리즘

백트렉킹이란, 특정 노드에서 유망성(promising)을 점검하고,
유망하지 않다면 그 노드의 부모로 돌아가서(Backtracking) 다음 노드에 대한 검색을 계속하게 되는 절차입니다.

이처럼 백트렉킹 알고리즘은 전수조사 방법중 하나인 깊이우선탐색으로 시작합니다.
그리고 각 노드에서 유망하지 않은 노드들은 탐색 하지 않고 (이를 가지치기 Pruning 라고 합니다) 유망한 노드에 대해서만 탐색을 합니다.
즉 순서는 이렇게 진행됩니다.

처음 깊이 우선 탐색을 시작합니다.
각 노드가 유망한지 검사합니다.
만약 유망하다면 탐색을 계속합니다.
만약 유망하지 않다면 그의 부모 노드로 돌아가서 탐색을 계속합니다.(백트렉킹)

이와같은 방법을 이용하면 깊이우선탐색보다 검색하는 경우의 수를 줄일 수 있습니다.

n-queen 문제 체스판의 첫 칸부터 시작한다. 체스판에 Queen을 놓을 때 해당 칸이 놓을 수 있는지를 체크한다. 첫 Queen이라면 모든 칸에 놓을 수 있기 때문에 (0, 0) 칸에 놓았다고 가정하고 시작하자. 만약 놓을 수 있다면? 해당 칸에 Queen을 놓자. Queen을 놓은 자리가 체스판의 마지막 줄이 아니라면 다음 줄에 Queen을 놓기 위해 2번 작업으로 돌아가 다시 체크한다. Queen을 놓고 다음 줄로 넘어가는 이유는 Queen을 놓은 그 줄에는 다른 Queen을 놓을 필요가 없기 때문에 확인할 필요가 없기 때문이다. 만약 마지막 줄이라면 지금까지 놓은 자리는 N-Queen 문제의 답이 된다. 체스판의 모든 케이스에 대해서 확인했다면 정답이 되는 케이스 건수를 확인하면 된다.

코드를 보면 좀 더 쉽게 느껴질 수 있다. 메모리 공간을 절약하기 위해 체스판을 2차원 배열이 아닌 1차원 배열을 사용하였다. 아래 코드는 구현부 중 중요한 역할을 하는 2개의 메서드이다.

private void placeQueens(int board[], int h) {
    for (int idx = 0; idx < board.length; idx++) {
        if (canPlaceQueen(board, h, idx)) {
            board[h] = idx;
            if (h == board.length - 1) {
                resultCount++;
                printBoard(board);
            } else {
                placeQueens(board, h + 1);
            }
        }
    }
}
private boolean canPlaceQueen(int[] board, int h, int v) {
    int size = board.length;
    for (int idx = 0; idx < h; idx++) {
        if (board[idx] == v) {  //같은 라인에 놓인 경우
            return false;
        } else if (Math.abs(idx - h) == Math.abs(board[idx] - v)) {  //대각선 라인에 놓인 경우
            return false;
        }
    }

    return true;
}

placeQueen(): Queen을 놓는 시도
canPlaceQueen(): Queen을 해당 칸에 놓을 수 있는지 확인
board[h] = idx: (h, idx)에 Queen을 놓는 작업

내 코드

#include <cmath>
#include <vector>

using namespace std;

int answer = 0;

bool isCanPlace(vector<int>& bd, int row, int col);
void placeQueen(vector<int>& bd, int row);

int solution(int n) {
    vector<int> board(n, n+1);
    int bSize = board.size();

    placeQueen(board, 0);
    
    return answer;
}

bool isCanPlace(vector<int>& bd, int row, int col) {
    int bSize = bd.size();

    for(int parentRow = 0; parentRow < row; parentRow++) {
        if(bd[parentRow] == col) return false;
        else if(abs(parentRow-row)== abs(bd[parentRow]-col)) return false;
    }
    return true;
} 

void placeQueen(vector<int>& bd, int row) {
    int bSize = bd.size(); 
    for(int col = 0; col < bSize; col++) {
        if(isCanPlace(bd, row, col)) {
            bd[row] = col;
            if(row == bSize-1) { answer++; return; }
            else placeQueen(bd, row+1);
        }
    }
}

■ 최소 연쇄행렬곱셈 알고리즘 Minimum Multiplication

행렬 곱셈에는 결합 법칙이 성립함으로 행렬 A, B, C, D가 있다고 할 때, A × (B × C) × D 이런식으로 곱해도 결과값에는 영향을 주지 않는 다는 말이다. 하지만 A × B × C × D 로 계산 해서 풀었을 때와 A × ((B × C) × D) 이렇게 풀었을 때 중간에 곱셈을 하는 횟수가 달라진다.

예를 들어 다음과 같은 행렬이 있다고 할 때 A × B × C × D 20×2 2×30 30×12 12×8 결합법칙에 의해서 나올 수 있는 경우를 살펴보면 다음과 같아진다. A(B(CD)) 30 × 12 × 8 + 2 × 30 × 8 + 20 × 2 × 8 = 3,680 (AB)(CD) 20 × 2 ×30 + 30 × 12 × 8 + 20 × 30 × 8 = 8,880 A((BC)D) 2 × 30 × 12 + 2 × 12 × 8 + 20 × 2 × 8 = 1,232 ((AB)C)D 20 × 2 × 30 + 20 × 30 × 12 + 20 × 12 × 8 = 10,320 (A(BC)D 2 × 30 × 12 + 20 × 2 × 12 + 20 × 12 × 8 = 3,120

연쇄 행렬 곱셈의 구현의 핵심은 부분수열(subsequence) 을 이용하는 것이다.

간략히 설명한다면, 다음과 같다.

전체 행렬에 있어, 2개의 부분수열로 분리한다. 각 부분수열에 있어, 최소 비용을 구한 후 합쳐준다. 분리할 수 있을 때까지 부분수열의 길이를 늘려주면서 이 과정을 반복한다.

연쇄 행렬 곱셈의 점화식은 다음과 같다.

m[i][j] = 행렬 i번에서 j번까지의 최소 비용, d = 행렬 크기 => m[i][j] = m[i][k] + m[k + 1][j] + d[i - 1] + d[k] + d[j]

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n MatrixChainOrder(int dims[]) { // length[dims] = n + 1 n = dims.length - 1; // m[i,j] = Minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j] // The cost is zero when multiplying one matrix for (i = 1; i <= n; i++) m[i, i] = 0;

for (len = 2; len <= n; len++) { // Subsequence lengths
    for (i = 1; i <= n - len + 1; i++) {
        j = i + len - 1;
        m[i, j] = MAXINT;
        for (k = i; k <= j - 1; k++) {
            cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
            if (cost < m[i, j]) {
                m[i, j] = cost;
                s[i, j] = k; // Index of the subsequence split that achieved minimal cost
            }
        }
    }
}

}

시간복잡도는 O(n^3) 이 된다. 실제로 동작하는 것을 보면 쉽게 이해할 수 있다. 행렬 A, B, C, D 가 주어졌을 때 다음과 같다.

m[1][2] = 행렬 AB m[2][3] = 행렬 BC m[3][4] = 행렬 C~D

m[1][3] = 행렬 AC, m[1][1] + m[2][2] + .... m[1][3] = 행렬 AC, m[1][2] + m[3][3] + .... m[2][4] = 행렬 BD, m[2][1] + m[2][4] + .... m[2][4] = 행렬 BD, m[2][2] + m[3][4] + ....

m[1][4] = 행렬 AD, m[1][1] + m[2][4] + .... m[1][4] = 행렬 AD, m[1][2] + m[3][4] + .... m[1][4] = 행렬 A~D, m[1][3] + m[4][4] + ....

[구현방법 1] #include

using namespace std;

#define MIN(A, B) ((A)>(B)?(B):(A)) #define MAX_VALUE 9999999 #define MAX_SIZE 101

int M[MAX_SIZE][MAX_SIZE]; int d[MAX_SIZE];

int main() { int size = 4;

d[0] = 20, d[1] = 1, d[2] = 30, d[3] = 10, d[4] = 10;
 
for (int diagonal = 0; diagonal < size; diagonal++)
{
    for (int i = 1; i <= size - diagonal; i++)
    {
        int j = i + diagonal;
        if (j == i)
        {
            M[i][j] = 0;
            continue;
        }
        M[i][j] = MAX_VALUE;
        for (int k = i; k <= j - 1; k++)
            M[i][j] = MIN(M[i][j], M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]);
 
    }
}
 
/*결과 출력*/
cout << M[1][size] << endl;
for (int i = 1; i <= size; i++)
{
    for (int j = 1; j <= size; j++)
    {
        cout << M[i][j] << " ";
    }
    cout << endl;
}
return 0;

} Colored by Color Scripter cs (line 18) for (int diagonal = 0; diagonal < size; diagonal++) -> 구하려는 행렬 사이즈만큼 반복한다. (line 20) for (int i = 1; i <= size - diagonal; i++) -> i값은 상단 1부터 시작, 반복하는 횟수가 1씩 감소한다. (line 22) int j = i + diagonal; -> j값은 우측으로 diagnonal만큼 반복할때마다 이동한다. (line 2325) if (j == i) -> i와 j가 같을 경우 M[i][j] = 0 (line 2830) -> k=i~j-1만큼 반복하며, 공식을 적용하여 M[i][j]에 들어갈 곱의 최소값을 구한다.

[구현방법 2]

#include <iostream>
using namespace std;

int ChainedMatrix(int arr[], int n)
{
    int** DP;
    int i, j, k, L;
    int tmp;

    DP = new int*[n];
    for (i = 0; i < n; i++)
    {
        DP[i] = new int[n];
    }
     
    for (i = 1; i < n; i++)
    {
        DP[i][i] = 0;
    }
     
    for (i = 1; i < n; i++)
    {
        for (j = 1; j < n - i; j++)
        {
            k = i + j;
            DP[j][k] = INT32_MAX;
            for (L = j; L <= k - 1; L++)
            {
                tmp = DP[j][L] + DP[L + 1][k] + arr[j - 1] * arr[L] * arr[k];
                if (tmp < DP[j][k])
                {
                    DP[j][k] = tmp;
                    //cout << tmp << endl;
                }
                cout << tmp << endl;
            }
        }
    }
     
    return DP[1][n - 1];
}

int main(void)
{
    int arr[] = { 10,20,7,5,30 };
    int n;
    n = sizeof(arr) / sizeof(int);

    cout << ChainedMatrix(arr, sizeof(arr) / sizeof(int)) << endl;
}

http://egloos.zum.com/sakuragis/v/3322692 http://debuglog.tistory.com/76 http://twinparadox.tistory.com/183 http://huiyu.tistory.com/entry/DP-%EC%97%B0%EC%87%84%ED%96%89%EB%A0%AC-%EC%B5%9C%EC%86%8C%EA%B3%B1%EC%85%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

■ 인덱스 트리

date[] 배열의 값들을 리프노드로 하는 이진 트리를 구성하면 그 것이 바로 인덱스 트리이다.
그러면 이 인덱스 트리를 구성할 때는 배열으로 구현하면 된다.
트리를 배열로 구성하려면 한가지 조건만 알면 된다.
그 것은 바로 tree[x]의 자식노드는 이진트리이기 때문에 tree[2x], tree[2x+1] 이고 tree[y]의 부모노드는 tree[y/2]라는 점이다.
그렇다면 date[] 배열의 갯수를 N이라고 하자. 그러면 tree의 크기는 얼마나 잡아야 할까?
N의 갯수가 딱 2^x개 라면(완전이진트리를 만들 수 있다면) 2^(x+1)개를 잡으면 된다.
왜냐하면 리프노드들의 부모노드의 갯수는 (2^x)-1개 이기 때문이다.
즉, 2^(x+1)개면 인덱스 0를 안 쓴다고 하여도 리프노드와 부모노드들을 모두 포함할 수 있다.
만약 N의 갯수가 2^x < N <= 2^(x+1) 이라면 배열을 2^(x+2)개를 잡아야 한다.
잘 이해가 안된다면 그냥 max(N)*4로 배열 크기를 잡아버리면 된다.

결국 인덱스 트리를 사용하는 경우는 주어진 data 배열에서 구간 대표 값을 여러 구간에 대하여 계속해서 구해야 하고
data 배열이 계속해서 변경 될 때 사용한다.
아래코드는 구간합을 구하는 코드이다.
각 리프노드에는 update할 때마다 1씩 들어가게 된다.
아래코드는 재귀 방식으로 구현되어 있고
재귀로 구현한 코드는 3가지만 고려하면 된다.

1. 구하고자하는 구간과 현재 구간이 하나도 겹치지 않을 때
2. 구하고자하는 구간에 현재 구간이 완전이 포함될 때
3. 구하고자하는 구간과 현재 구간이 겹쳐 있을 때

[구현1]

#include <cstdio>
#include <cstring>

int N, M;
int arr[100001];
int inv[100001];
int tree[400001];

//(루트노드, 구하고자하는 범위, 현재 범위)
int get(int node, int left, int right, int start, int end){
    //구하고자하는 구간과 현재 구간이 하나도 겹치지 않을 때
	if (end<left || start>right) return 0;
    //구하고자하는 구간에 현재 구간이 완전이 포함될 때
	if (left <= start && end <= right) return tree[node];
    //구하고자하는 구간과 현재 구간이 겹쳐 있을 때
	return get(node * 2, left, right, start, (end + start) / 2) +
		get(node * 2 + 1, left, right, ((start + end) / 2) + 1, end);
}

//(루트노드, 업데이트할 리프노드, 현재 범위)
void update(int node, int num, int start, int end){
    //구하고자하는 구간과 현재 구간이 하나도 겹치지 않을 때
	if (num < start || end < num) return;
    //구하고자하는 구간에 현재 구간이 완전이 포함될 때
	if (start == end) {
		tree[node] = 1;
		return;
	}
    //구하고자하는 구간과 현재 구간이 겹쳐 있을 때
	update(node * 2, num, start, (end + start) / 2);
	update(node * 2 + 1, num, ((start + end) / 2) + 1, end);
	tree[node]++;
}

int main(){
	scanf("%d", &N);
	while (N--){
		scanf("%d", &M);
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= M; i++){
			scanf("%d", &arr[i]);
		}

		for (int i = 1; i <= M; i++){
			int tmp;
			scanf("%d", &tmp);
			inv[tmp] = i;
		}
	
		long long sum = 0;
		for (int i = 1; i <= M; i++){
			int now = inv[arr[i]];
			sum += get(1, now+1, M, 1, M);
			update(1, now, 1, M);
		}
		printf("%lld\n", sum);
	}
}

■ 부분합(Prefix Sums) 알고리즘

여기서 느낀점은 부분합을 구할때 부분적인 합을 누적시키므로 DP와 비슷하다는 점
sub[0]=a[0]
...
sub[1]=sub[0]+a[1]
sub[2]=sub[1]+a[2]
이런식으로 구해가면된다.
나중에 2-4, 3-10 이렇게 범위를 구하는 쿼리가 나오면 sub[4]-sub[1]= 2-4 이렇게 2번의 참조로 값을 구할 수 있으므로 효과적이다.

부분 평균 문제가 있었는데 평균의 수학적인 법칙으로
부분평균의 최솟값을 구하려면 길이가 2짜리 부분집합과 3짜리의 최소값만 고려하면 된다는 점이였다.

■ 자카드 유사 (카카오 블라인드 테스트) Union 합집합, Intersection 교집합 구하기
문자열 두개 일때 AB -> 숫자로 표현해서 카운트 시켜 구하는 방법 알파벳은 26개 A-> 0 Z ->25 0~675로 표현 가능 총 개수는 676

int cal(string s) {
    return 26 * (s[0] - 'A') + s[1] - 'A';
}

    int count1[676] = { 0, };
    int count2[676] = { 0, };
    for (int i = 0; i < s1.size(); i++) {
        count1[cal(s1[i])]++;
    }
    for (int i = 0; i < s2.size(); i++) {
        count2[cal(s2[i])]++;
    }
  int Union = 0, intersection = 0;
    for (int i = 0; i < 676; i++) {
        if (count1[i] > 0 || count2[i] > 0) { //합집합
            Union += max(count1[i], count2[i]);
        }

        if (count1[i] > 0 && count2[i] > 0) { //교집합
            intersection += min(count1[i], count2[i]);
        }
    }

같은 문자열의 최대를 더하면 합집합, 최소를 더하면 교집합

■ Trie 알고리즘 (자료구조) 트리기반의 자료구조 자동완성 시 유용

사용 용도 : 여러 개의 문자열 (ex. 문서파일) 에서 많은 양의 텍스트정보를 빠르고 효율적으로 검색하기 위해 사용.
retrieval 에 유용하다고 하여 Fredkin이 Trie 라고 명명함.

문자열에서 이진검색트리를 사용한다면 문자열의 최대 길이가 M이라면 O(MlogN)의 시간 복잡도
문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색가능

1. 자식 노드가 1개이며, 그 문자열이 $인 경우 (문자열 전체를 다 입력했을 때)
2. 자식 노드가 1개이며, 그 문자열이 추가된 횟수가 1인 경우(이 문자열 이후로는 오직 1번만 추가되었음을 의미)

트라이 예) {"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"} [ ]
[A] [D]
[AE] [AT] [DE] [DC]
[ATE] [ATV]
[ATES] [ATEV]

[구현방법1]

struct Trie {
    bool finish;    //끝나는 지점을 표시해줌
    Trie* next[26];    //26가지 알파벳에 대한 트라이
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }
    void insert(const char* key) {
        if (*key == '\0')
            finish = true;    //문자열이 끝나는 지점일 경우 표시
        else {
            int curr = *key - 'A';
            if (next[curr] == NULL)
                next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
            next[curr]->insert(key + 1);    //다음 문자 삽입
        }
    }
    Trie* find(const char* key) {
        if (*key == '\0')return this;//문자열이 끝나는 위치를 반환
        int curr = *key - 'A';
        if (next[curr] == NULL)return NULL;//찾는 값이 존재하지 않음
        return next[curr]->find(key + 1); //다음 문자를 탐색
    }
};

출처: http://jason9319.tistory.com/129?category=670441 [ACM-ICPC 상 탈 사람]

[구현방법2]

class Trie
{
public:
    set<char> words;
    vector<int> cnt;
    Trie() { cnt.resize(26); }
};

long long solve(vector<string> words)
{
    map<int, map<char, Trie> > trie;

    for (auto word : words)
    {
        word += '$';
    
        int st = 0;
    
        for (int i=0; i<word.length() -1; i++)
        {
            trie[st][word[i]].words.insert(word[i + 1]);
            if (word[i + 1] == '$') break;
            trie[st][word[i]].cnt[word[i + 1] - 'a']++;
            st++;
        }
    }
    
    long long ans = 0;
    
    for (auto word : words)
    {
        long long sum = 0;
        int st = 0;
    
        for (int i = 0; i < word.length(); i++)
        {
            sum++;
            if (trie[st][word[i]].words.size() == 1)
            {
                char spell = *trie[st][word[i]].words.begin();
                if (spell=='$' || trie[st][word[i]].cnt[spell - 'a'] == 1) break;
            }
            st++;
        }
        ans += sum;
    }
    return ans;
}

■ 목적지 문제

재귀로 했다가 시간초과 남/ 사이즈 m이나 n 500단위 넘으면 n=100까지는 할만하다.
그냥 배열로 경우의 수 dp 처리하는게 좋은 듯

#include <vector>
#include <iostream>

using namespace std;

int MOD = 20170805;
unsigned int answer = 0;
vector<vector<int>> cm;

void goDrive(int h, int w) {
    bool canRD[2];
    int distance;
    int cnt;
    
    canRD[0]=true; canRD[1]=true;
    
    if(h==cm.size()-1) canRD[1]= false;
    if(w==cm[0].size()-1) canRD[0]= false;
    if(!canRD[0]&&!canRD[1]) { answer++; return; }
    
    //go right
    if(canRD[0]) {
        distance=cm[0].size()-1 -w;
        cnt=0;
        
        for(int i=1; i<=distance; i++) {
            if(cm[h][w+i]==2) cnt++;
            else break;
        }
        
        if(cm[h][w+1]==0) goDrive(h, w+1);
        else if(cnt!=0&&distance!=cnt&&cm[h][w+cnt+1]!=1) goDrive(h, w+cnt+1);
    }
    
    //go down
    if(canRD[1]) {
        distance = cm.size()-1 -h;
        cnt=0;
        
        for(int i=1; i<=distance; i++) {
            if(cm[h+i][w]==2) cnt++;
            else break;
        }
        
        if(cm[h+1][w]==0) goDrive(h+1, w);
        else if(cnt!=0&&distance!=cnt&&cm[h+cnt+1][w]!=1) goDrive(h+cnt+1, w);
    }
}

int solution(int m, int n, vector<vector<int>> city_map) {
    answer = 0;
    MOD = 20170805;
    cm = city_map;
    
    goDrive(0,0);
    
    return answer = answer%MOD;
}

■ 페이지 교체 알고리즘

FIFO (First In First Out) - 이건 너무 쉽다 그냥 넣은 순으로 빼면 됨 - 인덱스 변수 하나만 둬서 처리가능 LRU (Least Recently Used) - 카카오 2017 블라인드 기출 - 나는 -1초기화 LRU배열을 하나 만든다음, for문 index를 맨처음부터 비교해서 맨처음 인덱스가 0, -1보다 크니까 넣고 인덱스니까 가장 낮은 숫자를 바꿔주면 됨 LFU (Least Frequently Used) - 가장 적은 참조횟수를 갖는 페이지를 교체, 같으면 LRU방법대로 코딩을 구현한다면 LRU처럼 인덱스배열을 만들되 LFU인덱스 배열을 하나 더 만들어 다시 들어올 때 스택을 쌓고 바뀌면 그인덱스에 0으로 초기화, 비교 시에 LFU를 먼저 확인하고 리스트 하나 더 만들어서 for문 돌면서 가장 작으면 리스트를 초기화하고 인덱스 넣고 같으면 리스트에 추가하고 해서 가장 작은 집합(리스트)를 구해서 LRU 해당 인덱스 부분만 for문으로 비교 가장 작은 걸 찾아서 바꿔준다.(이 때, 원래 값, LRU, LFU 3개 바꿔줘야함)

■ Max Heap과 Min Heap

우선순위 큐에서 최대값이 top 가장먼저 빠지는 큐를 Max Heap 최솟값이 top 가장먼저 빠지는 큐를 Min Heap이라고 하며 최댓값 최솟값을 계속 구해야하는 경우, 은근 엄청많이 쓰일 수 있다. cpp에선 기본이 Max Heap, Min Heap 구현 시 3번째 인자에 greater를 입력해주면된다.

■ 그리디(Greedy) 알고리즘

약간 무식한(단순한) 방법이긴 하지만 특정경우에선 dp도 무거울 경우가 있다. 이때 현재의 최선을 구해서 문제를 푸는 방식이 있다. 부분적인 최적해가 전체적인 최적해가 되는 경우 사용한다. 사용하는 알고리즘으로 [프림 알고리즘]과 [다익스트라 알고리즘]이 있다.

구명보트 문제도 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 오름차순으로 가장 몸무게가 큰 사람순으로 넣어보아 가장 작은 애까지 못 넣으면 다음 보트 이런식으로 구해야하기 때문에 그리디라 할 수 있다. 여기서 근데 2명이기 때문에 최대와 최소를 뽑았을 때 못 타면 최대는 무조건 혼자타야하기 때문에 못 타게되면 큰놈을 따로 보내고 또 최소 최대 비교하는 식으로 짜면됨. 무게제한이 240이고 최대최소가 무게 제한의 반일 때만 탈 수 있고 못타면 그 이상이므로 두명 불가 120최소 121최대 라면 240이 넘기에 120이 중복되지않는이상 둘 다 혼자타야함.

저울문제도 측정 할 수 없는 가장 작은 자연수를 구하기도 가장 작은 추 부터 더해가며, [더한 합+1 < 다음 추] 일때 그 더한 합+1 이 답이다. 만약 저 상황이 안나오면 [총 더한 합+1] 이 답이겠죠?

개념 코드 tempP = P // tempP 는 현재 남아있는 문제 while tempP not empty loop // tempP가 남아있으면 반복 수행 in subproblem tempP, decide greedy choice C // tempP서 greedy로 해결책 C를 선택(C는 현재 선택가능한 최적의 해) Add value of C to solution // 해결책에 C의 값을 적용 tempP := subproblem tempP reduced based on choice C // 남은 문제의 축소 end loop

활동 선택 문제, 활동 선택 문제는 쉽게 말하면 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 겁니다. dp는 C[i,j] = max(C[i,k] + C[k,j] + 1) 지만 모든 C를 구해야함 따라서 아래 그리드 알고리즘으로 구한다.

var activity = [[1,1,3], [2,2,5], [3,4,7], [4,1,8], [5,5,9], [6,8,10], [7,9,11], [8,11,14], [9,13,16]]; function activitySelection(act) { var result = []; var sorted = act.sort(function(prev, cur) { return prev[2] - cur[2]; // 끝나는 시간 순으로 정렬 }); var last = 0; sorted.forEach(function(item) { if (last < item[1]) { // 조건 만족 시 결과 집합에 추가 last = item[2]; result.push(item); } }); return result.map(function(r) { return r[0]; // map을 한 이유는 그냥 몇 번째 행동이 선택되었는지 보여주기 위함. }); } activitySelection(activity); // [1, 3, 6, 8] 일단 끝나는 시간 순으로 정렬한 후, 반복문을 돌며 집합의 끝나는 시간이 다음 행동의 시작 시간보다 작은 경우 집합에 추가하면 됩니다.

분할 가능 배낭 문제, 물건이 무거울 경우 쪼개서 넣을 수 있습니다. 즉 무게가 초과할 거 같은면 물건을 쪼개서 일부만 넣을 수 있다는 것이죠. 물건을 쪼갤 수 있다는 가정 하에서는 무엇부터 넣는 게 최선일까요? 무게 대비 가치가 높은 것들을 먼저 넣는 게 좋겠죠? 무게 제한도 50

var test = [[1,60,10], [2,100,20], [3,120,30]]; function fractionalKnapsack(item, w) { var sorted = item.sort(function(prev, cur) { return cur[1] / cur[2] - prev[1] / prev[2]; // 무게 대비 가치 순으로 정렬 }); var limit = w; var result = 0; for (var i = 0; i < sorted.length; i++) { var cur = sorted[i]; if (limit > 0) { if (limit >= cur[2]) { // 물건 무게가 제한 이하일 경우 limit -= cur[2]; result += cur[1]; } else { // 물건 무게가 제한 초과일 경우 result += cur[1] / cur[2] * limit; // 잘라서 넣음 limit = 0; } } else { break; } } return result; } fractionalKnapsack(test, 50); // 240

■ 다익스트라 알고리즘 (Dijkstra Algorithm)

그래프 상에 존재하는 두 노드 간의 최단거리를 구하고 싶을 때 이용할 수 있다. 그래프의 기초라고 할 수 있으며, 간단한 구현과 Min Heap(pq)을 이용한 구현이 있다.

최단거리는 최단거리로 이루어져 있다는 그리디(Greedy)한 생각에서부터 출발한다. 최단거리는 최단거리로 이루어져 있다는게 무슨뜻이냐면 예를들어 1번 정점에서 2번 정점으로 가는 최단거리의 경로가 1->4->3->2 으로 형성되어 있다고 가정해보자. 이때 1번정점에서 4번 정점으로 가는 최단거리와 1번정점에서 3번 정점으로 가는 최단거리는 1번 정점에서 2번 정점으로 가는 최단거리 내에 포함된다. 만약 1번 정점에서 4번 정점으로 가는 최단경로가 1->5->4라면 1번 정점에서 2번정점으로 가는 최단경로가 1->5->4->3->2가 되어야 하므로 모순이 된다. 고로 이 아이디어에 기반하여 정점 V로부터 최단거리를 구하는 과정에 구해지는 정점들을 이용하여 계속 최단거리를 구해나간다. 만약에 1->3의 최단거리를 구했다면 3에 연결 된 간선들은 최단경로의 후보가 될 수 있는 간선. 힙에 들어가는 거리는 지금까지의 누적거리 이기 때문에 정점 V에 연결 된 간선의 정보를 삽입할 때 'd[V]+해당 간선의 가중치'가 들어가야한다.

예제)

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int v, e, s, x, y, z, d[20002];
vector<vector<pair<int, int>>> vt;
int main() {
    scanf("%d%d%d", &v, &e, &s);
    vt.resize(v + 1);
    for (int i = 0; i < e; i++) {
        scanf("%d%d%d", &x, &y, &z);
        vt[x].push_back({ y,z });
    }    //인접리스트로 그래프를 형성
    memset(d, -1, sizeof(d));//거리가 담길 배열 d를 나올 수 없는 수(-1)로 초기화
    priority_queue<pair<int, int>> pq;//정보를 담을 힙(거리,정점)
    pq.push({ 0,s });//시작정점의 정보를 삽입
    while (pq.size()) {//pq가 빌 때까지 다익스트라 알고리즘 동작
        int here = pq.top().second;//현재 확인하는 정점
        int cost = -pq.top().first;//거리(비용) -를 붙이는 이유는 pq를 minheap으로 사용하기 위함
        pq.pop();
        if (d[here] != -1)
            continue;//이미 계산되었다면 넘어감
        d[here] = cost;//최단거리 정보를 갱신
        for (auto it : vt[here]) {
            int next = it.first;//다음 정점
            int acost = -it.second - cost;//누적 된 거리
            if (d[next] != -1)
                continue;//이미 계산되었다면 넘어감
            pq.push({ acost,next });
        }
    }
    for (int i = 1; i <= v; i++) {
        if (d[i] == -1)puts("INF");
        else printf("%d\n", d[i]);
    }//최단거리 출력
    return 0;
}

■ A* 알고리즘 (A* algorithm) 에이스타 알고리즘

게임에서 많이 사용되는 최단거리 길찾기 알고리즘이다. 다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. BFS의 가지치기 알고리즘이라 생각하면 된다.

핵심 개념

1. 최소가 되는 지점을 우선 탐색 (우선 순위 큐)
2. 휴리스틱 추정값 사용 ( F = G + H )
3. Open List / Closed List를 이용하여 노드 관리

G는 시작 노드에서 해당 노드까지의 실제 소요 경비값이고, H는 휴리스틱 추정값으로 해당 노드에서 최종 목적지까지 도달하는데 소요될 것이라고 추정되는 값. (H는 보통 좌표가 주어지면 장애물을 생각하는 방식과 아닌방식 이런식으로 계산하는데 Manhattan Method는 장애물을 무시하고 가로,세로로 최단거리 목적지 거리이다. 추정잔여거리(H)를 구할 수 없으면 이 알고리즘은 의미가 없다.)

열린목록 : 아직 조사하지 않은 데이터 닫힌목록 : 조사한 데이터

똑같이 시작 점을 C에 넣고 C에 넣은 노드에 연결된 노드를 O에 넣어 구하는데 열린목록(O)에 중복되는 노드가 있을 경우 F가 작은 쪽을 선택한다.

■ 프림 알고리즘 (Prim Algorithm)

프림 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 최소 신장 트리(MST, minimum spanning tree)를 찾는 그리디 알고리즘. 크루스칼 알고리즘과 같은 용도이지만, 응용 상황에서 두 알고리즘의 효율성이 달라질 수 있기 때문에 둘 모두 알아두는 것이 좋습니다. 최소 스패닝 트리에 대한 개념을 모른다면 크루스칼 알고리즘을 먼저 보고 오시는 걸 추천합니다.

step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. ) step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다. step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. (step 1에서 찾은 간선도 같이 T에 포함됩니다.) step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

[O(n^2) 코드]

#include <bits/stdc++.h>
#define PII pair<int,int>

using namespace std;

const int N = 1005, INF = 2140000000;

vector<PII> ad[N];  // ad[i] : i 노드가 출발지인 간선들, first = 목적지, second = 비용
int dist[N];        // dist[i] : 선택된 노드들과 i 노드가 연결되어 있는 간선의 비용 중 최소비용
bool selected[N];   // selected[i] : i 가 이전에 선택된 노드인가?

long long prim(int pn){
    long long ret = 0;
    for(int i=1; i<=pn; i++){ // 초기화
        dist[i] = INF;
        selected[pn] = false;
    }
    dist[1] = 0;              // 1번 노드부터 선택
    for(int i=1; i<=pn; i++){
        int now=-1, min_dist = INF;
        for(int j=1; j<=pn; j++){
            if(!selected[j] && min_dist > dist[j]){
                min_dist = dist[j];
                now = j;
            }
        }
        if(now<0) return (long long)INF; // 연결 그래프가 아님
        ret+=min_dist;
        selected[now] = true;
        for(auto edge: ad[now])
            dist[edge.first] = min(dist[edge.first], edge.second);
    }
    return ret;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    while(m--){
        int v1,v2,c;
        scanf("%d %d %d",&v1,&v2,&c);
        ad[v1].push_back(PII(v2,c));
        ad[v2].push_back(PII(v1,c));
    }
    printf("%lld",prim(n));
    return 0;
}

출처: http://weeklyps.com/entry/프림-알고리즘-Prims-algorithm [weekly ps]

[O(ELogV)코드]

#include <bits/stdc++.h>
#define PII pair<int,int>

using namespace std;

const int N = 1005, INF = 2140000000;

vector<PII> ad[N];  // ad[i] : i 노드가 출발지인 간선들, first = 비용, second = 목적지
priority_queue<PII, vector<PII>, greater<PII> > dist;        // dist : 선택될 가능성이 있는 간선들
bool selected[N];   // selected[i] : i 가 이전에 선택된 노드인가?

void add_edge(int node){
    for(auto edge: ad[node]){
        dist.push(edge);
    }
}

long long prim(int pn){
    long long ret = 0;
    for(int i=1; i<=pn; i++){ // 초기화
        selected[i] = false;
    }
    dist.push(PII(0,1));
    for(int i=1; i<=pn; i++){
        int now=-1, min_dist = INF;
        while(!dist.empty()){
            now = dist.top().second;
            if(!selected[now]){
                min_dist = dist.top().first;
                break;
            }
            dist.pop();
        }
        if(min_dist==INF) return (long long)INF; // 연결 그래프가 아님
        ret+=min_dist;
        selected[now] = true;
        add_edge(now);
    }
    return ret;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    while(m--){
        int v1,v2,c;
        scanf("%d %d %d",&v1,&v2,&c);
        ad[v1].push_back(PII(c,v2));
        ad[v2].push_back(PII(c,v1));
    }
    printf("%lld",prim(n));
    return 0;
}

출처: http://weeklyps.com/entry/프림-알고리즘-Prims-algorithm [weekly ps]

■ 완전 탐색 무식하게 모든 경우를 구해야하는 경우 이렇게 풀어야한다.

■ 깊이 우선 탐색 DFS(Depth First Search) 그래프 문제, 최단거리 문제에서 사용한다. <-> BFS 간단하게 이야기하면 갈수있을 때까지 간다입니다. 즉, 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라 갑니다. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아가면서 탐색이 이루어 집니다. 깊이 우선 탐색의 경우, 내가 지나간 곳을 계속해서 추적해야 하기 때문에 스택이나/ 재귀함수가 필요.

#include <stdio.h>

int n, min; // 맵의 크기와 최소값을 나타내는 변수 int map[10][10]; // 맵을 나타내는 2차원 배열

void DFS(int x, int y, int l) { // 도착 지점에 도착했을 경우 if (x == n - 1 && y == n - 1) { // 현재 최소값이 l보다 크면, l이 작은 것이므로 l를 최소값으로 지정 if (min > l) min = l; return; } map[y][x] = 0; // 방문했음을 표시하기 위해 0을 대입

// 위로 이동할 수 있다면 이동!
if (y > 0 && map[y - 1][x] != 0) DFS(x, y - 1, l + 1);
// 아래로 이동할 수 있다면 이동!
if (y < n - 1 && map[y + 1][x] != 0) DFS(x, y + 1, l + 1);
// 왼쪽으로 이동할 수 있다면 이동!
if (x > 0 && map[y][x - 1] != 0) DFS(x - 1, y, l + 1);
// 오른쪽으로 이동할 수 있다면 이동!
if (x < n - 1 && map[y][x + 1] != 0) DFS(x + 1, y, l + 1);
 
map[y][x] = 1; // 지나간 자리를 원상태로 되돌리기 위해 1을 대입

}

int main() { int i, j;

scanf("%d", &n);
min = n * n; // 모든 경로를 돌아다녀도 n * n이니, 이를 최소값으로 지정해둔다
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        scanf("%d", &map[i][j]);
DFS(0, 0, 1); // DFS 시작!
 
printf("최단 거리: %d\n", min);
 
return 0;

}

5 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 최단 거리: 13

■ 너비 우선 탐색 BFS(Breadth First Search)

• 그래프 문제 최단거리 문제에서 사용한다. <-> BFS 이 너비 우선 탐색은 먼저 가까운 정점부터 시작하여 가장 먼 정점까지 방문하기 시작합니다. 너비 우선 탐색은 방문한 정점의 위치를 기억하기 위해 큐가 필요.

#include <stdio.h>

int n, cnt; // 맵의 크기와 카운트 변수 int map[10][10]; // 맵을 나타내는 2차원 배열 int x[100], y[100], l[100]; // 좌표와 길이를 담을 배열

// 큐에 좌표 정보와 길이를 삽입하는 함수 void enqueue(int _x, int _y, int _l) { x[cnt] = _x; y[cnt] = _y; l[cnt] = _l; cnt++; }

void BFS(int _x, int _y) { int pos = 0;

// 시작점의 좌표 정보와 길이를 큐에 삽입한다
enqueue(_x, _y, 1);
// 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다
while (pos < cnt && (x[pos] != n - 1 || y[pos] != n - 1))
{
    // 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다
    map[y[pos]][x[pos]] = 0;
 
    // 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (y[pos] > 0 && map[y[pos] - 1][x[pos]] == 1)
        enqueue(x[pos], y[pos] - 1, l[pos] + 1);
    // 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (y[pos] < n - 1 && map[y[pos] + 1][x[pos]] == 1)
        enqueue(x[pos], y[pos] + 1, l[pos] + 1);
    // 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (x[pos] > 0 && map[y[pos]][x[pos] - 1] == 1)
        enqueue(x[pos] - 1, y[pos], l[pos] + 1);
    // 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
    if (x[pos] < n - 1 && map[y[pos]][x[pos] + 1] == 1)
        enqueue(x[pos] + 1, y[pos], l[pos] + 1);
 
    // 큐의 다음 순서의 지점을 방문한다
    pos++;
}
 
// cnt가 pos보다 크다면, 도착 지점에 무사히 도착한 것이라고 말할 수 있다.
// 위의 반복문은 도착점에 도착하게 되면 루프를 바로 빠져나오기 때문에,
// 길이를 삽입하는 큐의 마지막 요소가 최단 경로의 길이라고 할 수 있다.
if (pos < cnt)
    printf("최단 경로 길이: %d\n", l[pos]);

}

int main() { int i, j;

scanf("%d", &n);
min = n * n;
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        scanf("%d", &map[i][j]);
BFS(0, 0); // BFS 시작!
 
return 0;

}

■ 그래프 문제(Graph) 정점(Vertex)과 간선(Edge)로 이뤄진 문제 edge 수에 따라 sparse graph(희귀 그래프), dense graph(밀집 그래프). 종류- 무방향(무향) = 양방향 1->2 2->1, 방향(유향) 1->2 문제가 있다. 구현- 2가지 (인접행렬-밀집 그래프에 유리), (인접리스트-희귀 그래프에 유리)

양방향을 표현하기 위해 vector<vector> a; 이런 2차원 백터나 배열을 사용한다. 1->2, 2->1 케이스 둘다 받음 가중치(Weighted)가 없는 경우 1로 표현하고 있으면 적절하게 그 백터에 값에 넣으면 된다.

그래프가 disconnected거나 방향그래프일 경우 visited가 있는 경우 그 노드에서 시작하는 식(while문)으로 짜면된다.

■ DAG(Directed Acyclic Graph) 방향 사이클(Directed cycle)이 없는 방향 그래프. 우선순위가 있는 그래프라고 보기도 한다.

■ 그래프의 인접행렬(Adjacency Matrix) 인접행렬은 정점(V)이 n개일 때 N*N 이차원 배열로 나타낼 수 있다. 대각선 대칭이며 그래서 쓸대없는 공간이 있다. 가중치로 1이 아닌 다른 수를 적을 수도 있다. (0, 1 가중치 없으면) ad[?] 라고 표현한 ad는 인접행렬을 뜻함. vt = vertex(꼭지점,정점) edge = 선

■ 위상정렬(Topological Sort) 순서대로 해야하는 과정들이 있는데 그러한 것을 알고리즘화 시키고 프로그래밍화 시킨 것이 위상 정렬이다. A->C로 가기위해 단계적으로 치루어야 할 것이 있다. A를 수행해야 B, D를 할 수 있고, C는 B, E가 모두 수행이 완료되야 C를 수행할 수 있게 된다. 이러한 위상 정렬에서는 항상 그래프를 가로로 나열하였을 때, 왼쪽에서 오른쪽으로 모두 방향이 향할 수 있어야 하는데, 사이클을 이루는 경우에는 위상 정렬을 이룰 수 없게된다. 따라서 위상 정렬이 가능하다면 그 그래프는 DAG(Directed Acyclic Graph)의 형태를 띄어야 한다. 이 말은, 방향이 있는 그래프이고, 사이클이 존재해서는 안된다는 의미이다. 어떤 정해진 순서의 규칙의 조합을 구하는 문제에서 사용할 수 있다.

1. 이 그래프가 사이클이 있는지 확인한다. (보통의 경우 문제를 해결하는 경우에는 이 과정이 있다면 위상 정렬 자체를 시도하지 않을 것이지만)

2. 현재 정점에 들어오는 간선이 없다면 BFS라면 큐에 담아준다.

3. 큐에서 front원소를 빼고 front에 연결되어있는 정점들 간의 간선을 모두 삭제해준다. 이때 해당하는 다음 정점에 들어오는 간선이 없다면 큐에 담아준다. 이 과정을 정점의 개수만큼 반복한다.

4. 결국 이 과정을 반복하는 동안 큐에서 빠지는 front 순서대로가 위상 정렬의 결과이다.

[BFS로 위상정렬]

#include #include #include

using namespace std;

vector vc[1001]; // 그래프 형성을 위한 벡터 int line[1001]; // 자신에게 들어오는 간선들의 수 int result[1001]; // 최종 위상 정렬 결과 값

int main() { int n, m;

scanf("%d %d", &n, &m);
 
for (int i = 0; i < m; i++)
{
    int num, cur, prev;
 
    scanf("%d", &num);
 
    // 피디가 선호하는 순서가 없다면
    if (num == 0)
        continue;
 
    // prev를 먼저 담아주고 num - 1만큼 반복한다.
    scanf("%d", &prev);
    for (int j = 0; j < num - 1; j++)
    {
        scanf("%d", &cur);
 
        // cur은 prev에 의해 들어오는 간선이 생기므로 +1
        line[cur]++;
        // prev -> cur의 그래프가 생기는 과정
        vc[prev].push_back(cur);
        // cur이 다음 for문에서 prev가 된다.
        prev = cur;
    }
}
 
queue<int> q;
 
// 들어오는 간선이 없는 정점은 모두 queue에 담아준다.
for (int i = 1; i <= n; i++)
    if (line[i] == 0)
        q.push(i);
 
// 위상 정렬
for (int i = 0; i < n; i++)
{
    // 위상 정렬 도중에 큐가 비게 된다면 위상 정렬을 할 수 없다.
    if (q.empty())
    {
        printf("0");
        return 0;
    }
 
    // 큐의 front를 cur로 받아준다.
    int cur = q.front();
    q.pop();
 
    // 큐에서 front 순서대로가 위상 정렬의 결과 값이다.
    result[i] = cur;
 
    // cur->next로 연결되는 노드들에 대해 아래 코드를 수행한다. 
    for (int j = 0; j < vc[cur].size(); j++)
    {
        int next = vc[cur][j];
        // cur->next의 간선을 지우는 과정, 이때 간선의 수가 0이 되면 큐에 담아준다.
        if (--line[next] == 0)
            q.push(next);
    }
}
 
// 위상 정렬 결과 값을 출력한다.
for (int i = 0; i < n; i++)
    printf("%d\n", result[i]);
 
return 0;

}

출처: https://www.crocus.co.kr/716?category=209527 [Crocus]

[DFS로 위상정렬]

#include #include #include #include #define MAX_N 32000 using namespace std; vector<vector> vt; stack st; int n, m, x, y, visited[MAX_N + 1]; void dfs(int v) { visited[v] = true; for (auto i : vt[v]) { if (visited[i]) continue; dfs(i); } st.push(v); } int main() { scanf("%d%d", &n, &m); vt.resize(n + 1); for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); vt[x].push_back(y); } for (int i = 1; i <= n; i++) { if (!visited[i]) dfs(i); } while (st.size()) { printf("%d ", st.top()); st.pop(); } return 0; }

출처: http://jason9319.tistory.com/93 [ACM-ICPC 상 탈 사람]

[indegree 수를 이용한 방법] indegree란 한 정점에서 자신에게 들어오는 방향인 간선의 수입니다. 우리는 간선의 정보를 받을 때 모든 정점의 indegree의 개수를 세준 후 queue에 indegree가 0인 정점을 삽입해 줍니다. 정점의 횟수 만큼 반복문을 돌려 다음 작업을 반복합니다. -> 큐의 front를 추출하여 해당 정점에서 나가는 간선을 다 지워준 후 지워진 간선에 의하여 indegree가 0이 되는 정점들을 queue에 삽입해줍니다. (이때 간선을 지워준 다는 것은 간선의 종점인 정점들의 indegree의 개수를 -1 해줌으로 구현 가능합니다.) 하지만 우리가 정점의 횟수만큼 반복문을 돌리던 중 큐의 크기가 먼저 0이 되어 버린다면 사이클이 존재하므로 위상 정렬이 불가능하다는 결론이 나옵니다. 사이클에 속하는 정점들이 존재한다면 그 정점들은 모두 indegree가 1이상이라 큐에 들어가지 않기 때문입니다.

#include #include #include #include #define MAX_N 32000 using namespace std; int n, m, a, b, in[MAX_N + 1]; vector<vector> vt; priority_queue pq; int main() { scanf("%d%d", &n, &m); vt.resize(n + 1); for (int i = 0; i < m; i++) { scanf("%d%d", &a, &b); vt[a].push_back(b); in[b]++; } for (int i = 1; i <= n; i++) { if (!in[i]) pq.push(-i); } while (pq.size()) { int here = -pq.top(); pq.pop(); printf("%d ", here); for (int there : vt[here]) { in[there]--; if (!in[there]) pq.push(-there); } } return 0; }

출처: http://jason9319.tistory.com/93 [ACM-ICPC 상 탈 사람]

■ LCA (Lowest Common Ancestor) 알고리즘 - LG CNS에서 나옴 보통 트리에서 최소 공통 조상을 찾는 알고리즘 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 세그먼트 트리나 DP를 이용하여 구현할 수 있다. LCA 알고리즘의 시간 복잡도 :: O(lgN) 쿼리가 함께 존재할 경우 :: O(MlgN) 첫번째로 입력받은 정점과 간선을 이용하여 양방향 그래프를 생성한다. 그 후 depth와 조상을 가지는 트리를 생성한다. 이때 조상은 2^0, 2^1, 2^2, ... 의 조상이 누구인지 알 수 있도록 한다. depth와 2^k번째 조상을 가지고 있는 DP가 완성되었으면 이제 LCA(a,b) 즉, a와 b의 공통 조상이 누구인지 조사해야한다. 깊이가 더 깊은 노드를 깊이가 더 낮은 노드까지 노드를 올려준다.

#include #include #include #include

#define swap(a,b){int t = a; a = b; b = t;} #define MAX_NODE 100001

using namespace std;

// depth :: 노드의 깊이(레벨) // ac[x][y] :: x의 2^y번째 조상을 의미 int depth[MAX_NODE]; int ac[MAX_NODE][20];

typedef pair<int, int> pii; vector graph[MAX_NODE];

int max_level;

// DP(ac)배열 만드는 과정 void getTree(int here, int parent) { // here의 깊이는 부모노드깊이 + 1 depth[here] = depth[parent] + 1;

// here의 1번째 조상은 부모노드
ac[here][0] = parent;

// MAX_NODE에 log2를 씌어 내림을 해준다.
max_level = (int)floor(log2(MAX_NODE));
 
for (int i = 1; i <= max_level; i++)
{
    // tmp :: here의 2^(i-1)번째 조상
    /* 
        즉, ac[here][i] = ac[tmp][i-1]은
        here의 2^i번째 조상은 tmp의 2^(i-1)번째 조상의 2^(i-1)번째 조상과 같다는 의미
        예를들어 i = 3일때
        here의 8번째 조상은 tmp(here의 4번째 조상)의 4번째 조상과 같다.
        i =  4일때 here의 16번째 조상은 here의 8번째 조상(tmp)의 8번째와 같다.
    */
    int tmp = ac[here][i - 1];
    ac[here][i] = ac[tmp][i - 1];
}
 
// dfs 알고리즘
int len = graph[here].size();
for (int i = 0; i < len; i++)
{
    int there = graph[here][i];
    if (there != parent)
        getTree(there, here);
}

}

int main() { int n, m;

scanf("%d", &n);
 
// 양방향 그래프 형성
for (int i = 1; i < n; i++)
{
    int from, to;
    scanf("%d %d", &from, &to);
    graph[from].push_back(to);
    graph[to].push_back(from);
}
 
// make_tree에 1,0이 들어가기때문에 0은 -1로 지정
depth[0] = -1;
 
// 루트 노드인 1번 노드부터 트리 형성
getTree(1, 0);
 
// 쿼리문 시작
scanf("%d", &m);
 
while (m--)
{
    int a, b;
    scanf("%d %d", &a, &b);
 
    if (depth[a] != depth[b])
    {
        // depth[b] >= depth[a]가 되도록 swap
        if (depth[a] > depth[b])
            swap(a, b);
 
        // b를 올려서 depth를 맞춰준다.
        /* 
            이렇게하면 만약 max_level이 4라면
            2^4 -> 2^3 -> 2^2 -> 2^1 -> 2^0방식으로 찾아갈텐데
            결국 1, 2, 3, 4, 5 ..., 31까지 모두 찾는 방식과 같아진다.
            예를들어, i가 4일때와 1일때 만족했다 치면
            depth[a] <= depth[ac[b][4]]에 의해
            b = ac[b][4];가 되어 b는 b의 16번째 조상을 보고 있을 것이고
            depth[a] <= depth[ac[b][1]]에 의해(현재 b는 처음 b의 16번째 조상인 b로 바뀌었다.)
            b = ac[b][1];이 되어 b는 b의 2번째 조상을 보게 된다.
            즉, b의 16번째 조상의 2번째 조상을 보는 것이니 b의 18번째 조상을 보게 된다.
            (하고자 하는 말은 3번째, 7번째, 11번째 이런 조상들도 모두 볼 수 있다는 의미이다.)
        */
        for (int i = max_level; i >= 0; i--)
        {
            // b의 2^i번째 조상이 a의 depth보다 크거나 같으면 계속 조상을 타고간다.
            if (depth[a] <= depth[ac[b][i]])
                b = ac[b][i];
        }
    }
 
    int lca = a;
 
    // a와 b가 다르다면 현재 깊이가 같으니
    // 깊이를 계속 올려 서로 다른 노드의 조상이 같아질 때까지 반복한다.
    // 즉, 서로 다른 노드(2,3)의 조상이 1로 같다면 lca = ac[2][0]에 의해 2의 조상이 1임을 알 수 있고
    // 마찬가지로 ac[3][0] 또한 3의 조상이 1임을 알게되며 알고리즘이 끝이난다.
    if (a != b)
    {
        for (int i = max_level; i >= 0; i--)
        {
            if (ac[a][i] != ac[b][i])
            {
                a = ac[a][i];
                b = ac[b][i];
            }
            lca = ac[a][i];
        }
    }
 
    printf("%d\n", lca);
}
return 0;

}

이 코드에서 max_level의 의미는 문제에서 주어지는 최대 노드수에 log2를 취해 2^k번째 조상을 최대 몇번 갈 수 있는지 생각한 방식이다. 만약 노드 수의 최대가 100000이라면 2^16 = 65,536 이므로 max_level은 16임을 알 수 있다. 즉 아무리 최악의 경우라도 가장 아래의 노드가 2^16을 통해 루트 노드를 향해 갈 수 있지, 2^17을 해버리면 루트 노드를 넘어가버린다. DP를 만들기 위한 점화식을 살펴보면 다음과 같다. ac[here][i] = ac[ac[here][i - 1]][i-1]; 이것을 보기 좀 더 편하게 해서 tmp = ac[here][i-1]; ac[here][i] = ac[tmp][i-1];이라고 설정한다.

그리고 위의 알고리즘을 통해 양방향 그래프에서 단방향 그래프 즉, 트리로 생성하기 위해 if(there != parent)라는 요소를 추가하여 getTree(there, here);로 트리 및 깊이, 조상을 기록할 수 있게 한다. 만약 there == parent인곳도 dfs로 들어간다면 영원히 빠져나올 수 없는 재귀가 된다.

이 코드는 a와 b의 깊이를 같도록 해주는 코드이다. 여기서 의문점이 드는 상황이 2^k번째가 아닌 홀수번째들은 어떻게 파악하냐인데 for문을 잘 보면 max_level부터 시작하기 때문에(이로인해 O(lgN)이 가능하다.) 모든 조상에 대해 파악이 가능하고, depth를 맞출 수 있다. 그러한 내용은 주석을 통해 매우 자세히 설명해두었다.

이제 이 코드에 접어드는 순간 a와 b는 depth가 같아진 서로 다른 노드이다. 현재 lca는 a라고 가정을 해 두고 만약 a == b라면 아래와 같은 상황에서 나타난 lca이기에 그대로 lca는 a가 된다.

그 외의 경우에는 이제 깊이는 같고 노드가 서로 다르니 공통 조상을 찾으러 간다. 이때도 max_level부터 시작하기 때문에 모든 노드에 대해 조사가 가능하고, (이로인해 O(lgN)이 가능하다.) 결국 서로 같은 조상이 나오기 직전까지 반복 한 후 lca = ac[a][i]에 의해 서로 조상이 같은 다른 노드 a, b둘중 하나의 노드의 조상이 lca가 됨을 알 수 있다. (서브 트리의 노드 어디에서도 못만나도 결국 루트노드에서 만나게 되어있다.) 결국 LCA알고리즘을 이용하여 쿼리문 M개가 있는 문제를 해결하면 시간 복잡도는 O(MlgN)이 된다.

출처: https://www.crocus.co.kr/660 [Crocus]

[다른코드]

#include #include #include #include using namespace std; const int MAX = 18; // roundup log(2, 100000)

int N, M; int parent[100000][MAX]; // parent[i][k]: i의 2^k번째 부모 int depth[100000]; // 정점의 깊이 (루트의 깊이: 0) vector adj[100000]; // 인접 리스트

// dfs로 트리 제작하며 parent[i][0], depth 배열 채움 void makeTreeByDFS(int curr){ for(int next: adj[curr]){ if(depth[next] == -1){ parent[next][0] = curr; depth[next] = depth[curr] + 1; makeTreeByDFS(next); } } }

int main(){ // 트리 정보 입력 scanf("%d", &N); for(int i=0; i<N-1; i++){ int u, v; scanf("%d %d", &u, &v); u--; v--; adj[u].push_back(v); adj[v].push_back(u); } // 배열 초기화 memset(parent, -1, sizeof(parent)); fill(depth, depth+N, -1); depth[0] = 0; // 트리 만들기 makeTreeByDFS(0);

// parent 배열 채움
for(int j=0; j<MAX-1; j++)
    for(int i=1; i<N; i++)
        if(parent[i][j] != -1)
            parent[i][j+1] = parent[parent[i][j]][j];
 
// 쿼리 입력받기
scanf("%d", &M);
for(int i=0; i<M; i++){
    int u, v;
    scanf("%d %d", &u, &v);
    u--; v--;
 
    // depth[u] >= depth[v]가 되도록 필요에 따라 u, v를 스왑
    if(depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
 
    // 깊이 차(diff)를 없애며 u를 이동시킴
    for(int j=0; diff; j++){
        if(diff % 2) u = parent[u][j];
        diff /= 2;
    }
 
    // u와 v가 다르면 동시에 일정 높이만큼 위로 이동시킴
    if(u != v){
        // 높이 2^17, 2^16, ..., 2^2, 2, 1 순으로 시도
        for(int j=MAX-1; j>=0; j--){
            if(parent[u][j] != -1 && parent[u][j] != parent[v][j]){
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        // 마지막엔 두 정점 u, v의 부모가 같으므로 한 번 더 올림
        u = parent[u][0];
    }
 
    // LCA 출력
    printf("%d\n", u+1);
}

} [출처] 최소 공통 조상(Lowest Common Ancestor) (수정: 2017-02-04)|작성자 라이

■ 백 트레킹 - 순열,조합,중복순열,중복조합

순열은 아래와 같이 코딩 할 수 있다. 현재 값을 넣고 방문을 표시해준 후 다음 재귀를 반복하면 방문된 값들 빼고 계속 처리를 할 수 있다. 그 후 내가 출력 할 값이 m과 같아지면 출력을 하면 된다.

#include #include #include

using namespace std;

int n, m; vector vc; // 내가 출력할 것 bool visit[10]; // 그 숫자가 쓰는지확인

void dfs() { if (vc.size() == m) { for (auto i : vc) printf("%d ", i); printf("\n");

    return;
}
 
for (int i = 1; i <= n; i++)
{
    if (!visit[i])
    {
        visit[i] = true;
        vc.push_back(i);
        dfs();
        vc.pop_back();
        visit[i] = false;
    }
}

}

int main() { scanf("%d %d", &n, &m);

dfs();
 
return 0;

}

조합은 이전 수의 참조를 하면 안된다는 것을 생각하면 쉽게 구현 할 수 있다. 재귀에 인자가 들어가는데 현재 인덱스 다음 인덱스를 인자로 보내어 이전 값을 참조 못하도록 하자.

#include #include #include

using namespace std;

int n, m;

vector vc; void dfs(int cnt) { if (vc.size() == m) { for (auto i : vc) printf("%d ", i); printf("\n"); return; }

for (int i = cnt; i <= n; i++)
{
    if (vc.size() < m)
    {
        vc.push_back(i);
        dfs(i + 1);
        vc.pop_back();
    }
}

} int main() { scanf("%d %d", &n, &m);

dfs(1);
return 0;

}

출처: https://www.crocus.co.kr/1240?category=209527 [Crocus]

■ 세그먼트 트리(Segment Tree)

Segment Tree란 구간의 대표값을 이진 트리형태로 저장하는 자료구조 특정 값을 변경해서 합을 구할 때 유용함. 구간 a~b를 대표하는 노드의 왼쪽 자식은 a ~ (a+b)/2 구간을, 오른쪽 자식은 (a+b)/2+1 ~ b 구간을 대표 Segment Tree 에서 합이나 업데이트를 구하는 연산의 시간복잡도는 O(logN)입니다. (N : 수열의 길이) 이진 트리인 Segment트리의 높이만큼의 대표노드가 최대로 선택, 업데이트될 수 있기 때문 (log == log(2))

예) 1 10 3 6 5 6 4 7개의 수의 합을 세그먼트 트리로 나타내면 17/35 14/20 57/15 12/11 34/9 56/11 7/4 1/1 2/10 3/3 4/6 5/5 6/6

[구현코드]

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define ll long long

vector<ll> tree;
vector<ll> arr;

// 최초로 Segment트리의 대표값을 지정하는 함수
ll init(int node, int l, int r) {
    if(l==r) return tree[node]=arr[l];
    else return tree[node] = init(node*2, l, (l+r)/2)+init(node*2+1, (l+r)/2+1, r);
}

// idx 번째 값을 v로 업데이트하는 함수
ll update(int node, int l, int r, int idx, int v){
    if(idx < l || r < idx) return tree[node];
    if(l==r) return tree[node] = v;
    return tree[node] = update(node*2, l, (l+r)/2, idx, v) + update(node*2+1, (l+r)/2+1, r, idx, v);
}

// a번째 값부터 b번째 값 까지의 합을 구하는 함수
ll query(int node, int l, int r, int a, int b){
    if(b < l || r < a) return 0;
    if(a <= l && r <= b) return tree[node];
    return query(node*2, l, (l+r)/2, a, b)+query(node*2+1, (l+r)/2+1, r, a, b);
}

int main () {
    int N, M, K;
    scanf("%d%d%d", &N, &M, &K);
    arr = vector<ll>(N+1);
    tree = vector<ll>(N*4);
    for (int i=1;i<=N;i++) {
        scanf("%lld", &arr[i]);
    }
    init(1, 1, N);
    for(int i=1;i<=M+K;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a==1) {
            update(1, 1, N, b, c);
        } else {
            printf("%lld\n", query(1, 1, N, b, c));
        }
    }
    
    return 0;
}

■ 레이지 프로퍼게이션 (Lazy Propagation)

게으른 전파라는 뜻으로 게으르게 업데이트를 전파시켜서 O( logN )만에 Segment Tree에서 구간 업데이트를 달성하는 알고리즘 7개의 수 1, 10, 3, 6, 5, 6, 4에 대해 2번째 수부터 6번째 수 까지 10씩 더하라는 것 같이 구간을 업데이트해야 하는 질의가 있을 경우, 세그먼트 트리는 한번에 하나의 수를 업데이트 한다. 길이 N인 수열에 질의가 K번 들어올 때 하나의 수를 Segement Tree에서 업데이트하는데 O(logN)이 필요하므로 한 번의 질의에 최악의 경우 O(NlogN)연산이 필요, 따라서 전체 업데이트에 O(NKlogN) 연산 필요 레이지 프로퍼게이션을 사용하면 한번에 그 구간을 대표하는 노드를 수정해서 O(logN)만에 구간을 업데이트 할 수 있다.

예) 1, 10, 3, 6, 5, 6, 4에 대한 Segment Tree에 대해 구간 [1,6]에 5를 더하는 업데이트 1-4노드에 Lazy(5) 5-6노드에 Lazy(5)

구간 업데이트 정보를 반영하기 위해 조상노드의 lazy가 자손노드에 필요한 상황이라면 반드시 조상노드를 거쳐야 자손노드에 도달할 수 있기 때문에 조상 노드를 지날 때 마다 아래쪽으로 lazy(5)를 전파시키면 됩니다.

예를들어 위의 업데이트 경우에서 [2,4]의 합을 구하라는 질의가 들어온 상황

1. 먼저 구간[2,4]를 대표하는 노드를 찾아서 출발합니다.
2. 가던 도중에 lazy가 있는 조상 노드를 만났습니다. lazy를 해당 노드에 반영하고 (대표노드 값 20 + 5(구간 업데이트 정보인 lazy)*4(구간의 길이) = 40) 아래쪽 노드에 전파시켜준 뒤에 동일한 lazy가 두번 연속 전파되지 않기 위해 이 lazy를 0으로 수정합니다.
3. 위 과정을 반복합니다.
4. lazy를 전파하면서 아래쪽으로 내려오면서 [2,4] 구간을 대표하는 2노드, 3-4노드에 도달 이제 [2,4] 구간합을 계산하면 (10+51)15+(9+52)19=34로 올바른 값을 얻을 수 있습니다.

업데이트 함수(현재 노드){ //lazy 전파 업데이트 함수(왼쪽 자식 노드) 업데이트 함수(오른쪽 자식 노드) //여기! }

이때 //여기! 부분에서 재귀적으로 호출된 두 업데이트 함수가 종료된 상태입니다. 따라서 자식노드에 대한 업데이트가 완료된 상태이므로 자식 노드에는 올바른 값 저장되어 있을 것입니다. 또한 이 트리의 값은 자식 노드의 합을 나타내므로, 아래와 같은 코드를 /여기! 에 추가하여 현재 노드 또한 올바른 값을 얻을 수 있습니다. tree[현재 노드].value = tree[왼쪽 자식 노드].value + tree[오른쪽 자식 노드].value;

Segment Tree의 update와 sum함수에 lazy 전파 부분만 추가하면 쉽게 Lazy Propagation을 적용하여 구간 업데이트가 가능한 자료구조인 Segment Tree를 이용할 수 있습니다.

[구현코드]

#include <cstdio>
#define MAXN 1000010
#define ll long long
ll arr[MAXN];
typedef struct Tree{
    ll value, lazy;
}Tree;

Tree tree[3*MAXN];

//최초로 Segment트리의 대표값을 지정하는 함수
ll init(int node, int start, int end){
    if(start == end)
        return tree[node].value = arr[start];
    else
        return tree[node].value = init(node*2, start, (start+end)/2)+init(node*2+1, (start+end)/2+1, end);
}

//i~j 구간에 diff만큼 더해줄 때 SegmentTree를 업데이트 하는 함수
void update_range(int node, int start, int end, int i, int j, ll diff){
    //lazy가 남아있을 때
    if(tree[node].lazy != 0){
        tree[node].value += (end-start+1)*tree[node].lazy;
        if(start != end){
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy =0;
    }
    
    if(j < start || i > end) return;
    
    //대표 구간을 찾았을 때
    if(i <= start &&  end <= j){
        tree[node].value += (end-start+1)*diff;
        if(start != end){
            tree[node*2].lazy += diff;
            tree[node*2+1].lazy += diff;
        }
        return;
    }
    update_range(node*2, start, (start+end)/2, i, j, diff);
    update_range(node*2+1, (start+end)/2+1, end, i, j, diff);
    
    tree[node].value = tree[node*2].value+tree[node*2+1].value;
}

//i번째 값부터 j번째 값 까지의 합을 구하는 함수
ll sum(int node, int start, int end, int i, int j){
    if(tree[node].lazy != 0){
        tree[node].value += (end-start+1)*tree[node].lazy;
        if(start != end){
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy =0;
    }
    
    if(i> end || j < start) return 0;
    if(i <= start && end <= j) return tree[node].value;
    return sum(node*2, start, (start+end)/2, i, j)+sum(node*2+1, (start+end)/2+1, end, i, j);
}

int main(){
    int N, M, K;
    scanf("%d%d%d", &N, &M, &K);
    for(int i=1; i<= N; i++)
        scanf("%lld", &arr[i]);
    init(1, 1, N);
    for(int i=1; i<= M+K; i++){
        int t1, a, b;
        ll diff;
        scanf("%d", &t1);
        if(t1==1){
            scanf("%d%d%lld", &a, &b, &diff);
            update_range(1, 1, N, a, b, diff);
        }else{
            scanf("%d%d", &a, &b);
            printf("%lld\n", sum(1, 1, N, a, b));
        }
    }
    return 0;
}

출처: http://bowbowbow.tistory.com/4?category=159621 [멍멍멍]

■ 펜윅 트리 알고리즘(Fenwick Tree) - 바이너리 인덱스 트리 -펜윅 트리는 세그먼트 트리의 변형으로, update O(lgN)에 그리고 query를 O(lgN)에 수행 할 수 있으며 메모리는 세그먼트 트리에 비해 덜 소모됨. 펜윅 트리의 핵심은 구간 합 대신 부분 합만을 빠르게 계산할 수 있는 자료 구조를 만들어도 구간 합을 계산할 수 있다는 것이다. (이때 부분 합은 0k까지 합이고 구간 합은 ab까지 합을 의미한다.) 17/35 14/20 - 12/11 - 56/11 - 1/1 - 3/3 - 5/5 - 우선 펜윅 트리는 비트를 가지고 놀기 때문에 인덱스를 0번부터가 아닌 1번부터로 바꾸어준다.(코드에서 +1만 하면된다.) 만약 인덱스 3~6번 사이의 구간합을 구하고 싶다면 어떻게 해야 할까? (1-4) + (5-6) - (1-2)를 하면 3-6의 구간합을 얻을 수 있다.

[구현코드]

#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

ll sum(vector<ll> &tree, int i)
{
    ll ans = 0;
    while (i > 0)
    {
        ans += tree[i];
        i -= (i & -i); // 최하위 비트 지우기 
    }

    return ans;
}

void update(vector<ll> &tree, int i, ll diff)
{
    while (i < tree.size())
    {
        tree[i] += diff;
        i += (i & -i);
    }
}

int main()
{
    int n, m, k;

    scanf("%d %d %d", &n, &m, &k);
     
    vector<ll> arr(n + 1);
    vector<ll> tree(n + 1);
     
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &arr[i]);
        update(tree, i, arr[i]);
    }
     
    m += k;
     
    while (m--)
    {
        int num;
        scanf("%d", &num);
     
        if (num == 1)
        {
            int index;
            ll val;
            scanf("%d %lld", &index, &val);
     
            ll diff = val - arr[index];
            arr[index] = val;
     
            update(tree, index, diff);
        }
     
        else if (num == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
     
            printf("%lld\n", sum(tree, right) - sum(tree, left - 1));
        }
    }
     
    return 0;
}

출처: https://www.crocus.co.kr/666 [Crocus]

■ 플러드필 Flood Fill (= 시드필 Seed Fill)

다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다.
이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며,
바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다.

대부분 큐나 스택과 같은 자료구조를 사용한다.

4방향 재귀적 플러드 필, 8방향 재귀적 플러드 필

u와 v로 연결된 에지가 주어지는게 아니라
에지가 이런 문제처럼 상하좌우로만 연결되있을때 쓰는 방법

int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
//우좌하상을 나타내는 인덱스배열
문제에 따라 8방면을 봐야되면 해당 좌표를 추가해주면 됩니다.

for (int k = 0; k < 4; k++) {
	int nr = r + dr[k], nc = c + dc[k];
	if (0 <= nr && nr < n && 0 <= nc&& nc < n&&!check[nr][nc]&& arr[nr][nc]) {
		cnt+=dfs(nr, nc)+1;
	}
}

■ 시뮬레이션 문제(Simulation)

알고리즘을 풀 때 모든 과정이 제시되어 그 과정을 거쳐 나온 결과를 추론하는 문제입니다. 시뮬레이션은 설명해 준 대로 쭉 이행하면 됩니다. 어떠한 작업을 수행할지 적혀 있으면 시뮬레이션 문제이고 없으면 전체 탐색 문제입니다.

• 문제 A - 요구하는 것이 같으므로 시뮬레이션이라고 볼 수 있다. 3만원, 5만원, 8만원의 가치가 있는 물건이 있습니다. 여기서 2개의 물건을 들고 갈 수 있습니다. 가치의 합이 최대가 되도록 고르려고 합니다. 여러분이 들고 돌아갈 수 있는 최대 가치의 합계는 얼마인가요?

• 문제 B - 시뮬레이션 3만원, 5만원, 8만원의 가치가 있는 물건이 있습니다. 여기서 2개의 물건을 들고 갈 수 있습니다. 가치의 합이 최대가 되도록 비싼 순서대로 2개를 들고 돌아왔습니다. 여러분이 들고 온 물건의 가치 합계는 얼마인가요?

■ 이진탐색, 이분탐색(Binary Search)와 파라메트릭 서치(Parametric Search)

우선 이진탐색은 O(N)-> O(logN) 가능하게 하는 서칭기법 가운데 값을 기준으로 비교를 해 나가면서, 비교의 범위를 절반씩 줄여 나갈수 있게 된다. 그러기 위해 정렬이 필수다.

int bSearch(int *arr,int size, int value) { int left = 0; int right = size - 1; int mid;

while (left<right) {
    mid = (left + right) / 2;
    if (arr[mid] == value) return mid;
    else if (arr[mid] > value) right = mid - 1;
    else left = mid + 1;
}
return -1;

}

int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; printf("%d에 %d가 존재합니다.\n", bSearch(arr,10,3),3); printf("%d에 %d가 존재합니다.\n", bSearch(arr, 10, 100), 100); return 0; }

파라매트릭 서치는 배열의 들어가 있는 값이 아닌, 수직선 상 위에서 내가 원하는 값을 이진탐색으로 찾아가는 느낌으로 이해하는 것이 이해하기 편하다. 주로 내가 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고싶어 할 때 사용할 경우가 많다. 내가 가지고 있는 값이 아닌 값의 범위를 기준으로 답을 탐색한다. 그러기 위해서는 답에 가까워 질수 있게 만드는 compare 함수를 적절히 만들어야 한다.

간단한 예를 들어보면, 방정식을 푼다고 생각해 보자. Y= X^4+X^3+X^2+X 라는 방정식의 Y값이 주어졌을 때 0~10 사이에 값중 알맞는 것을 소수점 5자리 이내의 오차범위에서 구해보자고 하자. ex) Y= 15 1- 10 이므로 MID X= 5 625+125+25+5 = 780 더 작아야함. 1 X=2.4999995 4.9999999 39+16+6+3=64 더 작아야함 ...반복

파라메트릭 문제 - 입국심사 문제 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다. 상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

그냥 무작정 찍기로 총 걸린 시간을 찍는다. 이 때 이분탐색으로 찍는다. 최대시간은 제일 오래걸리는 심사대*인원수 이다. (초기 right 값)

l=1
r=60 mid = 30 tot = 30/7 + 30/10 = 7 //총 걸린시간으로 몇명이 지나갔는지 확인 ( 30분동안 최대 몇명이 지나갈수있는가 ) ->몫만 있으면 됨 이시간안으로는 총인원이 턱도없으면 시간을 늘려줘야되고

총인원보다 많은인원을 통과시킬수있으면 시간을 줄이고 총인원보다 같더라도 시간을 줄여봐야한다. 왜냐하면 어느게이트에 갔냐에 따라서 시간이 더 줄어들수있기 때문

right= 29 left=1 mid=15 tot=15/7+15/10=3 //모자름

r=29 l=16 m=22 tot=22/7+22/10 = 5 //모자름

r=29 l=23 m=26 tot=26/7+26/10=5 //모자름

r=29 l=27 m=28 tot=28/7+28/10=6 //충분

r=27 l=27 m=27 tot=27/7+27/10=5 // 모자름

●이분탐색 : 답을 찍어보는 경우에 사용된다 ●이분탐색 다음 타겟 정하기 :

최적의 해를 구하는 과정에서 내가 구한값이 너무 작으면 더큰게 필요하니까 left=mid+1 해주고 구한값이 너무 크면 더 작은게 필요하니까 right=mid-1 해주고 구한값으로 만족하다면 ? (==일때는) -> 최적의해가 최소값이라면 right=mid-1 해서 더 줄여서 시도해본다. 최적의 해가 최대값이라면 left=mid+1 해주면된다. 어차피 이분탐색은 반복되더라도 l<=r일때까지만 하고 logN의 시간복잡도이기 때문에 끝까지 가봐도 시간이 충분하다.

[나의 풀이] #include

using namespace std;

long solution(int n, vector times) { int tSize=times.size(); long answer = 0, s=0, e=1e9*n, mid, doneN; //e= Max takeTime * peopleNum

while(s<e) {
    mid=(s+e)>>1;
    doneN=0;
    for(int i=0; i<tSize; i++) doneN += mid/times[i];
    if(doneN>=n) e=mid;
    else s=mid+1;
}
    
return answer=s;

}

■ 비트 마스크(Bit Mask)

■ 외판원 문제(TSP:traveling salesperson problem) 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다.

[구현] #include #include

#define MAX_NUM 987654321

using namespace std;

int city[16][16]; int cache[16][65536];

int num;

int tsp(int cur, int visited) {

// 다 방문 했다면
if (visited == (1 << num) - 1) {
    return city[cur][0];
}
 
int & ret = cache[cur][visited];
 
// 메모이제이션 반환
if (ret != 0) {
    return ret;
}
 
ret = MAX_NUM;

for (int i = 0; i < num; i++) {
    // 방문했으면 패스
    if (visited & (1 << i))
        continue;
 
    // 갈 수 없는 길이라면 패스
    if (city[cur][i] == 0)
        continue;
 
    ret = min(ret, tsp(i, visited | (1 << i)) + city[cur][i]);
}
return ret;

}

int main() { cin >> num;

for (int i = 0; i < num; i++) {
    for (int j = 0; j < num; j++) {
        cin >> city[i][j];
    }
}

cout << tsp(0, 1);
 
return 0;

}

출처: http://moohyo97.tistory.com/entry/알고리즘-외판원-문제-해설 [물음표 공작소]

■ 메모이제이션(memoization) 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

4단고음, 1만들기 문제 ++로 이루어진 문자열이 있을 때 시작값은 1이고 는 x3 +는 +1값을 증가시킨다. (+(++)+) 와 같이 순서만 맞으면 모두 valid한 문자열이다.
이렇게 문자열을 만들 때 n값이 되는 문자열의 수를 구하는 문제이다.
ex) *++ = 5, **++++ = 13, ++++ = 17 뒤에서부터 문자를 채운다고 생각하면 *는 항상 +가 2개 이상 채워졌을 때부터 사용가능하다. 따라서 현재까지 +를 몇 개 사용했는지와 숫자 몇을 만들어야 하는지 2개를 인자로 가지고 가면 완전탐색함수를 구현 할 수 있고 map을 이용하여 메모이제이션 가능하다.

내용 추가) 백준 1로 만들기 문제와 비슷하게 생각하면 된다. 현재 n을 가지고 있고 적절한 - 연산과 / 연산으로 1을 만들고 싶은 상황이다. 하지만 문제 조건에 의해서 / 연산은 - 연산을 2스택 이상 모았을 경우에만 사용가능하다. 또한 1이 되었을 때 - 연산으로 모은 스택을 / 연산으로 다 활용하여 남은 스택이 0이 되야 한다. 따라서 - 연산을 최대 40번만 사용 가능하다. (*******++++...이 제일 작음 이때 최대로 붙이는 문자열이 20개) 이러한 제한을 두고 완전탐색 코드를 짠후 stl map을 이용하여 메모이제이션을 한다. 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> mp;
int solve(int b, int g){
	if(b>=40)
		return 0;
	if(g==1)
		return b==0;
	if(g<=1)
		return 0;
	if(mp.count({b, g})!=0)
		return mp[{b, g}];
	mp[{b, g}]=solve(b+1, g-1);
	if(b>1&&g%3==0)
		mp[{b, g}]+=solve(b-2, g/3);
	return mp[{b, g}];
}
int solution(int n) {
	return solve(0,n);
}

■ 최단거리 3대 플로이드워셜,벨만포드 알고리즘

■ 문자열 4대 아호코라식, suffix array

■ Best First Search(최선 우선 탐색), 레드블랙트리

■ 라면공장 (Heap 문제) 알고리즘을 풀기전에 충분히 고민하지 않아 복잡하게 생각해 이상한 방향으로 흘러간 케이스였다. 케이스를 지워가며 문제를 풀려하는 방식을 지양해야겠다는 것도 피드백됬다. 그냥 단순히 최소의 경우이므로 stock==시간 보다 작은 supplies 공급량만 pq에 넣고 top 빼내고를 반복하면 되는 문제였다.

■ 마방진(Magic Square)

n2개의 수를 가로, 세로, 대각선 방향의 수를 더하면 모두 같은 값이 나오도록 n × n 행렬에 배열한 것이다. 마법진(魔法陣), 낙서(洛書)라고도 한다. 합은 n(n^2 + 1) / 2 그 원리는 여기에 들어가는 숫자들의 평균을 가로, 혹은 세로 개수로 곱한 값이다. 1~n^2까지 합이 n^2(n^2+1)/2 이므로 여기서 한줄에 들어가는 수의 합은 n으로 나눠준 n(n^2 + 1) / 2 이 되는 것이다.

① 1행 가운뎃 열에 숫자 1을 놓는다. 3 by 3이면 2열에, 5 by 5면 3열에. ② 해당 위치에서 한 칸 왼쪽으로(열 감소), 한 칸 위쪽으로(행 감소) 이동한다. ③ 만약 해당 줄의 끝에 다다라서 더 이상 이동할 수 없을 때 그 줄의 반대쪽 끝으로 이동한다. (ex - 3행 1열일 경우 >> 2행 5열, 1행 2열일 경우 >> 5행 1열) ④ 만약 이동한 위치에 이미 숫자가 놓여져 있다면, 그 자리에서 한 칸 아래로(행 증가) 이동한다. ⑤ 이동한 위치에 2를 놓는다. ⑥ 2~5의 과정을 계속 반복하여 25를 놓을 때까지 진행한다.

1. 정사각형의 맨 아랫줄 가운데에 숫자 1 을 둔다.
2. 이전 숫자 위치에서 오른쪽 아래칸이 비어 있으면 다음 숫자를 채운다.
3. 이전 숫자 위치에서 오른쪽 아래칸이 채워져 있으면 이전 숫자의 위칸에 다음 숫자를 채운다.
4. 오른쪽 아래칸이 사각형의 영역 밖이면 다음의 규칙을 따른다. 4-1. 수평 및 수직으로 이동해서 마지막 칸이 비어 있으면 해당 칸에 숫자를 채운다. 4-2. 수평 및 수직으로 이동해도 칸이 없는 경우 이전의 숫자 위치 위쪽 칸에 다음 숫자를 채운다.

*** 홀수 요거임 가운데 테두리 변에 1을 시작 숫자를 둔다. 1행 가운데라면 왼쪽 위나 오른 쪽위 처럼 (변에서 나가게) 대각선으로 이동 만약 다음 것이 행이 나가면 반대 행 지점으로, 열이 나가면 반대열 가다가 이미 체워진 곳이면 진행방향의 반대쪽(아래)에 체우고 다시 시작 만약 열과 행이 모두 나가버리면 체워진것 처럼 진행방향 반대쪽(아래)에 체우고 다시시작.

ex) 해커랭크 코드 이건 나올 수 있는 경우 가지고 구한 케이스 #include <bits/stdc++.h>

using namespace std;

// Complete the formingMagicSquare function below. int formingMagicSquare(vector<vector> s) { int sum = 0, res=1000; int mM[8][3][3] = { {{6,1,8}, {7,5,3}, {2,9,4}},

    {{8,1,6},
    {3,5,7},
    {4,9,2}},

    {{2,7,6},
    {9,5,1},
    {4,3,8}},

    {{4,3,8},
    {9,5,1},
    {2,7,6}},

    {{2,9,4},
    {7,5,3},
    {6,1,8}},

    {{4,9,2},
    {3,5,7},
    {8,1,6}},

    {{6,7,2},
    {1,5,9},
    {8,3,4}},

    {{8,3,4},
    {1,5,9},
    {6,7,2}},
};

for(int i=0; i<8; i++) {
    sum=0;
    for(int j=0; j<3; j++) {
        for(int k=0; k<3; k++) {
            sum+= abs(mM[i][j][k]-s[j][k]);
        }
    }
    res = min(res, sum);
}

return res;

}

int main() { ofstream fout(getenv("OUTPUT_PATH"));

vector<vector<int>> s(3);
for (int i = 0; i < 3; i++) {
    s[i].resize(3);

    for (int j = 0; j < 3; j++) {
        cin >> s[i][j];
    }

    cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

int result = formingMagicSquare(s);

fout << result << "\n";

fout.close();

return 0;

}

■ 프로그래머스 순위 문제 : 그래프 문제 엄청 무식하게 풀었다. 우선 단방향이고 이긴리스트 진리스트를 각 번호 노드에 넣어둔다. 이긴리스트로 DPS로 가장 긴 거리를 구한다음 그 거리만큼 전체탐색 반복문을 돌려 내가 이긴 노드의 이긴 정보랑 진 정보 다 가져다 내꺼에 넣는다. 진정보 이긴정보 + 1(자기자신) == 모든정보 에 해당하는 결과값이 나오면 +1해준다.
요즘 C# 공부하느라 C#으로 풀었더니 더 어려운 것같다.

[C# 코드] using System; using System.Linq; using System.Collections.Generic;

public class RankNode { public HashSet winList; public HashSet loseList;

public RankNode() {
    winList = new HashSet<int>();
    loseList = new HashSet<int>();
}

}

public class Solution {

public List<RankNode> rL = new List<RankNode>();

public int getDepth(int d, List<int> t) {
    if(t.Count==0) return d;
    
    for(int i=0; i<t.Count; i++) return getDepth(d+1,rL[t[i]].winList.ToList());
    return 0;
} 

public int solution(int n, int[,] results) {
    int answer = 0;
    int maxDepth = 0;
    
    //Input
    for(int i=0; i<=n; i++) rL.Add(new RankNode());
    
    for(int i=0; i<results.Length*0.5; i++) {
        rL[results[i,0]].winList.Add(results[i,1]);
        rL[results[i,1]].loseList.Add(results[i,0]);
    }
    
    //MaxDepthFind
    for(int i=1; i<=n; i++) {
        maxDepth = Math.Max(getDepth(0, rL[i].winList.ToList()),maxDepth);
    }
    
    //SeachingToMaxDepth
    for(int i=0; i<maxDepth; i++) {
        for(int j=1; j<=n; j++) {
            RankNode rN = rL[j];

            foreach(var w in rN.winList.ToList()) foreach(var wSub in rL[w].winList.ToList()) rN.winList.Add(wSub);
            foreach(var l in rN.loseList.ToList()) foreach(var lSub in rL[l].loseList.ToList()) rN.loseList.Add(lSub);
        }
    }
    
    //Result
    for(int i=1; i<=n; i++) {
        if(rL[i].winList.Count+rL[i].loseList.Count+1 == n) answer++;
    }
    
    return answer;
}

}

■ 그래프 문제 : 사이클 그래프 문제를 풀다 보면 '사이클을 찾아라', '사이클일 경우는 안된다' 라는 조건이 걸린 문제를 종종 볼 수 있습니다. 만약 모든 정점에 대해서 dfs를 돌려 사이클을 찾게된다면 O(V(V+E))라는 시간으로 상당한 시간이 걸리게 될겁니다. 사이클 여부는 DFS트리 한번으로 찾을 수 있습니다.

결론부터 얘기하자면 사이클은 back_edge가 존재할 때 생기고, 이 back_edge의 유무를 찾아주면 됩니다.

단방향 그래프에서 사이클을 어떻게 찾는지 알아보겠습니다.

이런 그래프가 있을 때 빨간 간선과 같이 back_edge가 존재하면 사이클이 존재한다는 얘기입니다. 서브스패닝트리의 루트에 도달할 수 있으면 다시 루트부터 내려가기 때문에 사이클이 생깁니다. vector<vector> v; vector visit; vector check; int dfs(int u) { if (visit[u]) return 1; if (check[u]) return 0; check[u] = 1; visit[u] = 1; for (int i = 0; i < v[u].size(); i++) { if (dfs(v[u][i])) return 1; } visit[u] = 0; return 0; }

이런 식으로 코드를 작성할 수 있습니다. 현재 dfs재귀중이라면 그 정점은 방문 중인 정점입니다. 현재 방문 중인 정점을 visit배열에 기록을 해줍니다. dfs이기 때문에 방문한 정점은 2번 방문하면 안됩니다. 그래서 check배열에서 방문 여부를 저장해줍니다. 만약 visit에 기록된 배열을 다시 방문한단얘기는 그 에지는 backedge란 얘기고 즉 사이클이 있단 얘기가 됩니다.

다음은 양방향 그래프에서의 사이클 찾기입니다. 양방향 그래프에서 사이클 찾기는 방문순서를 기록해줍니다. 부모를 제외한 에지들 중에 방문순서가 먼저인 정점이 있다면 이미 방문하나 정점이고, 사이클이 존재한다는 얘기입니다.

정점 안 숫자는 방문한 순서입니다. 부모가 아닌 에지인데 방문순서가 먼저라면 그 에지는 벡에지가 됩니다. void go(int u, int p) { for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (p != v) { if (d[v] == 0) { d[v] = d[u] + 1; go(v, u); } else if (d[u] > d[v]) { printf("벡에지입니다"); } } } } 이런식으로 구할 수 있습니다.

[출처] 사이클 찾기|작성자 jh20s http://blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221248815321&categoryNo=7&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

무향 그래프에서 사이클은 (엣지 개수 >= 노드 개수) 면 무조건 싸이클이 있고 아니면 무조건 없음

■ 후보키 카카오 블라인드 테스트 #include <bits/stdc++.h>

using namespace std;

bool isKeyCheck(vector<vector> relation, int rSize, int cSize, int bMask) { bool isSame; for(int i=0; i<rSize-1; i++) { for(int j=i+1; j<rSize; j++) { isSame = true; for(int k=0; k<cSize; k++) { if((bMask & (1<<k)) == 0) continue; if(relation[i][k] != relation[j][k]) { isSame = false; break; } } if(isSame) return false; } } return true; }

int solution(vector<vector> relation) { int answer = 0; int rSize = relation.size(); int cSize = relation[0].size(); vector cKey;

for(int i=1; i< (1<<cSize); i++) {
    if(isKeyCheck(relation, rSize, cSize, i))
        cKey.push_back(i);
}

sort(cKey.begin(), cKey.end(), [] (int a, int b) {
    int aR=0, bR=0;
    while(a) { if(a&1) aR++; a = a >>1; }
    while(b) { if(b&1) bR++; b = b >>1; }
    return aR > bR;
});

while(!cKey.empty()) {
    int n = cKey.back();
    cKey.pop_back();
    answer++;
    
    for(vector<int>::iterator it = cKey.begin(); it !=cKey.end();) {
        if((n & *it)==n) it = cKey.erase(it);
        else it++;
    }
}

​
​ return answer; }

■ 오픈채팅방 카카오 블라인드 테스트 #include <bits/stdc++.h>

using namespace std;

vector solution(vector record) { vector answer; map<string, string> uInfo; vector<pair<string, int>> mList; istringstream iss; string m; vector msg;

for(string r : record) {
    iss.clear();
    msg.clear();
    iss.str(r);
    while(getline(iss, m, ' ')) {
        msg.push_back(m);
    }
    
    if(msg[0]=="Enter") {
        uInfo[msg[1]]=msg[2];
        mList.push_back({msg[1],0});
    } else if(msg[0]=="Leave") {
        mList.push_back({msg[1],1});
    } else {
        uInfo[msg[1]]=msg[2];
    }
} 

for(int i=0; i<mList.size(); i++) {
    if(mList[i].second) {
        answer.push_back(uInfo[mList[i].first]+"님이 나갔습니다.");
    } else {
        answer.push_back(uInfo[mList[i].first]+"님이 들어왔습니다.");
    }
}

​ return answer; }

■ ??? - 전광판 광고 모의 시험

---

■ 프로그래머스 이분탐색 > 징검다리 문제

파라메트릭 서치 문제다.
0-distance 사이의 거리의 반을 나눠서 시작
그 반의 거리보다 클 때까지 돌을 제거해서 제거해야하는 돌의 수가 n보다 많은가 적은가를 보고 mid 값을 옮긴다.
n보다 적을 때 최대값을 구하면 되니까 계속 돌렸을 때 가장 높아진 low를 answer로 담으면 끝.

using System;

public class Solution {
    public bool isRmCntMoreN(int m, int[] rocks, int n) {
        int rmCnt=0, last=0;

        foreach(int r in rocks) {
            if(r - last > m) last = r;
            else rmCnt++;
        }
    
        return rmCnt>n;
    }
    
    public int solution(int distance, int[] rocks, int n) {
        int answer, l=0, h=distance, m;
    
        Array.Sort(rocks);
    
        while(l<=h) {
            m = (l+h)/2;
            if(isRmCntMoreN(m, rocks, n)) h=m-1;
            else l=m+1; 
        }
    
        return answer = l;
    }
}

■ 프로그래머스 이분탐색 > 예산 문제

이것도 파라메트릭 예산액이 초과되면(빼서 0보다 작아지면) 예산액 반으로 줄이고 돌려보고 통과하면 늘려서 돌리고 해서 통과할 때만 기록해 가능한 최댓값을 구한다.

#include <bits/stdc++.h>

using namespace std;

bool isBudgetOver(vector& budgets, int& mid, int M, int& answer) { for(auto b : budgets) { if(b > mid) M-=mid; else M-=b;

    if(M<0) return true;
}

answer = max(answer, mid);
return false;

}

int solution(vector budgets, int M) { sort(budgets.begin(),budgets.end()); int answer = 0, l=1, h=budgets.back(), mid;

while(l<=h) {
    mid = (l+h)/2;
    if(isBudgetOver(budgets, mid, M, answer)) h=mid-1;
    else l=mid+1;
}

return answer;

}

■ 프로그래머스 그래프 > 사이클 제거

처음 코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<int> visitedOrder;
vector<int> chkList;
bool hasC;

void hasCycle(int now, int parent, int except) {
    for(int i=0; i<adj[now].size(); i++) {
        if(hasC) return;
        int to = adj[now][i];
        if(to == except) continue;
        if(to != parent) {
            if(visitedOrder[to] == 0) {
                visitedOrder[to] = visitedOrder[now] + 1;
                chkList.erase(remove(chkList.begin(),chkList.end(), to),chkList.end());
                hasCycle(to, now, except);
            } else if(visitedOrder[to] < visitedOrder[now]) {
                hasC=true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> edges) {
    int answer = 0;
    adj.resize(n+1, vector<int>());
    
    for(int i=0; i<edges.size(); i++) {
        adj[edges[i][0]].push_back(edges[i][1]);
        adj[edges[i][1]].push_back(edges[i][0]);
    }
    
    for(int i=1; i<=n; i++) {
        
        chkList = adj[i];
        hasC=false;
        for(int j=0; j<chkList.size(); j++) {
            visitedOrder.resize(n+1, 0);
            hasCycle(chkList[j],0, i);
            visitedOrder.clear();
        }
        if(!hasC) { answer+=i; }
    }
        
    return answer;
}

서브트리에 포함된 백엣지의 수 구하는 코드로 효율성 통과
backT - i가 루트인 서브트리에 '완전히' 포함된 back edge의 수
backS - i가 루트인 서브트리에 '조금이라도' 포함된 back edge의 수
backP - i가 루트인 서브트리에서 i의 부모가 목적지인 back edge의 수

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj, child;
vector<int> check, backT, backS, backP;

void dfsTree(int n, int from)
{
    for(auto to : adj[n]) {
        if(to != from) {
            if(!check[to]) {
                child[n].push_back(to); 
                check[to] = check[n]+1;
                int tmp = backT[n];
                dfsTree(to, n);
                backP[to] = backT[n] - tmp;
                backT[n] += backT[to];
                backS[n] += backS[to];
            } else if(check[to]<check[n]) {
                backS[n]++;
                backT[to]++;
            }
        }
    }
}

int solution(int n, vector<vector<int>> edges) {
    int answer = 0, eSize = edges.size();
    adj.resize(n+1); child.resize(n+1);
    check.resize(n+1, 0); backT.resize(n+1, 0);
    backS.resize(n+1, 0); backP.resize(n+1, 0);
    
    for(int i=0; i< eSize; i++) {
        adj[edges[i][0]].push_back(edges[i][1]);
        adj[edges[i][1]].push_back(edges[i][0]);
    }
    
    check[1] = 1; dfsTree(1,0);
    
    for(int i=1; i<=n; i++) {
        bool skip = false;
        for(auto to : child[i]) if(backS[to] - backP[to] > 1 || backT[to]) skip = true;
        if(skip || eSize-(n-1)-backS[i] != 0 ) continue;
        answer+=i;
    }
    
    return answer;
}

■ 프로그래머스 그래프 > 방의 개수

평면그래프 문제
평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다.
평면 그래프의 공식 v - e + f = 2
v = 점의 개수, e = 선의 개수, f = 면의 개수
시작시점부터 모든 점과 선을 구한다음 식 맞춰주면 되는데 여기서 중요한 점은 식에서 좌표 평면 전체도 평면으로 세기 때문에 f면의 개수 -1 해줘야함
그리고 대각선끼리 만나는 점은 소수점이 나오니까
ex) (0,0 -> 1,1) (1,0, -> 0,1) 라면 0.5, 0.5 에서 만나니까
공식에 따를거니까 선, 점의 개수가 늘어나는건 상관없으니 애초에 2의 길이만큼 가게 해서 1.0 에서 만나게 만듬.

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] arrows) {
        int[] dX = {0, 1, 1,  1,  0, -1, -1, -1};
        int[] dY = {1, 1, 0, -1, -1, -1,  0,  1};
        HashSet<Tuple<int,int>> v = new HashSet<Tuple<int,int>>();
        HashSet<Tuple<Tuple<int,int>, Tuple<int,int>>> e = new HashSet<Tuple<Tuple<int,int>, Tuple<int,int>>>();
        int answer = 0, x=0, y=0;
        
        v.Add(Tuple.Create(x,y));


​        
​        for(int i=0; i<arrows.Length; i++) {
​            for(int j=0; j<2; j++) {
​                int nX = x + dX[arrows[i]];
​                int nY = y + dY[arrows[i]];
​                Tuple<int, int> srtPnt = Tuple.Create(x, y);
​                Tuple<int, int> endPnt = Tuple.Create(nX, nY);
​                int result = endPnt.Item1.CompareTo(srtPnt.Item1);
​                if( result == 0 ) result = endPnt.Item2.CompareTo(srtPnt.Item2);
​                if( result > 0 ) {
​                    Tuple<int, int> temp = srtPnt;
​                    srtPnt = endPnt;
​                    endPnt = temp;
​                }
​                e.Add(Tuple.Create(srtPnt, endPnt));
​                x = nX;
​                y = nY;
​                v.Add(Tuple.Create(x,y));
​            }
​        } 
​        
​        return answer = 2 - v.Count + e.Count - 1;
​    }
}

C++

0. 헤더파일

#include <bits/stdc++.h>
모든 표준 라이브러리가 포함된 헤더입니다. 프로그래밍 대회에서 위 해더를 사용하는 것은 좋은 아이디어 입니다. 문제를 풀 때 마다
include 등등을 작성하는 반복적인 일을 줄여서 시간안배를 도와줍니다.
단점

• bits/stdc++.h 헤더는 GNU C++ 라이브러리의 표준 헤더가 아니기 때문에, GCC가 아닌 다른 컴파일러로 빌드를 하려고 한다면 실패합니다.
• 쓸대없는 파일들을 추가시켜서 컴파일 시간이 늘어납니다.
• 표준 C++이 아니기 때문에 이식성이 있지도 않고, 컴파일러 종속적입니다.

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2015 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

for(auto i = s.begin();i!=s.end();i++){ 포문 iterator형태로 속도를 올리자.

일반적으로, standard input에서 입력 받는 경우는 scanf와 cin만으로 충분하다고 생각했으나,
문제를 몇 개 풀면서 그게 아니라는 것을 알았다.

문자열이 공백을 포함하거나, 한 줄을 통째로 입력받는데 그것을 scanf 문 하나로 커버할 수 없는 경우
어려움이 생긴다.

공백을 포함하여 한 줄을 통째로 입력받아야 하는 경우,
그리고 그 크기도 짐작하기 어려운 경우에, 다음과 같이 받으면 된다.

string s;
getline(cin, s);

이렇게 하면, 공백을 포함한 문자열이 통째로 s 안으로 들어온다. ( cin >> s 로는 불가능한 것.)
이 s를 가지고 stringstream 등으로 지지고 볶아서 각 원소를 분리해내면 된다.

출처: https://word.tistory.com/21 [Life]

1. 문자열 (#include string> 은 당연하니까 뺀다.)

문자열에서 문자열 추출

string str.substr(시작인덱스,갯수);

문자열 찾기 str.find : str에서 특정 문자열을 찾고, 그 시작위치를 반환
( 문자 ) : 인덱스 0부터 해당 문자를 찾고, 시작위치를 반환한다.
( 찾는문자열 ) : 인덱스 0부터 해당 문자열을 찾고, 그 시작위치를 반환한다.
( 찾는문자열, 시작위치 ) : 시작위치부터 문자열을 찾고, 시작위치를 반환한다.
string::npos // 찾는 문자열이 없는 경우에는 string::npos를 반환한다.

string s1 = "abcd" ;  
string s2 = "b" ;   
int location = s1.find( s2 ) ;  
location = s1.find( s2, x ) ;

문자/문자열 찾기 (응용) 특정 문자열을 찾아서 *로 바꾼다음 *의 갯수로 특정 문자열의 수를 구한 예
문자나 문자열을 size_t str.find(찾을문자/문자열, 찾는 위치(int)) 로 찾을 수 있다.

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
string str;
int main() 
{
    cin >> str;
    int pos = 0;
 
    string croatia[8] = { "c=","c-","dz=","d-","lj","nj","s=","z=" };
    string tmp;
    string star = "*";
 
    for (int i = 0; i < 8; i++) 
    {
        tmp = croatia[i];
 
        if (str.find(tmp) != string::npos) 
        {
            while ((pos = str.find(tmp)) != string::npos) 
            {
                str.erase(pos, tmp.length());
                str.insert(pos, star);
            }
        }
    }
    cout << str.size() << endl;
    return 0;
}

대/소 문자 처리

#include <algorithm> // transform() 함수용

std::string str = "Hello World";
std::transform(str.begin(), str.end(), str.begin(), ::toupper); 
//문자열 전체 대문자로 소문자는 마지막 인자를 ::tolower *주의: 뒤에 ()안붙이고 앞에 :: 붙이기

char ch = toupper(a);
char ch = tolower(a);
//char 한 글자 처리 #include <algorithm> 필요없다.

대/소문자/공백 체크
true면 아무숫자 false면 0

<cctype>
int isspace(int x) //공백체크 
int isupper(int x) 
int islower(int x)

문자열 치환

std::string ReplaceAll(std::string &str, const std::string& from, const std::string& to){
    size_t start_pos = 0; //string처음부터 검사
    while((start_pos = str.find(from, start_pos)) != std::string::npos)  //from을 찾을 수 없을 때까지
    {
        str.replace(start_pos, from.length(), to);
        start_pos += to.length(); // 중복검사를 피하고 from.length() > to.length()인 경우를 위해서
    }
    return str;
}

...

std::cout << ReplaceAll(string("Number Of Beans"), std::string(" "), std::string("_")) << std::endl;
std::cout << ReplaceAll(string("ghghjghugtghty"), std::string("gh"), std::string("X")) << std::endl;
std::cout << ReplaceAll(string("ghghjghugtghty"), std::string("gh"), std::string("h")) << std::endl;

문자열 제거

 str.erase (std::remove(str.begin(), str.end(), chars[i]), str.end());

토큰으로 문자열 나누기

#include <iostream>
#include <string>
#include <sstream> //istringstream 용
 
std::string myText("some-text-to-tokenize");
std::istringstream iss(myText);  // iss를 string을 넣어 생성자로 생성한거구
//iss.str(myText); 이렇게하면 생성자 아닐 때 반복문에서 string을 넣어주는 방법, 단, 저거하기전에 iss.clear(); 먼저 해주기
//char ch = iss.get(); 하면 한개의 문자를 꺼내올 수 있다. 
//여기서 iss.unget(); 하면 가져온걸 다시 넣는다. 조건 검사하고 아니면 다시 넣을 때 필요.
std::string token;
while(getline(iss, token, '-')) // "abc-def" 일 때 getline(iss, token, '-'); 을 하면 나눠지고 token으로 abc만 들어감 iss엔 "-def"가 남아있다.
{
      std::cout << token << std::endl;
}

헤더 :

stringstream은, 주어진 문자열에서 필요한 정보를 빼낼 때 유용하게 사용된다.

간단한 사용 예를 보자.

float num;
stringstream stream1;

string string1 = "25 1 3 .235\n1111111\n222222";	  
stream1.str(string1);
while( stream1 >> num )
	cout << "num: " << num << endl;  // displays numbers, one per line

이 코드는, 저 문자열에서 실수 형태의 정보를 num에 저장하고 출력하는 것이다.
실제로 float 형태의 변수에 25, 1, 3, ... 등의 값들이 각각 저장되는 것으로, 매우 유용하다.

출력 결과는, 6개 줄에 걸쳐 "num : " 옆에 25, 1, 3 0.235, 1111111, 222222 가 출력된다.
공백과 \n을 무시하고, 숫자 정보만 빼낸 것이다.
while(stream1 >> num)이란, 더 이상 num의 자료형에 맞는 정보가 없을 때까지
계속 스트림에서 num으로 자료를 추출/복사하는 것이다. 끝에 도달하면 끝난다.
(즉, 만일 주어진 string이 "23 259 .326 22 a 15" 인 경우,

num이 int이면 259까지만, num이 float이면 22까지만 추출하고 멈춘다.)
여기서 특이한 것은, float 자료형에 맞게 .235를 0.235로 저장한다는 것이다.
만일 위와 똑같은 코드에서 맨 윗줄만 바꿔서, float num 대신 string num으로 선언하였을 경우,
이번엔 float 형태가 아니라 string 형태이기 때문에,
문자열 내에 존재하는 .235는 앞서와 달리 0.235로 바뀌지 않고 그냥 ".235" 가 된다.
여기서 주의할 점은, 값을 추출한다고 해서, stringstream에 있는 값들이 변하는 것은 아니라는 것이다.
마지막 값까지 모두 추출했다고 하더라도, stringstream에 저장된 값은 처음과 변함없이
"25 1 .235\n1111111\n222222" 가 되어 있다.

---

str() 함수에 관하여 - str() 함수가 사용되는 방법은 2가지이다.

1. str(string s)

• 현재 stringstream의 값을 s 로 바꾼다.

2. str()

• 현재 stringstream이 저장하고 있는 문자열의 복사본을 반환한다.

clear 함수에 관하여

1. 정확히 뭘 clear하는지 모르겠다. 확실한 것은 stringstream에 저장된 문자열을 clear하지는 않는다는 것 !!

   • stringstream에 저장된 문자열을 삭제하고 싶으면, stringstream ss; ss.str("")를 사용하면 된다.

2. clear를 실시한 경우에만, str(string s)로 새로운 문자열을 받았을 때 첫 위치부터 추츨이 가능하다.

둘을 모두 이용하면 stringstream 변수를 새로운 문자열을 받는 데에 재사용 할 수 있다.

string str1 = "23 259 .326 22 a 15";
string str2 = "1 263avj 3135df 3235 baij af9i39a fklk30";

stringstream ss(str1);	
string k;
while(ss >> k)	cout << k << endl;

ss.clear();
ss.str(str2);
while(ss >> k)	cout << k << endl;

이 코드에서 clear()이 없는 경우, str2를 저장해도 여기서 값을 추출할 수 없다.
이전의 string에서 이미 끝까지 도달했다는 flag가 올라가서, 더 이상 값이 추출되지 않기 때문이다.
그러한 flag bit들을 초기화시키는 것이 clear()으로 보인다.

---

<활용 팁>

다음과 같은 input이 들어온다고 해 보자. (vector이라고 하자)

[0] - "1 Kim 89"
[1] - "2 Park 52"
[2] - "3 Moon 100"
[3] - "4 Jun 95"
...

이러한 input에서, 각 번호/이름/점수를 각각 나누어 저장해야 할 때, 어떻게 하면 좋을 것인가?

vector input(3, "");	// given input
input[0] = "1 Kim 89";
input[1] = "2 Moon 100";
input[2] = "3 Chan 78";

for(int i = 0; i < input.size(); i++)
{
	int num, score;
	string name;

	stringstream ss;	ss.str(input[i]);

	ss >> num;
	ss >> name;
	ss >> score;

	cout << num << " " << name << " " << score << endl;
	// 이후 필요한 자료 구조에 저장하여 활용한다.
}

출처: https://word.tistory.com/24 [Life]

문자열 카운트

int occurrences = 0;
string::size_type start = 0;

while ((start = base_string.find("찾는것", start)) != string::npos) {
    ++occurrences;
    start += "찾는것".length(); // see the note
}

문자를 가지고 반복해 문자열 생성 [특이한 방법, 참고]

 *(new string(n, '*')); //n=5 "*****"

string->int / stoi() 이 (내장 함수)가 (+ - 부호)까지 처리한다!!! *다른 변환도 비슷함 atoi는 문자->숫자 itos 숫자를 스트링

int i = stoi(str);

숫자 자료형(int, double..)-> string / to_string(값)

string str = to_string(i);

2. 자료 구조

Vector 가장 기본적인 동적 배열같은 스택(?) 리스트(??)

백터를 스택처럼 사용가능 top() -> back(), push() -> push_back(), pop() -> pop_back()

생성, 초기화, 복사

vector.resize(n); n범위 생성
vector<int>(n, 0); n범위 0으로 생성해 체우기
vector<int>v, c; 
// c에 내용을 넣었다고 가정
v = c; // 개꿀팁 ㅎㅎ 오버라이딩 연산자 되어있어서 그냥 백터끼리 '= '연산자로 복사 붙여넣기 할 수 있음.

백터의 특정 범위에 같은 값 넣기 algorithm 필요

fill (v.begin(), v.begin()+4, 1); // 1번째 위치부터 4번째 위치까지 1로 할당
fill (v.begin()+4, v.end(), 2); // 5번째 위치부터 끝까지 2로 할당

백터의 요소의 합을 구하는 함수

#include <numeric>
sum_of_elems = accumulate(vector.begin(), vector.end(), 0); //int형
sum_of_elems = accumulate(vector.begin(), vector.end(), 0L); //long형 반환

백터에서 최고값/ 최솟값 요소 값 구하기

#include <algorithm>
*max_element(works.begin(), works.end()) -= 1;
*min_element(v.begin(), v.end())

벡터에 특정위치(인덱스)에 값을 삽입하기

v.insert(v.begin()+1, 3, 4); //2번째 위치(1번 뒤에)에 3개의 4값을 삽입합니다. (뒤엣놈들은 뒤로 밀림)
v.insert(v.begin()+1,sub.begin(),sub.end()); //2번째 위치(1번 뒤에)에 sub백터의 begin()과 end()까지 요소들을 삽입합니다.
q=v.insert(v.begin()+1, 3); //2번째 위치(1번 뒤에)에 3의 값을 삽입합니다. 삽입한 곳의 iterator를 반환합니다.

백터의 중복된 요소 제거하기 ( ->다른방법으로 set에 넣어 중복방지 시키는 방법이 있음)

vector<int> v({1,1,1,1,2,2,2,3,3,4,4,5,6,7,7,7,7,8,8,9,9,9});
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

찾기

vector<int>::iterator it = std::find(v.begin(), v.end(), 123);

if(it==v.end()){

    std::cout<<"Element not found";
}

백터 요소 정렬하는 함수

#include <algorithm>          // sort,reverse 사용 위해 필요
#include <functional>         // greater 사용 위해 필요

sort(v.begin(), v.end()); 오름차순 정렬 해버림
sort(v.rbegin(), v.rend()); 내림차순 정렬
sort(v.begin(), v.end(), std::greater<int>()); 내림차순 정렬
reverse(v.begin(),v.end()); 오름차순 했다가 이 함수 쓰면 내림차순됨 (이건, Vector가지구 큐 흉내낼 때 쓰면 좋음)

2차 백터일 경우 요소 동적 추가하는법

vector<vector<int>> a;
a.push_back(vector<int>()); //동적추가로 a[0]을 만듬.
a[0].push_back(14); //이런식으로 동적추가 a[0][0] 만들고 거기에 14를 넣을 수 있다.

백터 요소 삭제 (1개 이상일 경우 1에 개수 입력)

vector.erase(vector.begin(), vector.begin()+1[개수]); // [0]~[n]
vector.erase(vector.begin()); // 이러면 그냥 맨처음 한개 삭제될거임 [0]
vector.erase(--vector.end()); // 마지막 요소 1개 삭제할때

백터 특정 요소 찾아서 모두 제거
Consider this vector:
|0|1|2|3|4|5|6|7|8|9|
We use remove_if to remove all elements that are multiples of 4:

v.erase( std::remove_if(v.begin(), v.end(), [](auto i){ return i != 0 && !(i%4); }), v.end());

#include <algorithm>
...
vec.erase(std::remove(vec.begin(), vec.end(), 8), vec.end());

백터 요소를 일부만 새로운 백터로 만들기 (시작, 끝 인덱스 적힌곳에 숫자 적으면 됨)

pastedVec.assign(copiedVec.begin()+[시작 인덱스], copiedVec.begin()+[끝 인덱스 +1]) 
//반복자는 (b,e) 일 경우 (0, 1) -> 이래야 0인덱스를 가리킨다. (0, 0) no no!

T[ 10] 정적 배열 / T* p = new T[ n]동적 배열

배열 첫번째 항목만 특정 숫자로 초기화 방법

int count1[676] = { 1, }; // index [0]만 1로 초기화

배열 전부 0으로 효율적이게 채우기 1이상의 값 쓰면 쓰레기값 들어감!!
(int형이지만 내부에서는 unsigned char(1 byte)로 변환되어서 저장된다.)

int r[501][501];
memset(r, 0, sizeof r); // 0으로 초기화

1차배열 특정 숫자(-1)로 100개 채우기
2차배열 (3)으로 다 채우기

fill_n(array, 100, -1);

char data[26][80]; //2차 배열
fill_n(&data[0][0], 26*80, 3);  // or fill_n(*data, 26*80, 3);

pair<T, T>

해더파일 #include utility>에 있지만
algorithm>, vector>와 같은 헤더파일에서 이미 include하고 있기에 이게 있다면 따로 utility를 include해 줄 필요는 없다.
생성할 때 make_pair(i, str)나 pair int,string>(i, str) 이렇게 사용할 수 있다. (백터와 엮기 좋음 K, V 흉내내기도)
p.first : p의 첫번째 인자를 반환해 줍니다.
p.second : p의 두번째 인자를 반환해 줍니다.
sort() 알고리즘에 의해 정렬이 가능한 장점 때문에 사실 백터랑 엮어서 자주 씀.

// ~#include<utility>~ vector, algorithm이 있으므로 NO필요! 
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
int main(void){
    vector<pair<int, string> > v;

    v.push_back(make_pair(1, "Tiger JK"));  // 개인적으로 이 방법이 더 편함
    v.push_back(pair<int, string>(3, "Dok2"));    
    v.push_back(pair<int, string>(6, "DMask"));    
    v.push_back(pair<int, string>(1, "Tiger JK"));    
    

set, map<K, V>, multiset, multimap<K, V>, unordered_set, unodered_map<K, V>

map<string,int> m;
m[key] = 1;              //맵은 m[key] = value 이런식으로 넣을수 있다. m[key] ++; 이런식으로도 가능
for(auto& x: m) answer *= (x.second + 1);             //auto& x: m 이런식으로 요소를 쉽게 사용할 수 있다. x.first ->key,  x.second -> value 

map set 기본적으로 key,value값에 따른 오름차순인데 이런식으로 바꿀 수 있다.

map<int, string, greater<int> > m3;  키값 내림차순
map<int, string, string.less<int>>    -> map의 오름차순 (그냥 map<key, value> 사용시 오름차순)
map<int, string, string.greater<int>>  -> map의 키값 내림차순

set,map,multiset,multimap 에서 마지막 요소(가장 큰 값) 참조하는 법 (지우는 법)

minheap.erase( std::prev(minheap.end()));
minheap.erase(--minheap.end());

unique한 집합을 순서대로 출력해야 할 필요성이 있다면 그냥 set을 사용하고, unique 함 만을 체크해야 한다면 효율 좋은 unordered_set

#include <unordered_set>
unordered_set<string> mySet;

multimap, multiset의 경우 count로 원소의 개수를 알수 있다.

s.count(k); //0,1 set,map 일 경우

Priority Queue와 Heap

priority queue는 queue의 일종으로, 기본적으로 삽입(push), 꺼내기(pop) 연산을 가집니다.
pop 연산을 할 때, 현재 자료구조에 삽입된 원소들 중 우선순위가 가장 높은 원소를 꺼내는 연산을 하는 것이 priority queue 입니다.

heap은 priority queue의 한 종류로서, push와 pop이 O(log n) 시간에 빠르게 처리되는 구조입니다.
min-heap은 pop 연산 수행 시 원소들 중 최소값을 꺼냅니다. 반면 max-heap은 pop 연산 수행 시 최대값을 꺼냅니다.

priority_queue 일 때
min-heap은 priority_queue<int, vecter,greater> pq 이런식으로 선언하면 됨. (<T,vector,greater>)

// 오름차순 정렬 ****기존 순서와 반대로 해야한다!! 내림차순 오름차순 역순이다.
struct cmp{
    bool operator()(Custom t, Custom u){
        return t.value > u.value;
    }
};



int main(){

	// priority_queue
	priority_queue< Custom, vector<Custom>,  cmp > pq;

max-heap을 min heap 처럼 사용하는 특이한 방법으로
push할때 -를 붙여주어 순서를 역으로 만들고 -pq.top() 탑을쓸때도 -붙여주면 원래가장 작은 값이 나옴.

C++ STL의 priority_queue 자료형을 통해 min-heap 혹은 max-heap 중 사용자가 원하는 것을 쉽게 구현할 수 있습니다.

STL의 Queue 컨테이너 경우 다른 컨테이너와 다르게 clear 멤버 변수가 없습니다. 그래서 이를 초기화 해주려고 하면, 아래와 같이 일일히 루프를 돌며 pop을 해주거나하죠

while (!mQueue.empty())
{
    mQueue.pop();
}

void ClearQueue(std::queue<int> &someQueue)
{
    std::queue<int> empty;
    std::swap(someQueue, empty);
}

algorithm의 swap을 이용해 빈 큐와 바꿔치기 하는 방식이죠. 글 쓴이는 이 같은 방법이 실제 queue내의 메모리를 해제함과 동시에 queue를 초기화 할수 있다고 합니다.

#include queue> 헤더파일 필요

1. max-heap 구현 

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

int main () 
{ 
    priority_queue<int> q; 
    q.push (8); 
    q.push (1); 
    q.push (6); 
    q.push (2); 

    while (!q.empty ()) { 
        cout << q.top () << endl;  // print 8 6 2 1 
        q.pop (); 
    } 
    
    return 0; 
} 

3. 정렬

숫자를 문자열로 변경해서 정렬하는 방식 [참고]

#include <string>
#include <algorithm>
#include <functional>

using namespace std;

long long solution(long long n) {
    long long answer = 0;

    string str = to_string(n);
    sort(str.begin(), str.end(), greater<char>());
    answer = stoll(str);

    return answer;
}

sort(퀵 정렬), stable_sort(합병 정렬), partial_sort(힙 정렬)

• 평균적인 소요시간이 중요할 때에는 sort를 사용한다.
• 최악조건에서의 소요시간이 중요하다면 stable_sort나 partial_sort를 사용한다.
• 국가-지역 필드 혹은 동명이인 필드를 정렬해야 하는 경우, 안정 정렬(stable_sort)을 사용하는 것이 빠르다.
• 안정 정렬(stable_sort) 은 값이 같다면 원래의 순서를 보장한다.
• 불안정 정렬(sort, partial_sort) 은 값이 같아도 원래의 순서를 보장하지 않는다.

정렬 함수 만들 때 람다 함수(간단한 함수)로 표현해 낼 수 있다.

sort( s.begin(), s.end(), [] (const pair<int, int>& a, const pair<int, int>& b) { 
        if(a.first==b.first) return a.second<b.second; 
        return a.first>b.first;
});

4. 알고리즘/수학/순열/조합

최댓값 최솟값

#include <algorithm>
min(a,b) max(a,b) 

기초 많이 쓰는 함수

#include <cmath>

ceil(n) -> 올림
floor(n) -> 버림
round(n) -> 반올림
abs(n) -> 절대값
pow(n, p) -> 제곱
sqrt(n) -> 루트

순열

• #include algorithm> 다음 아래 함수를 통해서 순열을 구할수가 있다.

함수에 벡터의 iterator 혹은 배열의 주소를 넣으면 다음 순열(1-2-3-4의 다음 순열은 1-2-4-3) 혹은 이전 순열(1-2-4-3의 이전 순열은 1-2-3-4)의 결과가 벡터나 배열에 적용된다.

next_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
prev_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

#include <algorithm>
// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

n개 중에 r개로 순열(순서상관았는)을 만들기

• 순열(next_permutation), 반전(reverse)함수를 이용해서 제작 가능.
  반드시 오름차순으로 입력 n개 입력 1234 or 00112 //중복되도 됨
  [12] //순서대로 r만큼 출력
  1243 //r이후 요소를 reverse (34->43) = reverse(begin()+r,end());
  1324 //next_permutation()으로 다음 순열 제작, 조건걸어서 false나오면 반복문 빠져나가면 됨

이 과정을 반복하면 아래와 같이 조합을 모두 뽑아낼 수 있다.

[13]
1342 1423
[14]
1432 2134
[21]
2143 2314
[23]
...

원리는 r 뒤의 오름차순된 내용을 반전으로 최댓값을 만들어
다음번 순열을 구할 때 출력한 r의 다음번 내용이 나오고
r 뒤는 최솟값이 나오게 하여
이를 반복하면 r부분만 변하는 순열이 되버린다.

[소수찾기 - 응용 예]

#include <string>
#include <algorithm>
#include <unordered_set>
#include <cmath>

using namespace std;

unordered_set<long> num;

void subPermutation(string n, int m) {
    do {
        num.insert(stol(n.substr(0,m)));
        reverse(n.begin()+m,n.end());
    }
    while(next_permutation(n.begin(),n.end()));
}

int solution(string numbers) {
    int answer = 0;
    bool isPrime;

    sort(numbers.begin(),numbers.end());
    
    for(int i=1; i<=numbers.length(); i++)
        subPermutation(numbers, i);
    
    num.erase(0); num.erase(1);
    
    for(auto& x: num) {
        isPrime = true;
        for(int i=2; i<=sqrt(x); i++) 
            if(x%i==0) { isPrime=false; break; }
        if(isPrime) answer++;
    }
    
    return answer;
}

중복없는 조합

중복있는 조합

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

자리수/ 소수점아래 자리수 맞추기

double num = 987.123456;
cout << "num = " << num << endl;
// 출력 결과   987.123 
cout.precision(7);     //가장 왼쪽에 있는 숫자부터 오른쪽으로 7개까지의 숫자를 출력  
cout << "num = " << num << endl;
//출력 결과 987.1235
cout << fixed; //소수점아래 자리수 고정시키겠다는 뜻
cout.precision(2);
cout << "num = " << num << endl;
//출력 결과는 987.12

5. 검색/탐색

찾는 함수 (다양한 자료구조에서 유용 대게 begin(),end() 포인터로 찾고 결과를 내뿜는다.)

find(), find_if(), count(), count_if()

알고리즘에 있는 distance() 함수와 find_if() 함수 눈여겨보자 <참고>

#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(vector<string> seoul)
{
    return string("김서방은 ") + to_string(distance(seoul.begin(), find_if(seoul.begin(), seoul.end(), [](string s){ return s == string("Kim"); }))) + string("에 있다");
}

lower_bound 란?

• 이진탐색(Binary Search)기반의 탐색 방법입니다. (배열 또는 리스트가 정렬 되어있어야 한다.)
• lower_bound는 찾으려 하는 key값이 "없으면" key값보다 큰 가장 작은 정수 값을 찾습니다.
• 같은 원소가 여러개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있습니다.
• 구간이 [start, end]인 배열이 있을때, 중간위치의 index를 mid 라고 하면,
  arr[mid-1] < key 이면서 arr[mid] >= key 인 최소의 m 값을 찾으면 됩니다. (m>=2)

반환형이 Iterator 이므로 vector container인 경우에는 iterator에서 v.begin()을 뺀 값으로 몇 번째 인자인지 계산을 하고,
배열인 경우에는 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 몇 번째 인자인지 알 수 있습니다.

#include<algorithm> //헤더파일

lower_bound(arr, arr+n, key); //이런식으로 사용.

upper_bound 란?

• lower_bound와 마찬가지로 이진탐색(Binary Search)기반의 탐색법 입니다.
• 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어있어야 합니다.
• upper_bound는 key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
• 같은 원소가 여러개 존재 해도 항상 유일한 해를 구할 수 있습니다.
• 구간이 [start, end]인 배열이 있을때, 중간위치의 index를 mid 라고 하면,
  arr[mid-1] <= key 이면서 arr[mid] > key 인 최소의 m 값을 찾으면 됩니다. (m>=2)
• upper_bound에서 기억해야 할 것은 (같은 값이 아닌) key 값을 초과하는 가장 첫번째 원소의 위치 라는 것 입니다.

#include<algorithm> //헤더파일
upper_bound(arr, arr + 10, 6) - arr + 1;

map 사용법 key value

// accessing mapped values
#include <iostream>
#include <map>
#include <string>

int main ()
{
  std::map<char,std::string> mymap;

  mymap['a']="an element";
  mymap['b']="another element";
  mymap['c']=mymap['b'];

  std::cout << "mymap['a'] is " << mymap['a'] << '\n';
  std::cout << "mymap['b'] is " << mymap['b'] << '\n';
  std::cout << "mymap['c'] is " << mymap['c'] << '\n';
  std::cout << "mymap['d'] is " << mymap['d'] << '\n';

  std::cout << "mymap now contains " << mymap.size() << " elements.\n";

  return 0;

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    int cSize= clothes.size();
    map<string,int> m;
    string key;

    for(int i=0; i<cSize; i++) {
        key = clothes[i][1];
        if(m.find(key)==m.end()) m[key] = 1;
        else m[key]+=1;
    }

    if(m.size()!=1) { for(auto& x: m) answer *= (x.second + 1); answer--; }
    else answer = cSize;

    return answer;
}

맵은 key중복되면 기존값을 수정함 value(int일때)올리고 싶으면 [ key]++; 방법있음
unordered_map

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    unordered_map <string, int> attributes;
    for(int i = 0; i < clothes.size(); i++)
        attributes[clothes[i][1]]++;
    for(auto it = attributes.begin(); it != attributes.end(); it++)
        answer *= (it->second+1);
    answer--;

    return answer;
}

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    string s("string to split");
    istringstream iss(s);

    do
    {
        string sub;
        iss >> sub;
        cout << "Substring: " << sub << endl;

    } while (iss);

}

istringstream을 거치면 공백을 delim 으로 하여 string 을 parsing 해준다.
위의 예제를 보면, istr에 저장된 string 을 int 형에도 넣을 수 있는 것을 볼 수 있는데
이것이 바로 istringstream의 강력한 기능이다.

그리고 ostringstream은 위에서 살펴본 istringstream과 반대 기능을 한다고 볼 수도 있다.
주로, 수를 string 으로 바꾸어 줄때 주로 사용하게 된다.
사용은,

string solution(string s) {
    istringstream iss(s);
    vector<string> wList;
    string word;
    
    
    while(iss >> word)
    {
        for(int i=0; i<word.length(); i++)
            i & 1 ? toLowerString(word,i) : toUpperString(word,i);
        wList.push_back(word);
    }

#include<sstream> // ostringstream 을 사용하기 위하여 필요함.  
#include<iostream>  
#include<string>  
using namespace std;  
  
int main(){  
    ostringstream ostr;  
    int num = 34534;  
    string val;  
    ostr<<num;    //ostr에 num 저장  
    val = ostr.str(); //ostr을 string으로 바꾸어 val에 저장  
      
    return 0;  
}  

숫자 정규식

bool isNumber(const std::string &token)
{
    return std::regex_match(token, std::regex("(\\+|-)?[0-9]*(\\.?([0-9]+))$"));
}

bool isNumber( std::string token )
{
    using namespace std;
    return std::regex_match( token, std::regex( ( "((\\+|-)?[[:digit:]]+)(\\.(([[:digit:]]+)?))?" ) ) );
}

vector 에는 기본적으로 iterator, const_iterator (더 가벼운) 이 있다. 이걸 잘 활용하면 iter은 포인터이구 *iter 이런식으로 가리키는 값을 볼 수 있다.

int temp;
    for (vector<int>::const_iterator iter = arr.begin(); iter != arr.end(); ++iter)
    {
        if (arr.empty() || temp != (*iter))
        {
            temp = (*iter);
            answer.push_back(temp);
        }
    }

isspace(char) 스페이스인지 확인하는 것, string::iterator 활용해서 find_if사용하자.

  #include <iostream>
  #include <iterator>
  #include <string>
  #include <vector>
  #include <algorithm>    //find_if
  #include <cctype>       //isspace

  using namespace std;

  bool notspc(char c) { return !isspace(c); }
  bool spc(char c) { return isspace(c); }

  int main()
  {
      typedef string::iterator iter;

      string str;
      vector<string> vs;

      cout << "Insert string : ";
      getline(cin,str);

      iter i=str.begin();

      while(i!=str.end())
      {
          i=find_if(i,str.end(),notspc);
          iter j=find_if(i,str.end(),spc);
          if(i!=str.end())
              vs.push_back(string(i,j));
          i=j;
      }

      endl(cout);
      cout << "The string split by whitespace." << endl;
      copy(vs.begin(),vs.end(),ostream_iterator<string>(cout,"\n"));

    return EXIT_SUCCESS;
 }

메트릭스 곱과 메트릭스 선언 이렇게하자

typedef vector<vector<long long>> matrix;

matrix operator* (matrix &a, matrix &b)
{
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) {
            for(int k=0; k<n; k++)
                c[i][j] += a[i][k]*b[k][j];
            c[i][j] %= mod;
        }    
    return c;
}

최댓값

#include <limits>
then use

int imin = std::numeric_limits<int>::min(); // minimum value
int imax = std::numeric_limits<int>::max();

set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 원소(value).의 집합으로 이루어진 컨테이너이다.
모든 연관 컨테이너는 노드 기반 컨테이너이며 균현 이진 트리로 구현되므로 균형 이진 트리의 모든 특징을 갖는다.
#include

map 컨테이너는 연관 컨테이너 중 자주 사용하는 컨테이너로 원소를 key 와 value의 쌍으로 저장한다.
set은 원소로 key 하나만을 저장하지만, map 은 원소로 key와 value의 쌍(pair 객체)를 저장한다.
set처럼 원소의 key는 컨테이너에 중복 저장될 수 없으며 중복 key를 저장해야 한다면 mulitmap을 사용해야 한다.
#include

set<int> s;

    s.insert(40);
    s.insert(30);
    s.insert(50);
    s.insert(80);
    s.insert(10);
    s.insert(90); 
    s.insert(70);

    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter)
        cout << *iter << " ";
    cout << endl;

    // count는 해당 원소의 개수를 반환한다. set은 중복을 허용하지 않으므로 1 또는 0이다.
    cout << "원소 50의 개수 : " << s.count(50) << endl;
    cout << "원소 100의 개수 : " << s.count(100) << endl;

    // find는 해당 원소를 찾는다. 원소가 없으면 end() 를 반환한다.
    iter = s.find(30);
    if (iter != s.end())
        cout << *iter << "가 s에 있다" << endl;
    else
        cout << "30이 s에 없다." << endl;


        // map
	// <string, int> => <key, value>
	map< string, int > m;


	// insert(key,value)
	m.insert(make_pair("a", 1));
	m.insert(make_pair("b", 2));
	m.insert(make_pair("c", 3));
	m.insert(make_pair("d", 4));
	m.insert(make_pair("e", 5));
	m["f"] = 6; // also possible


	// erase(key)
	m.erase("d");

먼저, std::tuple<> 안의 <> 안에 필요한 변수 타입들을 작성합니다.
typedef로 해당 타입을 OddOrEven 타입이라고 명명했습니다.
tuple 변수에 값을 넣을 때는 std::make_tuple()을 사용하면 됩니다.
해당하는 위치에 해당하는 값을 넣으면 생성이 됩니다.
tuple 안에 몇 개의 변수가 존재하는지는 std::tuple_size<decltype(myNumber)>::value로 가능합니다.
decltype(myNumber)는 C++11에서 생긴 문법으로 해당 변수의 타입을 유추해줍니다.
간단하게 auto와 비슷한 기능이라고 할 수 있습니다.
값을 가져올 때는 std::get(myNumber)로 가져올 수 있습니다.
인덱스는 0부터 시작해서 해당하는 위치의 값을 가져옵니다.
std::tuple_element를 사용해서 tuple의 특정 위치의 타입을 가져올 수 있습니다

// make tuple variable.
    typedef std::tuple<int, std::string, bool> OddOrEven;
    OddOrEven myNumber = std::make_tuple(10, std::string("Even"), true);
 
    // get tuple size
    std::cout << "size : " << std::tuple_size<decltype(myNumber)>::value << std::endl;
 
    // get each value and get type using std::tuple_element, auto keyword.
    std::tuple_element<0, decltype(myNumber)>::type nNum = std::get<0>(myNumber);
    auto szVal = std::get<1>(myNumber);
    bool bEven = std::get<2>(myNumber);
 
    std::cout << nNum << ", " << szVal << ", " << std::boolalpha << bEven << std::endl;

이해 안되는 알고리즘

#include <string>
#include <vector>

using namespace std;

long long solution(int a, int b) {
    long long answer = 0;
    if (a > b) a ^= b ^= a ^= b;
    answer = (long long)b * -~b / 2 - (long long)a * ~-a / 2; // 이부분만 이해안됨 가우스 소거 알고리즘
    return answer;
}

1. Manacher 알고리즘
2. Z 알고리즘
3. 3*n 타일링

https://www.acmicpc.net/board/view/3261
문제 푸는순서