Hwan. 001

 request와 json 패키지를 사용해서 JSON 데이터를 파싱할 때, 각 키의 데이터를 수정하려면 아래처럼 dictionary 형태로 변환시켜 value를 수정한다.

data = {"key1":"value1"}
data["key1"] = "value2"

 
 전체 데이터를 스캔하여 특정 값을 가진 키를 찾으려고 한다.
아래 코드로 (for, if로) 전체를 확인하면서 원하는 값을 가진 키를 찾았다.

data = {
 "key1":"value1",
 "key2":"value2",
 "key3":"value3",
 "key4":"value4",
 "key5":"value5",
}

for key in data:
  if "value3" == data[key]:
    print(key)
    break

 
 간단한 데이터라면 위 방식으로도 충분히 찾을 수 있다. 하지만 데이터의 수가 매우 많거나 복잡할때도 같은 방식으로 값을 찾고 수정할 수 있을까?
 
아래처럼 사람의 정보를 가진 JSON 데이터에서 "-", "N/A", "" 의 값을 가진 키를 찾아서 제거하려고 하는데 각 자료형도 다르고 형태도 일정하지 않다. 사람 수도 매우 많다고 가정하겠다.

{
 "person_1":{
  "name": {"first":"David", "middle":"", "last":"Smith"},
  "age":12,
  "address":"-",
  "education":{"highschool":"N/A","college":"-"},
  "hobbies":["running", "swimming", "-"],
 },
 "person_2":{
  "name": {"first":"Mason", "middle":"henry", "last":"Thomas"},
  "age":21,
  "address":"-",
  "education":{"highschool":"N/A", "college":"", "Universitry":"Stanford"},
  "hobbies":["coding", "-", ""],
 },
 ...
}

 
 
먼저 위 형태로 랜덤한 데이터가 원하는 만큼 생성되도록 함수를 만들었다.
아래 이미지를 보면 패턴이 있긴하지만 데이터가 잘 생성된거 같다.

def create_random_data(num:int) -> dict:
    import random
    
    data={}
    random_string = lambda x: "".join([chr(random.randint(97, 122)) for tmp in range(x)])

    for i in range(num):
        key = f"person_{i+1}"
        data[key] = {
            "name":{"first":random_string(random.randint(0, 8)), "middle":random_string(random.randint(0, 8)), "last":random_string(random.randint(0, 8))}, 
            "age":random.randint(10, 50),
            "address":"-",
            "education":{"highschool":random_string(random.randint(0, 8)), "college":"", "Universitry":random_string(random.randint(0, 8))},
            "hobbies":["coding", "-", "", random_string(random.randint(0, 8))],
        }

    return data
    
print(create_random_data(5))

 
이제 파싱을 위한 함수를 만들어야하는데 위 데이터의 형태를 봤을 때 가장 문제가 될 것 같은 부분은 데이터의 깊이라고 생각했다.
데이터의 깊이에 상관없이 탐색할 수 있도록 재귀를 사용해 파싱 함수를 작성해보자.
 

def clean(data):
    remove_keyword = ["N/A", "-", ""]

    for key in list(data):
        value = data[key]

        if type(value) == dict: 
            clean(value)
            if value == {}:
                data.pop(key)

        if type(value) == list:
            for x in [keyword for keyword in remove_keyword if keyword in value]:
                for _ in range(value.count(x)):
                    value.remove(x)

        if type(value) == str:
          if value in remove_keyword:
            data.pop(key)

datas = create_random_data(5)
print(datas)
clean(datas.copy())
print(datas)

 
나름 잘 정리 됐다. 그런데 JSON 데이터 100만개를 처리하면 시간이 얼마나 걸릴지 궁금해져서 코드를 좀 더 수정해봤다.
https://hwan001.co.kr/178 글에 함수의 실행 시간을 측정하는 데코레이터가 있다.
재귀를 사용한 clean함수는 따로 작성해야겠지만 해당 코드를 사용해서 100만 건의 생성 시간과 정리 시간을 측정해보자.

def my_decorator(func):
    def wrapped_func(*args):
        import time
        start_r = time.perf_counter()
        start_p = time.process_time()

        ret = func(*args)

        end_r = time.perf_counter()
        end_p = time.process_time()
        
        elapsed_r = end_r - start_r
        elapsed_p = end_p - start_p
        print(f'{func.__name__} : {elapsed_r:.6f}sec (Perf_Counter) / {elapsed_p:.6f}sec (Process Time)')
        
        return ret
    return wrapped_func

@my_decorator
def create_random_data(num:int) -> dict:
    import random

    data={}
    random_string = lambda x: "".join([chr(random.randint(97, 122)) for tmp in range(x)])

    for i in range(num):
        key = f"person_{i+1}"
        data[key] = {
            "name":{"first":random_string(random.randint(0, 8)), "middle":random_string(random.randint(0, 8)), "last":random_string(random.randint(0, 8))}, 
            "age":random.randint(10, 50),
            "address":"-",
            "education":{"highschool":random_string(random.randint(0, 8)), "college":"", "Universitry":random_string(random.randint(0, 8))},
            "hobbies":["coding", "-", "", random_string(random.randint(0, 8))],
        }

    return data

