깊이 우선 탐색 (depth First Search), DFS 알고리즘은 맹목적 탐색 기법 중 하나이다.

맹목적 탐색 기법이란, 정해진 순서에 따라 상태 공간 그래프를 점진적으로 생성해가면서 해를 탐색하는 방법이다.

맹목적 탐색 기법에는 깊이 우선 탐색, 너비 우선 탐색, 반복적 깊이심화 탐색 등이 있으며 이 글에서는 깊이 우선 탐색을 설명할 것이다. (너비 우선 탐색은 여기 -> https://velog.io/@fluid_silver/BFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

먼저 그림을 보자. (출처 : 학교 수업 pdf)

한 방향으로 끝까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법이다. (백트래킹)

목표 정점이 있다면, 모든 정점을 방문하지 않고 목표 정점에 도달했을 때 종료한다. 스택(stack)을 사용하여 구현한다.

알고리즘

1. 시작 정점을 스택에 저장
2. 스택의 맨 뒤 정점의 이웃을 neighbor에 저장
3. neighbor 중에 방문하지 않은 정점 하나를 택하여 스택에 저장, 모두 방문한 정점인 경우 선택된 정점을 스택에서 제거
4. 2~3 과정을 반복
5. 스택에 포함된 정점이 없을 때 알고리즘을 마침

코드

백준 1260번 DFS와 BFS : https://www.acmicpc.net/problem/1260

C++

#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
typedef struct Node Node;
struct Node {                    // Node
    int data = 0;
    Node* next = NULL;
};
int main() {
    int N, M, V;
    cin >> N >> M >> V;
    vector<Node> head(N + 1);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        Node* tmp = new Node();    // linked list
        tmp->data = b;
        tmp->next = head[a].next;
        head[a].next = tmp;
        Node* tmp2 = new Node();
        tmp2->data = a;
        tmp2->next = head[b].next;
        head[b].next = tmp2;
    }
    stack<int> s;
    map<int, int> visited;        // 방문한 정점 저장
    s.push(V);
    cout << V << " ";
    visited.insert({ V, 1 });
    while (size(s) != 0) {        // 스택에 정점이 없을 때까지
        int curr = s.top();        // 스택의 맨 뒤 정점
        Node head_tmp = head[curr];
        vector<int> neighbor;
        while (head_tmp.next != NULL) {    // 이웃 정점 저장
            head_tmp = *head_tmp.next;
            neighbor.push_back(head_tmp.data);
        }
        if (size(neighbor) == 0) {
            s.pop();
        }
        sort(neighbor.begin(), neighbor.end());    // 번호가 작은 것 방문
        for (int i = 0; i < size(neighbor); i++) {
            if (visited.find(neighbor[i]) == visited.end()) {    // 방문하지 않은 정점
                s.push(neighbor[i]);        // 스택에 저장
                cout << neighbor[i] << " ";
                visited.insert({ neighbor[i], 1});
                break;
            }
            else if (i == size(neighbor) - 1) {        // 모두 방문한 정점인 경우
                s.pop();                // 정점 제거
            }
        }
    }
    return 0;
}

Python

# 나중에 추가해보겠음

특징

DFS는 메모리 공간 사용이 효율적이지만 목표 정점을 찾으면 종료하기 때문에 최단 경로는 보장할 수 없다.

XOR Linked List는 메모리를 효율적으로 이용하는 Doubly Linked List이다.

원래 Doubly Linked List는 이전 노드와 다음 노드의 주소를 저장하기 위해 하나의 노드에 두 개의 공간을 필요로 한다.

그런데 XOR Linked List는 하나의 공간에 이전 노드와 다음 노드의 주소 둘 다 저장한다. 그러므로 메모리 사용이 줄어든다!

그러면 각 노드마다 저장된 npx로 이전 노드와 다음 노드의 주소를 어떻게 구할까?

이전 노드의 주소를 구하기 위해서는 npx와 다음 노드의 주소, 다음 노드의 주소를 구하기 위해서는 npx와 이전 노드의 주소가 필요하다. (진행 방향 기준으로 이전 노드의 주소를 저장하면 됨)

