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

순열 (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/ - 조합 코드 (블로그)

최단 거리 알고리즘

 그래프에서 간선들 사이의 가중치와 방향이 있을 때, 한 정점에서 다른 정점들까지의 최단 거리를 구할 수 있는 알고리즘은 다익스트라, 벨만포드, 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;

목적

• 하노이의 탑 알고리즘을 가시화하여 이해를 쉽게함
• 가시화된 알고리즘을 재귀 함수로 구현함
• 구현할 함수는 아래 2개임 ( A탑에 위치한 원반 개수는 N)
• int count_hanoi(int n) : A에서 C까지 N개의 원판을 이동시키는데 필요한 전체 개수
• void hanoi(int n, int from, int to) : n번째 원판을 From에서 To로 이동시킴

탑 이동 알고리즘 (Hanoi Function)

• 하노이 탑의 이동을 재귀로 구현할 땐 아래 이미지의 이동 방식을 알면 됨

• N이 2보다 더 큰 경우도 가장 밑에 있는 N번째 원판과 그위의 나머지 원판으로 부분을 나누면,
  위와 같은 방식으로 이동이 가능함

• hanoi(2, A, B)와 hanoi(2, B, C)의 이동을 직접 나열해보면 아래와 같다

• hanoi(n, from, to) 함수는 아래와 같은 규칙을 갖는다. 

원판의 개수로 전체 이동 횟수 구하기 (Count_Hanoi Function)

• 하노이 탑의 이동 횟수는 아래와 같은 형태의 수열을 이루고 있다.

• 원판의 개수가 N일 때, 원판을 이동 시키는 횟수는 '2의 N제곱 -1' (2^n -1)
• 제곱연산은 1 << N으로도 표현이 가능함 (비트연산)
  Ex) 0001 << 3 -> 1000(2), 8(10) 
  원판 개수 = 1 << N -1

소스 코드

• 아래 코드에선 탑을 1~3으로 표현함.

#include<iostream>

using namespace std;

void count_hanoi(int n){
	cout << (1 << n) -1 << "\n";
}

void hanoi(int n, int from, int to) {
	if (n == 1){
		cout << from << " " << to << "\n";
	}else{
		hanoi(n - 1, from, 6 - from - to);
		cout << from << " " << to << "\n";
		hanoi(n - 1, 6 - from - to, to);
	}
}

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

	count_hanoi(n);
	hanoi(n, 1, 3);
    
	return 0;
}

결과

목적

• 탐색 알고리즘에서 사용되는 표현 방식을 이해하고 직접 구현
• 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색) 알고리즘에 대해 이해하고 직접 구현
• 탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색) 알고리즘에 대해 이해하고 직접 구현

인접리스트와 인접 행렬

위 와 같은 그래프가 있을 때, 이 그래프를 표현하는 방식은 크게 2가지(인접리스트, 인접행렬)가 있다.

각 표현 방식을 구현해보면 다음 코드와 같다.

1) 간선을 인접리스트로 변환

#include<iostream>
#include<cstring>
#include<vector>
#include<map>

using namespace std;

// 만들어진 그래프를 출력
void print_adjacency_list(map<int, vector<int>> graph) {
	for (auto node : graph) {
		cout << node.first << " : ";
		for (auto ns : node.second) {
			cout << ns << " ";
		}
		cout << "\n";
	}
}

int main() {
	int n, m, u, v;
	
        // 최초 입력 받기
	cin >> n >> m >> start_node;

	// 그래프를 인접리스트 형식으로 표현
	map<int, vector<int>> graph;

	// 간선의 개수만큼 노드에 추가
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
        
		// 각 노드별로 연결된 간선을 서로 추가(무방향 또는 양방향 그래프)
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
    
    // 생성된 인접리스트 출력
    print_adjacency_list(graph);
    
    return 0;
}

2) 간선을 인접행렬로 변환

#include<iostream>

using namespace std;

int main() {
	int n, m, u, v;

	cin >> n >> m;

	// 인접행렬 생성
	int** graph = new int* [n];
	for (int i = 0; i < n; i++) {
		graph[i] = new int[n];
	}

	// 인접행렬 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			graph[i][j] = 0;
		}
	}

	// 간선 입력
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
        
		u--;
		v--;
        
		// 무방향 그래프
		graph[u][v] = graph[v][u] = 1;
	}


	// 인접행렬 출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}
    
	return 0;
}

3) 인접행렬을 문자열로 입력받기

#include<iostream>

using namespace std;