def clean(data):
    remove_keyword = ["N/A", "", "-"]

    for key in list(data):
        value = data[key]

        if type(value) == dict: 
            clean(value)
            if value == {}:
                data.pop(key)

        if type(value) == list:
            for x in [keyword for keyword in remove_keyword if keyword in value]:
                for _ in range(value.count(x)):
                    value.remove(x)

        if type(value) == str:
          if value in remove_keyword:
            data.pop(key)


datas = create_random_data(1000000)
print(len(datas), datas, "\n")

import time
start_r = time.perf_counter()
start_p = time.process_time()

clean(datas.copy())

end_r = time.perf_counter()
end_p = time.process_time()
        
elapsed_r = end_r - start_r
elapsed_p = end_p - start_p
print(f'{"clean"} : {elapsed_r:.6f}sec (Perf_Counter) / {elapsed_p:.6f}sec (Process Time)')
print(len(datas), datas)

 
데이터가 길어서 다 나오지 않았기 때문에 키워드 개수와 데이터 일부를 찍어봤다.(키워드는 줄지 않음)

생성에 129. 3초, 정리에 13초가 걸렸다. 100만 개 정도부터는 확실히 탐색 속도가 느린게 느껴진다.
추가로 예시의 데이터에서는 깊이가 얕아서 재귀로도 문제없이 동작했지만 만약 깊이가 매우 깊다면 탐색 중에 메모리 에러가 발생된다.
재귀가 아닌 큐나 스택을 활용한 방식으로 변경해야 하고 실제로 사용하려면 좀 더 효율적인 알고리즘이 필요할 거 같다.
 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12939

2. 접근 방식

• split 하고 min, max 함수로 결과 return

3. 코드

def solution(s):
    list_s = [int(x) for x in s.split(" ")]
    return f'{min(list_s)} {max(list_s)}'

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12913

2. 접근방식

• DP문제이다.
• 바텀업 방식으로 해결하면 좋다.
• 점화식 :
  4개의 열(Column) 중 현재 열과 같은 열을 제외한 나머지 값 중 최대값을 현재값에 더한다.

for j in range(4):
	land[i][j] += max([land[i-1][x] for x in list({0, 1, 2, 3} - {j})])

• 가장 큰 합들이 마지막 열에 반영되었기 때문에 가장 아래 열에서 최대값을 선택하면 된다.

3. 코드

def solution(land):
    answer = 0

    for i in range(1, len(land)):
        for j in range(4):
            land[i][j] += max([land[i-1][x] for x in list({0, 1, 2, 3} - {j})])
        
    answer = max(land[len(land)-1])
        
    return answer

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42842

2. 접근방식

• 주어진 brown과 yellow의 개수는 해당 색 부분의 넓이와 같다.
• 가로를 x, 세로를 y라고 할 때, 주어진 brown과 yellow의 조합으로 xy와 x+y를 알 수 있다.
• 간단한 이차방정식을 만들고 이후는 완전탐색으로 값을 찾음

3. 코드

def solution(brown, yellow):
    answer = []
    
    x_y = int(brown / 2) + 2
    xy = brown + yellow
    
    for x in range(1, x_y):
        for y in range(1, x_y):
            if (x + y == x_y) and (x*y == xy):
                if x >= y:
                    return [x, y]
        
    return answer

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

2. 접근 방식

• 괄호가 "("면 push 한다.
• 괄호가 ")"면 pop한다.
• 문자열의 반복이 끝났을 때, 스택에 값이 남아있다면 잘못된 괄호이다.

3. 코드

def solution(s):
    list_stack = []
    
    for ch in s:
        if ch == "(":
            list_stack.append(ch)
        else:
            if list_stack == []:
                return False
            else:
                list_stack.pop()
            
    return list_stack == []

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42747

2. 접근 방식

• H-Index는 N편의 논문중 H번 인용된 논문이 H편 이상일 때의 최대값을 의미한다.
• 논문의 순서는 중요하지 않다.
• H-Index는 내부의 인용된 회수와 같지 않을 수도 있다.

3. 코드

def solution(citations):
    citations = list(reversed(sorted(citations)))
    len_citations = len(citations)
    max_citations = max(citations)
    h=0
    
    for h in range(max_citations, 0, -1):
        cnt = 0
        for x in citations: 
            if x >= h:
                cnt+=1
        if cnt >= h:
            break
        
    return h

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/17682

2. 접근 방식

• S, D, T, *, #을 공백을 포함하여 replace 후 공백으로 split 해주면 서로 분리됨(마지막 공백은 제거)
• 각 기호에 맞는 점수를 제곱해서 정수로 변경해줌
• *은 현재와 이전 값에 *2 (해당 범위에 * 이나 다른 기호가 포함될 경우도 고려해서 미리 정수로 변경해줌)
• #은 0으로 변경 후 현재 값에 -1
• 정수로 변환된 전체 리스트를 합쳐줌 -> 총점

3. 코드