예를 들어, 노드 B에서 C로 가는 주소를 구하고 싶다면 npx(B)와 addr(A)(이전 노드의 주소)를 사용한다.

npx(B) XOR addr(A) = ( addr(A) XOR addr(C) ) XOR addr(A) = addr(A) XOR addr(C) XOR addr(A) = addr(C)

이렇게 C의 주소를 구할 수 있다.

.

.

.

(위 내용을 이용하여 XOR Binary Search Tree를 만들 수 있는가?)

너비 우선 탐색 (Breadth First Search), BFS 알고리즘은 맹목적 탐색 기법 중 하나이다.

맹목적 탐색 기법이란, 정해진 순서에 따라 상태 공간 그래프를 점진적으로 생성해가면서 해를 탐색하는 방법이다.

맹목적 탐색 기법에는 깊이 우선 탐색, 너비 우선 탐색, 반복적 깊이심화 탐색 등이 있으며 이 글에서는 너비 우선 탐색을 설명할 것이다. (깊이 우선 탐색은 여기 -> https://velog.io/@fluid_silver/DFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

먼저 그림을 보자. (출처 : 학교 수업 pdf)

시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. (결국 다 방문함) 큐(queue)를 사용하여 구현한다.

알고리즘

1. 시작 정점을 큐에 저장
2. 큐의 맨 앞 정점의 이웃을 neighbor에 저장
3. 선택된 정점을 큐에서 제거
4. neighbor에 저장된 정점(+방문하지 않은 정점)들을 큐에 저장
5. 2~4 과정을 반복
6. 큐에 포함된 정점이 없을 때 알고리즘을 마침

코드

백준 1260번 DFS와 BFS : https://www.acmicpc.net/problem/1260

C++

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef struct Node Node;
struct Node {                    // Node
    int data = 0;
    Node* next = NULL;
};
int main() {
    int N, M, V;
    cin >> N >> M >> V;
    vector<Node> head(N + 1);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        Node* tmp = new Node();    // linked list
        tmp->data = b;
        tmp->next = head[a].next;
        head[a].next = tmp;
        Node* tmp2 = new Node();
        tmp2->data = a;
        tmp2->next = head[b].next;
        head[b].next = tmp2;
    }
    queue<int> q;
    map<int, int> visited;        // 방문한 정점 저장
    q.push(V);
    cout << V << " ";
    visited.insert({ V, 1 });
    while (size(q) != 0) {        // 큐에 정점이 없을 때까지
        int curr = q.front();    // 큐의 맨 앞 정점
        Node head_tmp = head[curr];
        vector<int> neighbor;
        while (head_tmp.next != NULL) {    // 이웃 정점 저장
            head_tmp = *head_tmp.next;
            neighbor.push_back(head_tmp.data);
        }
        q.pop();                // 선택된 정점 큐에서 제거
        sort(neighbor.begin(), neighbor.end());    // 번호가 작은 것 먼저 방문
        for (int i = 0; i < size(neighbor); i++) {
            if (visited.find(neighbor[i]) == visited.end()) {    // 방문하지 않은 정점
                q.push(neighbor[i]);        // 큐에 저장
                cout << neighbor[i] << " ";
                visited.insert({ neighbor[i], 1});
            }
        }
    }
    return 0;
}

Python

# 나중에 추가해보겠음

특징

BFS는 최단 경로 해의 탐색을 보장하지만 모든 이웃 정점을 방문하기 때문에 메모리 공간 사용이 비효율적이다.

제네릭 프로그래밍(generic programming)이란, 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있도록 하는 프로그래밍 방식이다.

즉, 프로그래머가 어떤 자료형을 사용할 지 미리 알 수 없기 때문에 어떤 자료형이든 상관없이 실행할 수 있도록 프로그래밍한 것이다.

이 글에서는 C언어로 제네릭 프로그래밍을 직접 해 볼 것이지만, 이해하기 쉽도록 미리 예시를 들어보자면 C++ STL 중 vector를 생성할 때 vector<int>, vector<double> 등 < > 안에 원하는 자료형을 적어 사용하는 것을 볼 수 있다.

그리고 C++의 템플릿은 제네릭 프로그래밍으로 되어있다.