int main() {
	int n;
	string str;

	cin >> n;

	int** map = new int* [n];
	for (int i = 0; i < n; i++) {
		str = "";
		map[i] = new int[n];

		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			map[i][j] = str[j] - '0';
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j< n; j++) {
			cout << map[i][j];
		}
		cout << "\n";
	}
    
	return 0;
}

4) 인접행렬을 인접리스트로 변환

#include<iostream>
#include<vector>

using namespace std;

vector<int> *Convert_adjMatrix_to_adjList(int n, int** matrix) {
	vector<int> * adjlist = new vector<int>[n+1];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (matrix[i][j] == 1 && i != j) {
				adjlist[i+1].push_back(j+1);
			}
		}
        sort(adjlist[i+1].begin(), adjlist[i+1].end());
	}

	return adjlist;
}

int main() {
	int n;
	string str;

	cin >> n;

	int** map = new int* [n];
	for (int i = 0; i < n; i++) {
		str = "";
		map[i] = new int[n];

		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			map[i][j] = str[j] - '0';
		}
	}

	vector<int> *adl = Convert_adjMatrix_to_adjList(n, map);

	for (int i = 1; i <= n; i++) {
		cout << i << " : ";
		for (auto node : adl[i]) {
			cout << node << " ";
		}
		cout << "\n";
	}
    
	return 0;
}

DFS (깊이 우선 탐색)

• 재귀로 DFS 구현

#include<iostream>
#include<cstring>
#include<vector>
#include<map>

using namespace std;

void dfs_recursion(int n, vector<int>* graph, bool* visited) {
	cout << "start\nCurrent Node : " << n <<  "";

	// 시작노드의 방문 여부를 체크
	visited[n] = true;

	for (auto node : graph[n]) {
		cout << "\nN : " << n << ", Node : " << node << ", Visited : " << visited[node] << " ";
		// 노드가 방문이 되어있는지 확인
		if (!visited[node]) {
			cout << "-> Next node : " << node << "\n";
            
			// 방문 안된 노드의 키값을 넣음
			func_1260_dfs_recursion(node, graph, visited);
		}
	}
	cout << "\nend";
}

int main() {
	int n, m, start_node, u, v;
	
	cin >> n >> m >> start_node;

	vector<int> *graph = new vector<int>[n+1];
    
	bool *visited = new bool[n+1];
	memset(visited, 0, sizeof(bool) * (n+1));

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	/*
	// 오름차순으로 각 벡터를 정렬시킴 (이부분 주석 해제 시 1 2 3 4 5 순서로 진행)
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	*/

	dfs_recursion(start_node, graph, visited);
    
    return 0;
}

• 스택으로 DFS 구현

//

BFS (너비 우선 탐색)

• 큐로 BFS 구현

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

using namespace std;

void bfs_queue(int n, vector<int> * graph, bool* visited) {
	queue<int> q;
	int now_node;

	visited[n] = true;
	q.push(n);

	while (!q.empty()) {
		now_node = q.front();
		q.pop();
		cout << now_node << " ";

		for (auto node : graph[now_node]) {
			if (!visited[node]) {
				visited[node] = true;
				q.push(node);
			}
		}
	}
	cout << "\n";
}

int main() {
	int n, m, start_node, u, v;
	
	cin >> n >> m >> start_node;

	vector<int> *graph = new vector<int>[n+1];

	bool *visited = new bool[n+1];
	memset(visited, 0, sizeof(bool) * (n+1));

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}


	bfs_queue(start_node, graph, visited);
    
    return 0;
}

1. 달팽이 배열

 - 외곽부터 정사각형을 채우고 대각선 아래로 이동하여 반복

2. 방법별 코드 정리

 2-1) 코드 

  - 외부부터 한바퀴씩 작성

  - 시계방향으로 회전하는 달팽이 배열을 이동 좌표를 미리 계산하는 방식으로 작성

# 범위내 좌표이동
def add_direction(x, y, arr_direction, int_direction, int_k):
    a, b = 0, 0
    
    # x 좌표 이동
    next_x = x + arr_direction[int_direction][0]
    if next_x >= 0 and next_x < int_k:
        a = next_x
    # y 좌표 이동
    next_y = y + arr_direction[int_direction][1]
    if next_y >= 0 and next_y < int_k:
        b = next_y
    
    return a, b