def solution(s):
    for str_tmp in ["S", "D", "T", "*", "#"]:
        s = s.replace(str_tmp, str_tmp + " ") 
    res = [x for x in s.split(" ")][:-1]
    
    for i in range(len(res)):
        x = res[i]
        if x == "*" or x == "#":
            continue
        
        if "S" in x:
            res[i] = int(x.replace("S", ""))
        if "D" in x:
            res[i] = pow(int(x.replace("D", "")), 2)
        if "T" in x:
            res[i] = pow(int(x.replace("T", "")), 3)
            
    for i in range(len(res)):
        if res[i] == "*":
            res[i] = 0
            res[i-1] *= 2
            if i-2 >= 0:
                if res[i-2] != 0:
                    res[i-2] *= 2
                else:
                    res[i-3] *= 2
        if res[i] == "#":
            res[i] = 0
            res[i-1] *= -1
    
    return sum(res)

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/68935

2. 접근 방식

• 10진법을 2진법으로 만들때와 비슷하게 3으로 나눈 나머지를 리스트에 추가
• 역순으로 들어갔기 때문에 문제에서 요구하는 앞뒤 반전은 생략
• 해당 자리에 맞게 3의 제곱수를 곱해서 누적해줌

3. 코드

def solution(n):
    answer = 0
    tmp = []
    
    # 3^0:1, 3^1:3, 3^2:9, 3^3:27, 3^4:81...
    while(n!=0):
        tmp.append(n%3)
        n //= 3

    for x in range(len(tmp), 0, -1):
        i = len(tmp) - x
        answer += tmp[x-1] * 3**i
    
    return answer

4. 결과

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12940

2. 접근 방식

• 최대 공약수 :  두 수 이상의 여러 수의 공약수 중 최대인 수 -> n과 m에 동시에 나눠지는 i 중 가장 큰 값
• 최소 공배수 :  두 수 이상의 여러 수의 공배수 중 최소인 수 -> n과 m을 곱한 값을 최대 공약수로 나눈 값 (유클리드 호제법)
• 더 쉬운 방법 : math 패키지 활용

import math

math.gcd(a, b)
math.lcm(a, b)

3. 코드

def solution(n, m):
    answer = [1, 0]
    
    # GCD
    for i in range(1, m+1):
        if n%i ==0 and m%i==0:
            answer[0] = i
            
    # LCM
    answer[1] = n * m // answer[0]

    return answer

4. 결과

문제

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

접근 방식

• 지도 공간 중의 0인 위치를 찾아, 중복 되지 않고 3개의 위치를 선택한다. (순열)
• 해당 위치에 벽을 세우고 BFS로 바이러스를 확산시킨다. (4 방향)
• 모든 지도에 수행하면서 안전한 영역(0인 곳)이 가장 많이 남은 개수를 찾는다.

코드

#include <iostream>
#include <queue> 
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility> 

using namespace std;

void func_14502_virusInfect(int n, int m, int **_map, queue<pair<int, int>> q) {
	pair<int, int> cur;
	int _x, _y;
	int direc[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

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

		for (int i = 0; i < 4; i++) {
			_x = cur.first + direc[i][0];
			_y = cur.second + direc[i][1];

			if (_x >= n || _x < 0)
				continue;
            
			if (_y >= m || _y < 0)
				continue;

			if (_map[_x][_y] == 1 || _map[_x][_y] == 2) {
				continue;
			}

			_map[_x][_y] = 2;
			q.push({_x, _y});
		}
	}
}

int main() {
	int n, m, cnt, max_safeZone = 0;

	vector<pair<int, int>> _map_v;
	queue<pair<int, int>> q;

	cin >> n >> m;
	
	int** _map = new int* [n];
	int** _map_copy = new int* [n];

	for (int i = 0; i < n; i++) {
		_map[i] = new int[m];
		_map_copy[i] = new int[m];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> _map[i][j];

			if (_map[i][j] == 0) {
				_map_v.push_back({i, j});
			}
		}
	}

	sort(_map_v.begin(), _map_v.end());

	do {
		while (!q.empty()) {
			q.pop();
		}

		for (int i = 0; i < n; i++) {
			memcpy(_map_copy[i], _map[i], sizeof(int) * m);
		}
        
		for (int i = 0; i < 3; i++) {
			_map_copy[_map_v.at(i).first][_map_v.at(i).second] = 1;
		}
        
	    for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (_map_copy[i][j] == 2) {
					q.push({ i, j });
				}
			}
		}

		func_14502_virusInfect(n, m, _map_copy, q);

		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (_map_copy[i][j] == 0) {
					cnt++;
				}
			}
		}
		
		if (cnt > max_safeZone) {
			max_safeZone = cnt;
		}

		reverse(_map_v.begin() + 3, _map_v.end());
	} while (next_permutation(_map_v.begin(), _map_v.end()));

	cout << max_safeZone << "\n";
    
    return 0;
}

결과

순열 (Permutation)

 먼저 위키피디아에서 순열의 정의를 찾아봤다. 

수학에서의 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이라고 설명한다.

순열은 Permutation 의 앞글자 P로 표현한다. 

n개의 원소를 가진 집합을 임의의 다른 순서로 섞는 연산의 경우의 수는 n! 과 같고, n개의 원소 중 r개의 원소를 선택하여 순열하는 경우의 수는 P(n, r)과 같다.