함수형 포인터

제네릭 프로그래밍을 설명하기 전에, 함수형 포인터를 먼저 설명하겠다. 함수형 포인터란, 말 그대로 함수를 포인터로 사용하는 것인데 예시를 먼저 보자.

#include<stdio.h>
int maxv(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int(* c)(int, int) = maxv;    // 함수형 포인터
    printf("%d", c(5,3));
    return 0;
}

먼저, 큰 값을 반환하는 maxv 함수를 만들었다. 그리고 int(* c)(int, int)라고 쓴 부분이 함수형 포인터를 만든 것이다.

반환값 자료형(ex. int), 함수형 포인터 이름(ex. c), 괄호 안에는 매개변수 자료형(ex. (int, int))을 순서대로 써주면 된다. 그리고 코드에 쓴 것처럼 int(* c)(int, int) = maxv;라고 쓰면 함수형 포인터 c에는 함수 maxv의 주소가 들어가는 것이다.

그 후에는 함수형 포인터 c를 함수처럼 사용할 수 있다. (ex. c(5, 3)과 maxv(5, 3)은 같다.)

void 포인터

void 포인터에 대해서도 간단하게 설명하겠다. 제네릭 프로그래밍을 하면서 void*는 계속 쓰이기 때문에 꼭 알아야 한다.

먼저 포인터는 주소값을 저장해준다. int*를 쓰면 저장된 시작 주소로부터 4byte의 데이터(int형 데이터)를 읽어낼 것이고, double*를 쓰면 저장된 시작 주소로부터 8byte의 데이터(double형 데이터)를 읽어낼 것이다.

그런데 우리는 저장하려는 주소에 int형 데이터가 들어갈지 double형 데이터가 들어갈지 모르기 때문에 임시로 void*를 쓴다.

void*는 주소가 가리키는 데이터의 자료형은 모르겠지만 일단 주소만 저장되어있다. 그렇기 때문에 사용할 때 사용하려는 데이터의 자료형을 가리키는 포인터로 바꿔야한다.

제네릭 프로그래밍 예제

그러면, 제네릭 프로그래밍으로 배열에 원하는 숫자가 있는지 찾아서 위치를 반환하는 함수 linear_search를 만들어보겠다.

이 예제는 배열에 1~100의 숫자가 들어가 있고 (자료형은 찾는 값에 따라 정해짐), 찾는 값이 int, double 등 숫자 자료형으로 이루어져 있지만 자료형이 무엇인지 정해져 있지 않기 때문에 제네릭 프로그래밍을 해야한다.

linear_search 함수 코드

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int linear_search(void* _arr, int size, int esize, void* _key) {
    char* arr = (char*)_arr;
    char* key = (char*)_key;
    for (int i = 0; i < size; i++) {
        int cnt = 0;
        for (int j = 0; j < esize; j++) {    // 자료형 크기만큼 반복하며 숫자 하나를 비교
            if (*(arr + (esize * i) + j) == *(key + j)) {
                cnt++;
            }
        }
        if (cnt == esize) {
            return i;
        }
    }
    return -1;
}

linear_search의 매개변수는 자료형이 void*인 배열, 자료형이 int인 배열의 크기, 자료형이 int인 찾는 값 key의 자료형 크기, 자료형이 void*인 찾는 값으로 이루어져 있다. 배열과 찾는 값의 자료형이 void* 인 이유는 위에서도 말했듯이 자료형에 상관없이 찾을 수 있도록 하기 위해서이다.

그 다음 줄을 보면 배열과 찾는 값을 char*로 바꿔주는데, 그 이유는 1byte인 char*로 어떤 자료형이든 비교할 수 있기 때문이다.

자세히 설명하자면, 위에서 void 포인터는 사용할 때 사용하려는 데이터의 자료형을 가리키는 포인터로 바꿔야한다고 했는데 우리는 자료형을 모르기 때문에 사용하려는 데이터의 자료형으로 바꾸는 코드를 함수 안에 작성할 수 없다.

따라서 byte를 하나씩 비교하며 찾아줄 것인데, char*은 1byte의 데이터를 가리키기 때문에 int형은 1byte를 4번, double형은 1byte를 8번 반복하여 같은지 비교할 수 있다.