def snailArray_Generator(k):
    # k가 0보다 작거나 같으면 종료
    if k <= 0:
        return []

    # 이동할 좌표 구하기
    arr_Move = []
    # right, down, left, up
    arr_direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    # 최초 시작 좌표
    x, y = 0, 0

    # 루프 한번에 한 바퀴
    for n in range(k-1, 0, -2):
        # 각 방향으로
        for int_direction in range(4):
            # n개 씩 채우기
            for _ in range(n):
                arr_Move.append((x, y))
                # 좌표 이동
                x, y = add_direction(x, y, arr_direction, int_direction, k)
        
        # 다음 시작 좌표로 이동
        x, y = x+1, y+1

    # 마지막 이동한 위치가 array에 이미 있으면 추가 안함
    if not (x, y) in arr_Move:
        arr_Move.append((x, y))

    # 값 넣기
    arr_map = [[0 for _ in range(k)] for _ in range(k)]
    value = 0
    for move in arr_Move:
        value += 1
        arr_map[move[1]][move[0]] = value

    return arr_map


# map 출력
for map in snailArray_Generator(0):
    print(map)

 2-1) 결과

1. 가설 적용 코드 (C++)

typedef unsigned long long ll;

/*
*  input : ll input (정수)
*  output : int (1 or 0)
*  unsigned long long 형태의 정수를 넣으면 해당 수가 소수인지 여부를 알려준다.
*  소수 판별 custom 버전
*/
int is_prime_number_custom(ll input)
{
    if (input < 2) {
        return 0;
    }

    for (ll j = 2; j <= (ll)(input / j); j++)
    {
        if (input % j == 0)
        {
            return 0;
        }
    }

    return 1;
}

2. 가설 적용 코드 (Python)

def func1(input):
    if input < 2:
    	return 0
    for j in range(2, int(input/j)+1):
        if input % j == 0:
            return 0
    return 1

3. 에라토스테네스의 체 (c++)

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

4. 최소 공배수, 최대 공약수

int func_2609_gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    else {
        return func_2609_gcd(b, a % b);
    }
}

int func_2609_lcm(int a, int b) {
    return (a * b) / func_2609_gcd(a, b);
}

코드 1 - i(2 ~ N)를 j(2 ~ i)로 나누기

 N을 입력받고 i를 2~N까지 1씩 더한다.

j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님.

위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다.

각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다.

#include<stdio.h>
#include<math.h>

int main() {
    int i, j, cnt=0, flag=1;
    unsigned int min, max;

	// 범위 입력
    printf("min : ");
    scanf_s("%d", &min);
    printf("max : ");
    scanf_s("%d", &max);

	// 2보다 작은 최소 범위가 입력되면 2로 고정
    if (min < 2) min = 2;
	
    printf("입력 받은 범위 내의 소수");
    // i가 입력받은 최소 범위부터 최대 범위까지 반복
    for (i = min; i < max; i++) 
    {
        flag = 1; // 현재수가 소수라고 가정하고 시작
        
    	// j는 2부터 현재의 i 전까지 증가
        for (j = 2; j < i; j++) 
        {
        	// i와 j를 나눈 나머지가 존재하면 소수가 아님
            if (i % j == 0) 
            {
                flag = 0; // flag가 0이면 현재 수(i)는 소수가 아님
                break; // 더 이상 j로 나누어 줄 필요가 없으므로 탈출
            }
        }
		
        // 위에서 판단된 결과가 소수이면(0이 아니면)
        if (flag) 
        {
            cnt++; // 개수를 증가시킴 (입력 받은 범위 내의 소수 개수)
            printf("%d\t", i); // 출력
            
            if (cnt % 5 == 0) 
            {
            	printf("\n"); // 5개 단위로 끊음
            }
        }
    }

    printf("\n%d ~ %d 사이의 소수 개수 : %d개\n", min, max, cnt);

    return 0;
}

코드 2 - i (2 ~ N)를 j (2 ~ i / j)로 나누기

#include<stdio.h>
#include<math.h>
#include<time.h>

void test(int min, int max) 
{
    clock_t start, end;
    float res;
    int i, j, cnt = 0, flag;

    start = clock();
    for (i = min; i < max; i++)
    {
        flag = 1;
		
        // 기존과 달라진 부분, j로 확인 하는 범위를 i와 현재 j의 나눈 몫까지로 줄였음
        for (j = 2; j <= (int)(i / j); j++)
        {
            if (i%j == 0)
            {
                flag = 0;
                break;
            }
        }

        if (flag)
        {
            cnt++;
        }
    }
    end = clock();

    res = (float)(end - start) / CLOCKS_PER_SEC;

    printf("%d~%d : %d개\t%.3fms\n", min, max, cnt, res);
}