아래 이미지는 위키피디아에서 P(n, r) 연산하는 방법을 설명한 부분이다.

C++ 코드로 구현해보자.

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

using namespace std;

void func(){
	vector<int> v = {1, 2, 3};
    
	do{
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << " ";
        }
        cout << "\n";
    }while(next_permutation(v.begin(), v.end()));
}

위의 코드는 STL인 sort와 next_permutation (또는 sort+reverse와 prev_permutation)을 활용하여 원소가 n개인 집합을 순열 연산했다.

n개의 서로 다른 원소에서 r개를 선택하여 나열하는 코드도 작성해보자.

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

using namespace std;

void func(){ 
    vector<int> v = {1, 2, 3, 5, 4, 8, 7, 6};
    int r = 3;
    
    sort(v.begin(), v.end());
    
    do{
    	for(int i = 0; i < r; i++){
        	cout << v[i] << " ";
        }
        cout << "\n";
        
        reverse(v.begin() + r, v.end());
        
    }while(next_permutation(v.begin(), v.end()));
}

{1, 2, 3, 5, 4, 8, 7, 6} 의 집합에서 3개를 선택하여 나열하는 코드이다.

코드에선 r까지 출력했지만, 이미지에선 vector의 변화를 보기위해 v.size()까지 출력하였다.

첫 줄 sort를 통해 오름차순으로 정렬된 모습이 보인다.

reverse를 해주지 않아도 전체 경우의 수가 나오긴하지만, 필요한 r개 만큼만 출력하게 되면 사용한 이유를 알 수 있다.

재귀로 구현하는 방법과 더 자세한 설명은 아래 참고링크 (블로그) 에 있다.

조합 (Combination)

 조합도 위키피디아에서 정의를 먼저 읽어봤다.

조합은 n개의 집합에서 순서에 상관없이 r개를 선택하는 경우의 수이다.

수학 적으로는 C(n, r) 등으로 표현한다.

조합은 아래 방법으로 계산할 수 있으며, C(n, r) = C(n-1, r-1) + C(n-1, r) 가 성립한다.

위 공식을 활용해서 재귀로 코드를 작성해보자.

int combination(int n, int r) {
	if (n == r || r == 0) {
		return 1;
	}
	else {
		return combination(n-1, r-1) + combination(n-1, r);
	}
}

간단하게 작성됐다. 더 자세한 내용은 아래 (블로그) 부분을 참고하면 된다.

참고 자료 링크

• https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4 - 순열
• https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9 - 조합
• https://ansohxxn.github.io/algorithm/permutation/ - 순열 코드 (블로그)
• https://ansohxxn.github.io/algorithm/combination/ - 조합 코드 (블로그)

문제

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

접근 방식

• 1~n 까지 오름차순으로 정렬된 num_vector, stack_vector, 원하는 수열을 입력 받을 target_vector 를선언한다.
• target_v의 각 요소들에서 num의 top(back)과 값을 비교한다.
• 같으면 다음 target으로 이동하고 다르면 하나씩 뽑아서 비교하면서 stack에 넣는다.
• 넣는 중에 찾을 경우 다음 target으로 이동한다.
• 다 넣고 못찾았을 경우 stack을 확인한다.
• stack에서 하나씩 빼면서 탐색한다.
• stack이 비었는데 target이 남아있거나 , 원하는 값을 찾을 수 없는 경우 No로 판단한다.

코드

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

using namespace std;

int main() {
    int n, tmp, num_cur, flag;
    cin >> n;

    vector<int> num_v, stack_v, target_v;
    vector<char> res_v;

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        target_v.push_back(tmp);
        num_v.push_back(i + 1);
    }

    reverse(num_v.begin(), num_v.end());
    
    for (auto tmp_target : target_v) {
        flag = 0;

        if (num_v.size() == 0 && stack_v.size() == 0) {
            res_v.clear();
            break;
        }

        if (!stack_v.empty()) {
            if (tmp_target == stack_v.back()) {
                stack_v.pop_back();
                res_v.push_back('-');
                flag = 1;
                continue;
            }
        }

        while (true) {
            if (!num_v.empty()) {
                num_cur = num_v.back();
                stack_v.push_back(num_cur);
                res_v.push_back('+');
                num_v.pop_back();

                if (tmp_target == num_cur) {
                    stack_v.pop_back();
                    res_v.push_back('-');
                    flag = 1;
                    break;
                }
            }
            else {
                if (stack_v.empty())
                    break;

                while (!stack_v.empty()) {
                    if (tmp_target == stack_v.back()) {
                        stack_v.pop_back();
                        res_v.push_back('-');
                        flag = 1;
                        break;
                    }
                    else {
                        stack_v.pop_back();
                    }
                }
                
                if (!flag) {
                    res_v.clear();
                    break;
                }
            }
        }
    }


    if (res_v.empty()) {
        cout << "NO\n";
    }
    else {
        for (auto tmp_res : res_v) {
            cout << tmp_res << "\n";
        }
    }
    
    return 0;
}

결과