그 다음 줄에 나오는 for문이 비교하는 과정을 나타낸다. 배열을 차례대로 돌면서 비교하다가 찾는 값과 같은 값을 발견하면 인덱스를 반환한다. 찾지 못하면 -1을 반환한다.

main 코드 (double형 데이터 찾기)

int main() {
    void* ptr = malloc(sizeof(double) * 100);    // 동적할당 (double형 배열)
    double* a = ptr;    // double형 배열
    for (int i = 0; i < 100; i++) {        // 배열 초기화
        a[i] = i;
    }
    for (int i = 0; i < 100; i++) {        // 배열 출력
        printf("%f\n", *(a+i));
    }
    double key = 24;    // 찾는 값
    int ans = linear_search(a, 100, sizeof(double), &key);
    printf("%d", ans);
    return 0;
}

linear_search 함수의 매개변수 자료형을 보면 원래 void*를 넣어야 하는 자리에 그냥 double*를 넣은 것을 볼 수 있다. void*에 넣을 때는 굳이 void*로 바꿔주지 않고 넣어도 된다. 하지만 헷갈린다면 형변환을 해줘도 좋다.

문제점

int형 데이터를 찾을 때는 문제가 없을 수 있지만, double형 데이터를 찾을 때 배열을 초기화하는 과정을 다르게 하면 부동소수점으로 인해 찾지 못하는 경우가 생긴다.

main 코드 배열 초기화 수정

int main() {
    void* ptr = malloc(sizeof(double) * 100);    // 동적할당 (double형 배열)
    double* a = ptr;    // double형 배열
    for (int i = 0; i < 100; i++) {        // 배열 초기화 다른 방법
        a[i] = sqrt(i) * sqrt(i);
    }
    for (int i = 0; i < 100; i++) {        // 배열 출력
        printf("%f\n", *(a+i));
    }
    double key = 24;    // 찾는 값
    int ans = linear_search(a, 100, sizeof(double), &key);
    printf("%d", ans);
    return 0;
}

배열 초기화를 할 때 넣으려는 값 i에 루트를 씌우고, 다시 제곱을 해줬다. 이렇게 초기화를 하고 배열을 출력해 보면 값이 똑같이 출력되는 것을 볼 수 있다.

하지만 컴퓨터는 찾는 값 24를 찾지 못한다. 그 이유는 우리가 byte를 하나씩 비교해가며 같은 값인지 찾았기 때문이다.

사람이 직접 계산하기로는 루트를 씌우고 다시 제곱을 하는 것은 루트가 그냥 없어진다고 생각할 수 있다. 하지만 컴퓨터는 루트를 계산하고, 계산한 값을 다시 제곱한다. $$\sqrt{24}$$는 무리수이다. 그렇기 때문에 컴퓨터는 정확한 값을 다 적어낼 수가 없다. 정확하지 않은 값을 제곱하여 나타내니 아주 작은 오차가 생기게 된다.

배열을 출력할 때는 아주 작은 오차가 보이지 않았지만, byte를 비교하니까 다른 점이 생긴 것이다.

문제점 해결

문제점을 해결하기 위해 int형일 때와 double형일 때의 숫자 비교 방법을 나누어 함수를 만들어 줄 것이다. 그리고 그 함수를 linear_search 매개변수에 넣어줄 것인데, 이 때 함수형 포인터가 사용이 된다.

새로운 linear_search 함수 코드

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int int_compare(const void* a, const void* b) {
    int* aa = (int*)a;
    int* bb = (int*)b;
    return (* bb > *aa) ? -1 : (*aa > *bb);
}
int double_compare(const void* a, const void* b) {
    double* aa = (double*)a;
    double* bb = (double*)b;
    if (fabs(*bb - *aa) < 0.0001) {
        return 0;
    }
    if (*aa > *bb) {
        return 1;
    }
    else {
        return -1;
    }
}
int linear_search(void* _arr, int size, int esize, void* _key, int (*compare_function)(const void*, const void*)) {
    char* arr = (char*)_arr;
    char* key = (char*)_key;
    for (int i = 0; i < size; i++) {
        if (compare_function(arr + esize * i, key) == 0) {
            return i;
        }
    }
    return -1;
}