int main() {
    int arr[] = {100, 1000, 10000, 100000, 1000000, 10000000, 1000000000};

    for (int i = 0; i < (int)(sizeof(arr) / sizeof(int)); i++)
    {
        test(2, arr[i]);
    }
    return 0;
}

#include <iostream>

using namespace std;

typedef unsigned long long ll;

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (ll i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (ll j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    clock_t start, end;
    ll N, M;
    ll sum=0;

    start = clock();
    cin >> N >> M;
    bool* arr = Sieve_of_Eratosthenes(M);

    for (ll i = N; i <= M; i++) {
        if (arr[i]) {
            sum++;
        }
    }

    end = clock();
    float res = (float)(end - start) / CLOCKS_PER_SEC;
    cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
    
    return 0;
}

#include "stdafx.h"
#include <ctype.h>
#include <math.h>

int gcd(int a, int b);
int RSA(int n, int m, int d); 

int main(){
    // 키 생성
    //int p = 13, q = 37;
    //int p = 11, q = 13;
    int p = 17, q = 13;

    int n, e, d, f;

    n = p * q;
    f = (p-1) * (q-1);

    // e 결정
    for (int i = 2; i < f; i++) {
        // 서로소 판단
        if (gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1) {
            e = i;
            break;
        } 
    }

    //d 결정
    for (int i = 1; i < n; i++) {
        if ((1 + f * i) % e == 0) {
            d = (1 + f * i) / e; 
            break;
        }
    }

    // 소수에 따라 자동 계산된 변수 값
    printf("p\tq\tn\te\td\tf\n");
    printf("%d\t%d\t%d\t%d\t%d\t%d\n\n", p, q, n, e, d, f);

    // 암호화
    int msg = 'b';
    printf("msg : %c\n", msg);

    int c = RSA(n, msg, e);
    printf("c : %c\n", c);

    // 복호화
    int msg2 = RSA(n, c, d);
    printf("msg : %c\n", msg2);

    return 0;
}

// 암복호화를 위한 모듈로 연산을 수행 (n, d는 공개키/ 개인키, m은 메시지)
int RSA(int n, int m, int d) {
    int bin1[10] = { 0, };
    int tmp, j = 1;
    unsigned long long x_tmp = 1; 
    int x[10]; // m^2^0~9 mod n

    // 거듭 제곱법 구현을 위한 값 미리 저장
    x[0] = (unsigned long long)pow(m, 1) % n;
    for (int i = 1; i < 10; i++) {
        x[i] = (x[i - 1] * x[i - 1]) % n;
    }

    // 지수를 이진수로 변환 (구현 편의성을 위해 그냥 역으로 넣음) 
    for (int i = 0; d > 0; i++) {
        tmp = d % 2;
        d /= 2;
        bin1[i] = tmp;
    }

    // 이진수가 1일 떄만 미리 계산된 값 곱셈
    for (int i = 0; i < 10; i++) {
        if (bin1[i] == 1) {
            x_tmp *= x[i];
        }
    }

    return x_tmp % n; // 곱셈 합을 모듈로해서 반환
}

// 최대 공약수
int gcd(int a, int b) {
    int tmp, n;

    if (a<b) {
        tmp = a;
        a = b;
        b = tmp;
    }

    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }

    return a;
}

4. 참고 사항

 - 메르센 소수 같은 빅넘버를 처리하기엔 부적합함 (이 경우  OpenSSL 활용)

 - 거듭 제곱법 구현 함수 내 배열을 10으로 고정해두었으나 배열 크기 조정으로 어느정도 큰 소수

   (x_tmp 최대값, unsigned long long) 까지는 연산이 가능함.

- 문자를 하나씩 암호화 하면 같은 문자는 같은 값으로? 암호화됨. (블록 단위 암호화 필요)

  ex) testtest -> abcaabca 

- 자료형 크기 고려했을 때 문자를 대충 4바이트 단위까지 합쳐서 연산가능할 듯

  ex) asdf  -> 16진수변환 한번에 연산 등등

내용 수정

2024-01-21(일)

- 기존 코드에서 잘못된 부분을 확인하여 수정이 필요한 부분을 적어두었음

- e를 결정하는 부분에서 e와 f가 서로소인 부분이 확인 되어야 하기 때문에 기존 코드의 gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1 부분이 제거 되고 아래처럼 수정되어야 함

f = (p-1) * (q-1);

// e 결정
for (int i = 2; i < f; i++) {
    if (gcd(i, f) == 1) {
        e = i;
        break;
    }
}