최단 거리 알고리즘

 그래프에서 간선들 사이의 가중치와 방향이 있을 때, 한 정점에서 다른 정점들까지의 최단 거리를 구할 수 있는 알고리즘은 다익스트라, 벨만포드, A* 등이 있고, 모든 정점에서 모든 정점의 최단 거리를 구하는 알고리즘에는 플로이드 워셜 알고리즘이 있다.

 해당 알고리즘들을 응용하여 최단 거리를 가지는 경로를 구하는 방법도 있지만, 이 글에서는 다익스트라 알고리즘을 활용하여 최단 거리만 구해보겠다.

 먼저 우선순위 큐를 사용하지 않는 최초의 다익스트라 알고리즘은 아래 과정과 같고 O(V²) 의 시간 복잡도를 갖는다. (2중 for 문 구조)

1. 시작 노드 결정
2. 현재 노드를 기준으로 각 노드의 최소 비용을 계산
3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택
4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신
5. 3~4를 반복하여 모든 노드를 방문

 여기서 힙(우선순위 큐) 구조를 사용하면 O(log N)의 시간 복잡도로 값을 구할 수 있는데, 모든 간선에 대해 비교를 해야하므로 우선순위 큐로 구현된 다익스트라 알고리즘은 O(E * Log V) 의 시간 복잡도를 가진다.

아래 내용에서는 각 알고리즘의 특징과 방법을 정리하고 C++ 코드로 구현했다. (간선과 가중치 형태 입력, 인접 리스트)

다익스트라(Dijkstra) 알고리즘 - O(N²)

 그래프 사이에 가중치가 존재할 경우 경로를 갱신해가며 한 정점에서 다른 정점까지의 하나의 정점을 기준으로 각 노드의 최단 거리를 알 수 있다. 다익스트라 알고리즘은 양의 가중치를 가진 그래프에서 O(N²)의 시간 복잡도를 갖는다.

아래와 같은 그래프가 있을 때 A에서 각 정점까지의 최단거리를 위의 알고리즘을 따라서 계산해보자.

1. 시작 노드는 A

2. 현재 노드를 기준으로 각 노드의 최소 비용을 계산

 최초에 A에서 시작노드를 제외한 각 정점까지의 거리는 INF(무한)로 초기화되어 있기 때문에

A에서 각 정점까지의 최단 거리는 인접한 정점의 거리로 갱신된다.

(1) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택

  A에 인접한 노드 중 방문하지 않은 최소 비용의 노드는 E이다. 

(1) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신

E를 기준으로 최소 비용을 계산하면 아래와 같고, 이 때 E를 거쳐 갈 수 있는 경로가 없으므로 갱신하지 않는다.

5. 3~4를 반복하여 모든 노드를 방문

 모든 노드를 방문하지 않았으므로 3~4를 반복한다.

(2) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택

  E에 인접한 노드 중 방문하지 않은 최소 비용의 노드는 없으므로, A에 인접했던 노드 중 최소 비용의 방문하지 않은 노드인 C 노드를 선택한다.

(2) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신

  C 노드를 지나가는 경로 중 기존의 거리보다 가까운 경우는 D와 F 노드로 가는 경로이다.

해당 값들을 갱신해준다.

(3) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택

 C 노드의 인접 노드 중 방문하지 않은 최소 비용 노드는 D이다.

(3) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신

  D 노드를 지나가는 경로 중 기존의 거리보다 가까운 경우는 F 노드로 가는 경로이다. 

A-D의 최소 거리인 3과 D-F의 거리인 2를 더하면 5로 기존의 6보다 가깝다.

(4) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택 

 D 노드의 인접 노드 중 방문하지 않은 최소 비용 노드는 F이다.

(4) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신

 F 를 거쳐 B로 가는 비용 8과 E로 가는 비용 11은 기존 거리보다 멀기 때문에 갱신하지 않는다.

(5) - 3. 방문 하지 않은 노드 중 최소 비용의 노드를 선택 

 F 노드의 인접 노드 중 방문하지 않은 최소비용 노드는 B이다.

(5) - 4. 선택된 노드를 기준으로 거리 비용을 계산하여 더 가까울 경우 갱신

 B 를 거쳐 C 로 가는 경로의 거리 4는 기존 거리보다 멀기 때문에 갱신하지 않는다

6. 탐색 종료

 모든 노드와 경로를 방문하였기 때문에 탐색을 종료한다. 

A 노드에서 나머지 다른 노드로 가는 과정을 하나의 표로 나타내면 아래의 그림과 같고, 위 그래프에서의 다익스트라 결과는 0 3 2 3 1 5 이다.

이제 위의 과정을 C++ 코드로 구현 해보자.

#include <iostream>
#include <utility>
#include <vector>
#include <cstring>

using namespace std;