int_compare 함수와 double_compare 함수를 설명하기 전에, 새로운 linear_search 함수를 먼저 설명하겠다. 위에 있던 linear_search 함수와 달라진 점은 매개변수에 int (*compare_function)(const void*, const void*)가 추가된 것이다. 이 코드에 함수형 포인터와 void 포인터가 모두 쓰였다.

함수형 포인터를 쓴 이유는 int_compare 함수와 double_compare 함수 중 어떤 함수를 사용할 지 모르기 때문이고, 매개변수에 void 포인터를 쓴 이유는 마찬가지로 자료형이 int형인지 double형인지 모르기 때문이다.

그리고 숫자를 비교하는 부분을 간단하게 함수로 나타내주었다. 두 숫자를 비교했을 때 같은 숫자가 나오면 0을 출력하도록 함수를 만들 것이다.

이제 int_compare 함수와 double_compare 함수를 설명하겠다. 원래는 자료형을 모르기 때문에 byte를 하나하나 비교했다면, int_compare 함수와 double_compare 함수를 사용하게 되면서 int형인지 double형인지 함수는 알게 된다. 그렇기 때문에 int_compare 함수에서 void*로 받은 매개변수를 int*로 형변환하여 숫자를 바로 비교한다.

double_compare 함수는 다르다. 위에서 설명했던 문제점 때문에 우리는 아주 작은 오차는 무시하고 비교하도록 코드를 짜야 한다. 마찬가지로 먼저 void*로 받은 매개변수를 double*로 형변환하고, 두 숫자의 차의 절댓값을 계산한다. 이 차이가 자신이 설정한 아주 작은 오차보다 더 작게 나온다면 같은 숫자라고 판단하는 것이다.

main 코드 (int형 데이터 찾기)

int main() {
    void* ptr = malloc(sizeof(int) * 100);    // 동적할당 (int형 배열)
    int* a = ptr;    // int형 배열
    for (int i = 0; i < 100; i++) {        // 배열 초기화
        a[i] = (int)(sqrt(i) * sqrt(i) + 0.5);
    }
    for (int i = 0; i < 100; i++) {        // 배열 출력
        printf("%d\n", *(a+i));
    }
    int key = 24;    // 찾는 값
    int ans = linear_search(a, 100, sizeof(int), &key, int_compare);
    printf("%d", ans);
    return 0;
}

main 코드 (double형 데이터 찾기)

int main() {
    void* ptr = malloc(sizeof(double) * 100);    // 동적할당 (double형 배열)
    double* a = ptr;    // double형 배열
    for (int i = 0; i < 100; i++) {        // 배열 초기화
        a[i] = sqrt(i) * sqrt(i);
    }
    for (int i = 0; i < 100; i++) {        // 배열 출력
        printf("%f\n", *(a+i));
    }
    double key = 24;    // 찾는 값
    int ans = linear_search(a, 100, sizeof(double), &key, double_compare);
    printf("%d", ans);
    return 0;
}

만약 int형 데이터를 찾으려면 배열 초기화를 바꾸는 것이 좋다. double형에서의 문제점을 찾기 위해 일부러 루트를 씌우고, 제곱을 했기 때문에 int형으로 바꾸기 위해 번거롭게 반올림을 해주었다. double형에서의 문제점을 초점으로 한 코드이기 때문에 double형 코드를 중점으로 보길 바란다.

배열 초기화를 잘 하면 int형이든 double형이든 원하는 값의 인덱스를 잘 찾아낼 것이다.

먼저 chromedriver-autoinstaller, selenium을 다운받고 코드를 실행해야 합니다.

# 파일명 : main.py

import chromedriver_autoinstaller

chromedriver_autoinstaller.install()

from sutils import get_selenium_driver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC

driver = get_selenium_driver(False)
driver.get('웹 사이트 주소 입력')

프로젝트 안에서 새 Python File을 열고 다음 코드를 입력합니다.

# 파일명 : sutils.py

from selenium import webdriver

