우주의 IT 소행성

Flask를 통해 Bootstrap을 받아오려 했는데 css와 js를 인식하지 못하는 에러가 발생하였다.

Flask Docs를 통해 확인해 본 결과, 보안상의 이유로 모든 css와 js 정적 파일은 static 폴더 내에서 관리된다고 한다.

<link href="css/bootstrap.css" rel="stylesheet"> 형식으로 작성된 html 문서를

다음과 같이 바꿔주어야 한다.

이렇게 바꿔주었음에도, 파이참 내에서는 304 에러가, 웹에서 확인했을 때는 file not found 404 에러가 확인 되었는데,

내가 사용하려는 샘플 Bootstrap html 파일에 features.css만 작성되어있떠라도, bootstrap.js, bootstrap.css를 불러와야 정상적으로 작동한다는 점을 인지하여야 한다.

들어가기에 앞서

상호 배타적 집합 (Disjoint Set)

- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조직하는 자료 구조

- 공통 원소가 없는 부분 집합들로 나누어진 원소들에 대한 자료구조

- 서로소 집합 자료구조

유니온 파인드

- 그래프 알고리즘, 합집합 찾기의 의미를 가짐

- 상호 배타적 집합 이라고도 한다.

- 여러 노드가 존재할 때 두 개의 노드를 선택하여 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

- 유니온과 파인드 크게 3가지 연산으로 이루어져 있습니다.

> Make-Set : 초기화, x를 유일한 원소로 하는 새 집합을 생성

> Union 연산 :  x가 어떤 집합에 포함되어 있는지 찾는 연산

> Find 연산 : x와 y가 포함되어 있는 집합을 합치는 연산

유니온 파인드 어디에 사용하는 걸까?

- 전체 집합을 구성 원소들이 겹치지 않도록 분할하는 데 자주 사용

- Krusakl MST 알고리즘 에서 새로 추가할 간선이 사이클을 형성하는지 판단

C언어로 구현한 유니온 파인드

int root[MAX_SIZE];
int rank[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
  root[i] = i;
  rank[i] = 0;
}


int find(int x) {
  if (root[x] == x) {
      return x;
  } else {
      return root[x] = find(root[x]);
  }
}


void union(int x, int y){
   x = find(x);
   y = find(y);

   if(x == y)
     return;

   if(rank[x] < rank[y]) {
     root[x] = y;
   } else {
     root[y] = x;

     if(rank[x] == rank[y])
       rank[x]++;
   }
}

참고 및 소스코드 블로그

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

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

"""
a - > b
1. 곱하기 2
2. 1을 수의 가장 오른쪽에 추가

"""
a, b = map(int, input().split())
count = 1

def go(a, b, count):
    if a == b:
        print(count)
        exit()
    if a > b:
        return
    go(a * 2, b, count + 1)
    go(int(str(a) + "1"), b, count + 1)


go(a, b, count)
print(-1)

재귀 함수를 이용하여 푼 문제

재귀의 조건을 살펴보자

1. A와 B가 같은 값이면 재귀 종료

2. A가 B보다 커지면 재귀 종료

3. 1-2에 해당하지 않는 경우 매 순간 a에 대해 곱하기 2, 1을 추가 해주면 됨

def check(index):
    s = 0
    for i in range(index, -1, -1):
        s += ans[i]
        if sign[i][index] == 0:
            if s != 0:
                return False
        elif sign[i][index] < 0:
            if s >= 0:
                return False
        elif sign[i][index] > 0:
            if s <= 0:
                return False
    return True

def go(index):
    if index == n:
        return True
    if sign[index][index] == 0:
        ans[index] = 0
        return check(index) and go(index + 1)

    for i in range(1, 11):
        ans[index] = i * sign[index][index]
        if check(index) and go(index + 1):
            return True
    return False


n = int(input())
s = input()
sign = [[0] * n for _ in range(n)]
ans = [0] * n
cnt = 0
for i in range(n):
    for j in range(i, n):
        if s[cnt] == '0':
            sign[i][j] = 0
        elif s[cnt] == '+':
            sign[i][j] = 1
        else:
            sign[i][j] = -1
        cnt += 1
go(0)
print(' '.join(map(str, ans)))

"""
-10 ~ 10 까지 N개의 정수로 이루어진 수열 A (N <= 10)
S[i][j] = A[i] ~ A[j] 까지의 합,
S[i][j]가 0보다 크면 +, 작으면 -, 같으면 0을 출력
S가 주어졌을 때, 가능한 A를 찾는 문제

각 자리마다 21가지의 수를 구해 넣어주저야 함
O(21^10)은 너무 큰 수로 BRUTE FORCE로는 해결이 어려움


----시간초과를 해결 할 방법 첫번째----
s[i][i] = A[i]의 부호
s[i][i] > 0 1~ 10
        = 0 0
        < 0 -10 ~ -1
로 경우의 수를 10^10로 줄일 수 있다.
하지만 10^10은 100억으로 시간초과.

----두번째----
i번째의 수를 정하면 S[j][i]의 부호를 모두 검사할 수 있다.
"""