int main() {
    int n, m, start, max = 99999999;
    int min = max, current;
    int u, v, a;

    cin >> n >> m;

    // 방문 여부 초기화
    int* visit = new int[n+1];
    memset(visit, 0, sizeof(int) * (n+1));

    int* d = new int[n];
    for (int i = 0; i < n; i++) {
        d[i] = max;
    }

    // 인접 리스트 형태로 입력
    vector<pair<int, int>>* adjlist = new vector<pair<int, int>>[n];

    cin >> start;
    // 노드의 번호(A:1)를 인덱스로 변경(1->0)
    if(start > 0) start--;
    d[start] = 0;

    // 입력
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> a;
        adjlist[u - 1].push_back({ v - 1, a });
    }

    // 시작노드의 인접 노드 거리로 갱신
    for (auto tmp : adjlist[start]) {
        d[tmp.first] = tmp.second;
    }

    // 시작 노드 방문 처리
    visit[start] = 1;

    // 다익스트라 시작
    for (int i = 0; i < n - 1; i++) {
        min = max;
        current = 0;
		
        // 현재 최단 거리 중 방문하지 않은 노드의 인덱스와 거리를 찾는다.
        for (int j = 0; j < n;j++) {
            if (d[j] < min && !visit[j]) {
                min = d[j];
                current = j;
            }
        }
        
        // 찾은 노드를 방문 처리
        visit[current] = 1;

        // 현재 노드의 인접 노드 중 방문하지 않은 노드의 거리를 비교하여 갱신
        for (auto cur : adjlist[current]){
            if (!visit[cur.first]) {
                if (d[current] + cur.second < d[cur.first]) {
                    d[cur.first] = d[current] + cur.second;
                }
            }
        }   
    }

    // 최종 결과 출력
    for (int i = 0; i < n; i++) {
        cout << d[i] << " ";
    }
    cout << "\n";
    
    return 0;
}

우선순위 큐 다익스트라(Dijkstra) 알고리즘 - O(N log N)

 위의 코드에서는 거리를 비교하고 갱신하기 전에 방문하지 않은 노드 중 최단 거리인 노드를 확인하여 가장 짧은 거리를 선택하도록 했다. 하지만 같은 내용을 매번 반복하였기 때문에 알고리즘의 시간복잡도가 늘었다.

최초 알고리즘이 나온 이후 이런 부분을 개선한 다익스트라 알고리즘이 공개되었는데, 우선순위 큐의 특성을 활용한 다익스트라 알고리즘이다.

 우선 순위 큐는 항상 우선순위가 높거나 낮은 값을 pop한다. (우선순위 큐는 시간복잡도가 삽입/삭제 시 항상 O(log N)인 최소힙과 최대 힙을 이용하여 주로 구현된다고 한다. 우선순위 큐를 직접 구현하고 싶다면 https://hwan001.tistory.com/199 글을 참고하자.)

 C++에서는 우선순위 큐를 직접 구현할 필요가 없다.

STL을 통해 해당 자료구조를 제공하기 때문인데, priority_queue 타입을 사용하면된다.

해당 자료형에 대한 내용은 위의 우선순위 큐 글에 남겨두겠다.

코드로 구현해보자.

#include <iostream>
#include <utility>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

void dijkstra_pq(int start, vector<pair<int, int>>* graph, int *d) {
    int _current, _next, _distance, _nextDistance;

    d[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        _current = pq.top().second;
        _distance = -pq.top().first;

        pq.pop();

        if (d[_current] < _distance)
            continue;

        for (int i = 0; i < graph[_current].size(); i++) {
            _next = graph[_current][i].second;
            _nextDistance = _distance + graph[_current][i].first;

            if (_nextDistance < d[_next]) {
                d[_next] = _nextDistance;
                pq.push({-_nextDistance, _next});
            }
        }
    }
}

int main() {
    int n, m, start, max = 999999999;
    int u, v, a;

    cin >> n >> m;

    int* d = new int[n];
    for (int i = 0; i < n; i++) {
        d[i] = max;
    }

    vector<pair<int, int>>* adjlist = new vector<pair<int, int>>[n];

    cin >> start;

    for (int i = 0; i < m; i++) {
        cin >> u >> v >> a;
        adjlist[u - 1].push_back({ a, v - 1 });
    }

    dijkstra_pq(start-1, adjlist, d);

    for (int i = 0; i < n; i++) {
        if (d[i] == max) {
            cout << "INF ";
        }
        else {
            cout << d[i] << " ";
        }
    }
    cout << "\n";
    
    return 0;
}

큐는 FIFO, 우선순위 큐는 우선순위가 높은거 먼저 나옴

구현

1. 리스트를 이용한 구현 (큐로도 가능?)

2. 힙을 이용한 구현

시간 복잡도

1 -> 0(1), 삭제 시는 O(N) // 찾아서 삭제해야됨

2. -> O(log N) / O(log N) -> 삽입 삭제가 시간복잡도 동일하고

데이터의 입출력 과정이 힙정렬과 동일, 이때는 O(N log N)

힙은 완전 이진트리의 일종, 항상 루트 노드 제거

최소 힙은 루트 노드가 가장 작은 값을 가짐, 값이 작은 데이터가 우선 제거됨

ㄴ 넣었다 빼면 걍 오름차순

최대 힙은 루트 노드가 가장 큰 값이고 값이 가장 큰 데이터가 우선 제거됨, 내림차순

완전이진트리 : 루트부터 왼쪽, 오른쪽으로 순서대로 데이터가 삽입되는 트리

최소힙 구성함수 (min-heapify()), 상향식과 하향식으로 구현 가능, 최소 힙 성질을 만족하지 않는 서브 트리를 만족하도록 만들어 주는 함수, 새로운 원소 삽입 시 O(log N) 으로 힙 성질을 유지 가능

c++에서는 priority_queue 제공 가장 큰 값이 먼저 나오도록 동작함-> 오름차순으로 하려면 -를 붙여 부호를 반대로 바꿔줌

#include<bits/stdc++>

using namespace std;

void main(){
    priority_queue<int>& h;
    
    // 내림차순 (기본은 루트 노드가 가장 큰값을 가짐)
    h.push(1);
    h.push(3);
    
    // 오름차순 (부호가 반대면 1이 위로 올라감, 꺼낼때도 -붙여주기)
    h.push(-1);
    h.push(-3);
    
    h.top();
    // 오름차순 시 -h.top();
    
    h.pop();
}

priority_queue

push, pop, top, empty, size 제공

#include <queue>

내림차순(가장 큰값부터 출력) 시 priority_queue<int> pq;

#include <functional> // -> less, greater 

가장 작은 값부터 pop, 오름차순으로 사용 시 priority_queue<int, vector<int>, less<int>> pq;

문제

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

접근 방식

• BFS로 영역나누기, 8방향 검사

코드

#include <iostream>
#include <utility> 
#include <queue> 
#include <cstring>

using namespace std;

int main() {
    int w = 1, h = 1;
    queue<pair<int, int>> q;
    int direc[8][2] = { {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1} };
    int visit_value, _x, _y;
    pair<int, int> front;

    while (true) {
        cin >> w >> h;

        if (w + h == 0){
            break;
        }

        int** _map = new int* [h];
        int** visit = new int* [h];
        for (int i = 0; i < h; i++) {
            _map[i] = new int[w];
            visit[i] = new int[w];
            memset(visit[i], 0, sizeof(int) * w);
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> _map[i][j];
            }
        }

        visit_value = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (visit[i][j] == 0 && _map[i][j] == 1) {
                    q.push({ i, j });
                    visit[i][j] = ++visit_value;
                }

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

                    for (int i = 0; i < 8; i++) {
                        _x = front.first + direc[i][0];
                        _y = front.second + direc[i][1];

                        if (_x >= h || _x < 0) {
                            continue;
                        }

                        if (_y >= w || _y < 0) {
                            continue;
                        }

                        if (visit[_x][_y] != 0) {
                            continue;
                        }

                        if (_map[_x][_y] != 1) {
                            continue;
                        }

                        visit[_x][_y] = visit_value;
                        q.push({ _x, _y });
                    }
                }
            }
        }

        cout << visit_value << "\n";

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

        for (int i = 0; i < h; i++) {
            delete(_map[i]);
            delete(visit[i]);
        }
    }
    
    return 0;
}