def get_selenium_driver(headless=True):
    chrome_options = webdriver.ChromeOptions()
    if headless:
        chrome_options.add_argument('--headless')

    chrome_options.add_argument('--no-sandbox')
    chrome_options.add_argument('lang=en')
    chrome_options.add_argument('--disable-dev-shm-usage')
    chrome_options.add_argument("disable-gpu")
    chrome_options.add_argument("disable-infobars")
    chrome_options.add_argument("--disable-extensions")

    driver = webdriver.Chrome(options=chrome_options)
    driver.set_window_size(1920, 1080)
    return driver

만약 위 코드를 사용하고 자동 로그인(아래에 코드 있음)을 시도했을 때 로그인이 막힌다면, 다음 코드를 main.py에 입력합니다. (이 코드를 사용할 때는 sutils.py가 필요없습니다.) 다음 코드를 입력해도 로그인이 막힌다면, 저도 잘 모릅니다 ..

import chromedriver_autoinstaller

chromedriver_autoinstaller.install()

from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC

from selenium.webdriver.chrome.options import Options
import subprocess

def get_original_chrome_driver():
    subprocess.Popen(r'C:\Program Files\Google\Chrome\Application\chrome.exe --remote-debugging-port=9222 --user-data-dir="C:\chrometemp"')  
                       # chrome이 있는 위치를 적어줍니다.

    option = Options()
    option.add_experimental_option("debuggerAddress", "127.0.0.1:9222")

    chrome_ver = chromedriver_autoinstaller.get_chrome_version().split('.')[0]
    try:
        driver = webdriver.Chrome(f'./{chrome_ver}/chromedriver.exe', options=option)
    except:
        chromedriver_autoinstaller.install(True)
        driver = webdriver.Chrome(f'./{chrome_ver}/chromedriver.exe', options=option)
    driver.implicitly_wait(10)
    driver.set_window_size(1920, 1080)
    return driver

driver = get_original_chrome_driver()
driver.get('웹 사이트 주소 입력')

(이제부터 나오는 코드들은 main.py에 입력합니다.)

자동 로그인

먼저 예시를 보여드리겠습니다. 저는 나이키 로그인을 시도해봤습니다.

id = '아이디 입력'
pw = '비밀번호 입력'

try:
    WebDriverWait(driver, 3).until(EC.presence_of_element_located((By.CLASS_NAME, 'login')))
    elem_btn = driver.find_element(By.CLASS_NAME, 'login')
    elem_btn.click() # 버튼 클릭

    WebDriverWait(driver, 3).until(EC.presence_of_element_located((By.ID, 'j_username')))
    elem_id = driver.find_element(By.ID, 'j_username')
    elem_id.send_keys(id) # id 입력

    WebDriverWait(driver, 3).until(EC.presence_of_element_located((By.ID, 'j_password')))
    elem_pw = driver.find_element(By.ID, 'j_password')
    elem_pw.send_keys(pw)

    login_btn = driver.find_element(By.XPATH, '//button[@class="button large width-max"]')
    login_btn.click()
except: # 이미 로그인이 되어있는 경우
    pass 

위 코드를 보면

WebDriverWait(driver, 3).until(EC.presence_of_element_located((By.CLASS_NAME, 'login')))
elem_btn = driver.find_element(By.CLASS_NAME, 'login')
elem_btn.click()

이러한 형태의 코드가 계속 반복됩니다. WebDriverWait(driver, 3) : 창이 뜰 때까지 최대 3초 기다린다는 뜻 By.CLASS_NAME, 'login' , By.XPATH, '//button[@class="button large width-max"]' , ... : 웹 사이트에서 F12를 누른 후 클릭하고 싶은, 또는 입력하고 싶은 곳을 찾아 코드를 작성합니다. 위 코드는 나이키 로그인에 맞는 코드이므로 다른 사이트에 적용하려면 수정해야합니다.

자동 구매

구매도 똑같습니다.

WebDriverWait(driver, 3).until(EC.presence_of_element_located((By.CLASS_NAME, 'login')))
elem_btn = driver.find_element(By.CLASS_NAME, 'login')
elem_btn.click()

이 코드를 수정하여 사용합니다.

마지막에 아래의 코드를 작성한 후, 실행합니다.

import time

time.sleep(600) # 600초 동안 창이 꺼지지 않음

driver.close()

소수를 구하려면 약수를 찾는 방법부터 알아야 한다. 소수의 정의는 1과 자기 자신을 약수로 가지는 수, 즉 약수가 2개인 수이기 때문이다.

def is_divisor(n: int, m: int):
    return n % m == 0

n을 m으로 나누었을 때 나머지가 0이면 m이 n의 약수이고, 0이 아니면 m이 n의 약수가 아니다.

소수 구하기

다양한 방법을 소개할 것인데, 아래로 갈 수록 더 간단하고 빠른 코드이다. 간단하고 빠른 코드로 바꾸는 과정을 설명한다.

첫 번째 방법

def is_prime(num: int):
    count = 0  # 약수의 개수
    for i in range(1, num + 1):  # 1 ~ num 사이의 약수 개수 구하기
        if is_divisor(num, i):
            count = count + 1
    return count == 2  # 약수의 개수 2개 == 소수

이 방법은 구하는 시간이 오래 걸린다. N이 소수인지 알기 위해서 for문을 N번 반복해야 하기 때문이다. (시간복잡도가 N이다.)

구하는 시간을 줄여보자. 첫 번째 방법에서 약수를 찾기 위해 1부터 num까지 하나하나 검사해보았는데, 1부터 $$\sqrt{num}$$ 까지만 검사해도 된다.

(증명 방법 배웠는데 기억이 안나서 찾으면 올림 ..)

예시를 들어 설명하자면, 16의 약수는 1, 2, 4, 8, 16이다. 16 = 1 x 16 = 2 x 8 = 4 x 4 이므로 1, 2, 4만 구해도 $$\sqrt{16}$$ (= 4) 보다 큰 약수인 8, 16은 자동으로 구해진다. 1과 16, 2와 8, 4와 4는 각각 한 세트로 생각한다.

이렇게 하면 약수가 1개인 수가 소수이다. 숫자 자기 자신은 검사하지 않기 때문에 약수가 1만 나온다.

두 번째 방법

def is_prime_up_to_root(num: int):
    if num == 1:  # 1은 소수 아님
        return False
    count = 0
    i = 1
    while i * i <= num:  # 1 ~ 루트 num 사이의 약수 개수 구하기
                         # 실수가 나오지 않도록 양변을 제곱하여 식을 변형함
        if is_divisor(num, i):
            count = count + 1
        i = i + 1
    return count == 1

구하는 시간을 더 줄여보자. 처음부터 2의 배수를 제외하는 것이다. 그렇다면 구하는 시간이 절반으로 줄어든다.

세 번째 방법

def is_prime_up_to_root_out_mult2(num: int):
    if num == 1:
        return False
    if num % 2 == 0:  # 2의 배수 제외
        return num == 2  # 2만 소수
    count = 0
    i = 1
    while i * i <= num:
        if is_divisor(num, i):
            count = count + 1
        i = i + 1
    return count == 1

3의 배수도 생략하면 시간이 더더 줄어든다.

코드를 더 간단하게 정리해보자.

네 번째 방법

def is_prime_up_to_root_out_mult2_2(num: int):
    if num % 2 == 0: 
        return num == 2 
    if num % 3 == 0:
        return num == 3
    i = 5  # 1은 나머지가 무조건 0이기 때문에 제외, 2, 3, 4는 위에서 판별
    while i * i <= num:
        if num % i == 0:  # num이 i를 약수로 가짐
            return False
        i = i + 2  # i가 짝수일 때 num이 i를 약수로 가지면 num은 짝수라서 이미 판별
    return num != 1  # 1은 소수 아님

이 방법은 약수를 찾는 함수가 필요 없다. 또한 1을 제외한 다른 약수가 구해지면 num을 바로 합성수라고 판단하고 return False가 실행되어 구하는 시간이 줄어든다.

이 외에도 코드를 더 간단하고 빠르게 만드는 방법이 존재할 수 있다.

소수 출력

소수 구하는 함수를 실행시키는 방법이다.

number = 1
while True:  # 계속 반복함
    if is_prime(number):
        print(number)
    number = number + 1