결과

문제

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

접근 방식

• 정렬 후 이진탐색 구현 매개변수로 정렬된 벡터 전달 -> 10% 시간 초과
• 입출력 속도 개선 -> 10% 시간 초과
• 정렬된 벡터를 전역 변수로 접근(매개변수로 전달하는 과정에서 시간이 많이 걸릴 수 있다고 함) -> 통과

코드

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

using namespace std;

vector<int> func_1920_An;

int func_1920_isExist(int find_value) {
    int res = 0;
    int start_index = 0, end_index = func_1920_An.size();
    int index = (int)floor((start_index + end_index) / 2);

    while(start_index < end_index) {
        if (find_value == func_1920_An.at(index)) {
            res = 1;
            break;
        }

        if (start_index == index){
            break;
        }

        if (find_value > func_1920_An.at(index)) {
            start_index = index;
        }

        if (find_value < func_1920_An.at(index)) {
            end_index = index;
        }

        index = (int)floor((start_index + end_index) / 2);
    }

    return res;
}


int main() {
    int n, m, tmp;
    vector<int> Am;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        func_1920_An.push_back(tmp);
    }

    sort(func_1920_An.begin(), func_1920_An.end());

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        Am.push_back(tmp);
    }

    for (auto m_tmp : Am) {
        cout << func_1920_isExist(m_tmp) << "\n";
    }
    
    return 0;
}

결과

문제

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

접근 방식

• 다이나믹 프로그래밍 분류에 있는 문제이므로 점화식을 찾아 DP로 구현

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

위 규칙을 기반으로 점화식을 찾아보자.

가능한 연산과 규칙을 나열해보면 최종적으로 dp[n] = 1 + min(dp[n-1], dp[n/2], dp[n/3]) 이라는 점화식을 찾을 수 있다. 점화식의 의미는 현재 수에 대한 연산 횟수 증가(1) + 가능한 이전 연산 중 최소 값 ( min(...) ) 이다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    int min, num;

    cin >> num;

    int* dp = new int[num+2];
    memset(dp, 0, sizeof(int) * (num+2));
    
    for (int i = 2; i <= num; i++) {
        dp[i]++;
        min = 0;

        if (min > dp[i - 1] || min == 0)
            min = dp[i - 1];

        if (i % 2 == 0) {
            if (min > dp[i / 2])
                min = dp[i / 2];
        }

        if (i % 3 == 0) {
            if (min > dp[i / 3])
                min = dp[i / 3];
        }

        dp[i] += min;
    }

    cout << dp[num] << "\n";
    
    return 0;
}

결과

​

문제

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

접근 방식

• 기본 Map과 색약 Map을 만들어 BFS로 구역을 나눠줌
• 틀렸습니다. 코드와 정답 코드 차이

// 틀린 코드
if (map_visit[i][j] == 0) {
	q.push({i, j});
    visit_value++;
}

// 정답 코드
if (map_visit[i][j] == 0) {
	q.push({i, j});
	map_visit[i][j] = ++visit_value;
}

코드

#include <iostream>
#include <cstring>
#include <utility> 
#include <queue> 

using namespace std;

void func_10026_bfs(queue<pair<int, int>> q, char **_map, int **visited, int visit_value, int n) {
    pair<int, int> tmp_coord;
    int _x, _y;
    char tmp_color;
    int direct[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

    while (!q.empty()) {
        tmp_coord = q.front();
        tmp_color = _map[tmp_coord.first][tmp_coord.second];
        q.pop();

        for (int i = 0; i < 4; i++) {
            _x = tmp_coord.first + direct[i][0];
            _y = tmp_coord.second + direct[i][1];

            if (_x >= n || _x < 0)
                continue;
            
            if (_y >= n || _y < 0)
                continue;

            if (visited[_x][_y] != 0)
                continue;

            if (_map[_x][_y] != tmp_color)
                continue;

            visited[_x][_y] = visit_value;
            q.push({_x, _y});
        }
    }
}

int main() {
    queue<pair<int, int>> q;
    int visit_value, map_max, map_rg_max;
    
    int n;
    cin >> n;

    char** map_origin = new char* [n];
    char** map_rg = new char* [n];
    int** map_visit = new int* [n];
    int** map_rg_visit = new int* [n];

    for (int i = 0; i < n; i++) {
        map_origin[i] = new char[n];
        map_rg[i] = new char[n];
        map_visit[i] = new int[n];
        map_rg_visit[i] = new int[n];

        memset(map_visit[i], 0, sizeof(int) * n);
        memset(map_rg_visit[i], 0, sizeof(int) * n);
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            cin >> map_origin[i][j];
            
            if (map_origin[i][j] == 'R')
                map_rg[i][j] = 'G';
            else
                map_rg[i][j] = map_origin[i][j];
        }
    }

    visit_value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_visit[i][j] == 0) {
                q.push({i, j});
                map_visit[i][j] = ++visit_value;
            }

            func_10026_bfs(q, map_origin, map_visit, visit_value, n);
        }
    }


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

    visit_value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_rg_visit[i][j] == 0) {
                q.push({ i, j });
                map_rg_visit[i][j] = ++visit_value;
            }

            func_10026_bfs(q, map_rg, map_rg_visit, visit_value, n);
        }
    }

    map_max = 0;
    map_rg_max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_max < map_visit[i][j]) {
                map_max = map_visit[i][j];
            }

            if (map_rg_max < map_rg_visit[i][j]) {
                map_rg_max = map_rg_visit[i][j];
            }
        }
    }
    
    cout << map_max << " " << map_rg_max << "\n";
    
    return 0;
}

결과

1. 문제

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

2. 접근 방식

• Stack 활용

3. 코드

#include <iostream>
#include <stack> 

using namespace std;

int main() {
    int test_case, tmp, sum=0;
    cin >> test_case;

    stack<int> stack_zero;

    for (int i = 0; i < test_case; i++) {
        cin >> tmp;
        if (tmp==0) {
            stack_zero.pop();
        }
        else {
            stack_zero.push(tmp);
        }
    }
    
    while (!stack_zero.empty()) {
        sum += stack_zero.top();
        stack_zero.pop();
    }

    cout << sum << "\n";
    
    return 0;
}

4. 결과

1. 문제

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

2. 접근 방식

• 1차 : 문제에서 알려준 공식대로 구현 -> 50점, 작은 문자열에서는 잘 동작하지만 큰 문자열에서는 시간초과
• 2차 :  합동식 활용 A * B mod C -> (A mod C) * (B mod C) -> 통과

3. 코드

• 1차 코드

#include<iostream>
#include <cmath> 

typedef unsigned long long ll;

using namespace std;

int main() {
    int str_len;
    cin >> str_len;
    string str;
    cin >> str;

    int a, r = 31, M = 1234567891;
    ll sum = 0;

    for (int i = 0; i < str_len; i++) {
        a = (str[i] - 'a') + 1;
        sum += a * pow(r, i);
    }

    cout << sum % M << "\n";
}

• 2차 코드

#include<iostream>

using namespace std;

typedef unsigned long long ll;

int main() {
    int str_len;
    cin >> str_len;

    string str;
    cin >> str;

    ll r, sum = 0, a;
    int M = 1234567891;

    for (int i = 0; i < str_len; i++) {
        a = (str[i] - 'a') + 1;

        r = 1;
        for (int j = 0; j < i; j++) {
            r *= 31;
            r %= M;
        }

        sum += a * r;
        sum %= M;
    }
    
    cout << sum;
}

4. 결과