this.code();

# a,b=map(int,input().split())
# print('%0.9f'%(a/b))  // 절대,상대오차는 소수점 9번째 자리(0.1e-9)까지 허용

🧐 백준 1990 (소수인 회문)    Gold V 

🤫  solution_1990(시간초과)

import math, sys
input = sys.stdin.readline
a, b = map(int, input().split())

dec = [i for i in range(b+1)]
dec_first = []
for i in range(2, int(b**0.5) + 1):
    if i in dec:
        dec_first.append(i)
    dec = [j for j in dec if j%i != 0]
decimal = dec_first + dec

ans = []
def palindrome(num):
    string_num = str(num)
    num_len = len(string_num)
    if string_num[:num_len // 2] == string_num[math.ceil(num_len / 2):][::-1]:
        if num in decimal:
            ans.append(num)

for i in range(a, b+1):
    palindrome(i)
ans.append(-1)
print(*ans, sep = "\n")

 

🤫  solution_1990

a, b = map(int,input().split())

def decimal(num):
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True


#10,000,000이상인 팰린드롬수는 존재 X
if b > 10000000 :
    b=10000000

palindrome = [i for i in range(a,b+1) if str(i) == str(i)[::-1]]
for i in palindrome:
    if decimal(i):
        print(i)
print(-1)

🧐 백준 15927 (회문은 회문이 아니야!)    Gold V 

🤫  Algorithm 

1) 문자열 전체가 회문이 아니면 답은 문자열의 길이이다.
2) 문자열 전체가 회문일 때,
 i) 문자열 전체가 모두 같은 문자일 때 팰린드롬이 아닌 부분 문자열이 존재하지 않기에 답은 -1이다.
 ii) 처음 또는 끝의 문자 하나만 제외한 문자열은 팰린드롬이 아니기에 답은 (원래 문자열의 길이 - 1)이다.

🤫  solution_15927

string = input()

ans = 0
if string == string[::-1]:
    if string[:len(string) // 2 + 1] == string[:len(string) // 2 + 1][::-1]:
        ans = -1
    else:
        ans = len(string) - 1
else:
    ans = len(string)

print(ans)

🧐 백준 11664 (CCW, 외적)    Gold V 

🤫  Algorithm 

# 점 a를 선분의 왼쪽에 있는 점, 점 b를 선분의 오른쪽에 있는 점이라 하자.
# 점 a와 점 b의 중간점 m을 구한다.

# l = 점 a와 점 c의 거리
# r = 점 b와 점 c의 거리
# h = 점 m과 점 c의 거리

# 만약 h가 현재 존재하는 최소값 ans보다 작다면, ans를 h로 갱신해줍니다.
# 만약 l이 r보다 크다면, c가 a보다 b에 더 가깝게 있다는 뜻이므로 점 a를 점 m으로 바꿔준다.
# (이분탐색을 진행해야 하므로 더 가까운 쪽으로 범위를 좁혀줘야 하기 때문.)
# 반대로 r이 l보다 크다면 c가 b보다 a에 더 가깝게 있다는 뜻이므로 점 b를 점 m으로 바꿔준다.

🤫  solution_11664

ax,ay,az,bx,by,bz,cx,cy,cz = map(int,input().split())

ans = float('inf')

while True:
    mx,my,mz = (ax+bx)/2,(ay+by)/2,(az+bz)/2
    l = ((ax-cx)**2+(ay-cy)**2+(az-cz)**2)**0.5
    h = ((mx-cx)**2+(my-cy)**2+(mz-cz)**2)**0.5
    r = ((bx-cx)**2+(by-cy)**2+(bz-cz)**2)**0.5

    if abs(ans-h) <= 1e-6:
        print('%0.10f'%ans)
        exit()
    if h < ans:
        ans = h
    if l > r:
        ax,ay,az = mx,my,mz
    else:
        bx,by,bz = mx,my,mz

🧐 백준 11758 (CCW, 외적)    Gold V 

🤫  solution_11758

x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())

CCW = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)

if CCW < 0:
    print(-1)
if CCW > 0:
    print(1)
if CCW == 0:
    print(0)

🧐 백준 2166 (CCW, 외적)    Gold V 

🤫  solution_2166

num = int(input())
x , y = [] , []
for i in range(num):
    X, Y = map(int,input().split())
    x.append(X)
    y.append(Y)

x.append(x[0])
y.append(y[0])

S = 0

for i in range(num):
    S += (x[i]*y[i+1] - x[i+1]*y[i])

print(round(abs(S)/2, 1))

🧐 백준 17386, 17387 (CCW, 외적)   Gold III, Gold II 

🤫  Algorithm 

🤫  solution_17387

import sys
input = sys.stdin.readline

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())

point = []
point.append([x1, y1])
point.append([x2, y2])
point.append([x3, y3])
point.append([x4, y4])
A, B, C, D = point[0], point[1], point[2], point[3]


def ccw(p1, p2, p3):
    X1, X2, X3 = p1[0], p2[0], p3[0]
    Y1, Y2, Y3 = p1[1], p2[1], p3[1]
    CCW = (X1*Y2 + X2*Y3 + X3*Y1) - (X2*Y1 + X3*Y2 + X1*Y3)
    if CCW > 0:
        return 1
    elif CCW < 0:
        return -1
    else:
        return 0


def checkCross(a, b, c, d):
    result = 0
    p123, p124 = ccw(a, b, c), ccw(a, b, d)
    p341, p342 = ccw(c, d, a), ccw(c, d, b)

    if (p123 * p124 <= 0 and p341 * p342 <= 0) or (p123 * p124 == 0 and p341 * p342 == 0):
        if min(a[0], b[0]) <= max(c[0], d[0]) and \
                min(c[0], d[0]) <= max(a[0], b[0]) and \
                min(a[1], b[1]) <= max(c[1], d[1]) and \
                min(c[1], d[1]) <= max(a[1], b[1]):
            result = 1
    return result

print(checkCross(A, B, C, D))

BFS(G, start_v)
    let Q be a queue
    mark start_v as visited
    Q.enqueue(start_v)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not marked as visited then
                label w as visited
                w.parent := v
                Q.euqueue(w)

def bfs(start_v):
    visited = [start_v]
    Q = deque([start_v])
    while Q:
        v = Q.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                Q.append(w)

    return visited

🧐 백준 1260 (DFS와  BFS)

🤔 Algorithm 과정_ DFS 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. 재귀를 이용한 DFS를 수행하는데, 아래와 같이 진행한다.

🤔 Algorithm 과정_ BFS 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다. (이때, 위의 DFS에서 사용했기에 초기화를 반드시 해줘야 한다!)
3. BFS를 수행하는데, 아래와 같이 진행한다.

이를 풀이하면 다음과 같다.

1. 큐 자료구조에 starting_vertex 삽입
visit_list에 현재 vertex 기록

2. while (큐가 빌 때 까지):
	큐에서 vertex를 가져와 출력
    현재 vertex의 연결vertex 중 미방문 vertex를 큐에 삽입(append)
    방문리스트에 기록

🤫  solution_1260

import sys
input = sys.stdin.readline

V, E, starting_vertex = map(int, input().split())

# graph라는 인접리스트 생성
#         [1]      [2]     [3]       [4]
# [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3], []]
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 정점에 우선순위가 부여되었으므로 정렬
for i in range(V+1):
    graph[i].sort()

# 방문리스트 생성
visit_list = [False] * (V+1)

def DFS(v):
    print(v, end = " ")
    visit_list[v] = True
    for i in graph[v]:
        if not visit_list[i]:
            DFS(i)

from collections import deque
def BFS(v):
    queue = deque()
    queue.append(v)
    visit_list[v] = True
    while queue:
        curr_vertex = queue.popleft()
        print(curr_vertex, end = " ")
        for i in graph[curr_vertex]:
            if not visit_list[i]:
                visit_list[i] = True
                queue.append(i)


# DFS 출력
DFS(starting_vertex)
print()

visit_list = [False] * (V+1)    # 리스트 초기화
# BFS 출력
BFS(starting_vertex)

🧐 깊이 우선 탐색, DFS (Depth First Search)

https://chan4im.tistory.com/121

🧐 백준 2023 (DFS)   Gold V 

🤔 Algorithm 과정 
1. 한자리소수 -> 이 한자리 소수에서 파생되어 나온 두자리소수 -> ... 의 반복이므로
2. 한자리 소수는 [2, 3, 5, 7]이다.
3. 여기서 파생되는 소수는 다음과 같다.
[2] - 23, 29
[3] - 31, 37
[5] - 53, 59
[7] - 71, 73, 79
위 과정을 계속 반복하여 입력된 자리수에 맞는 출력을 진행해주면 된다.
이는 재귀를 이용한 DFS를 통해 해결할 수 있으며 아래 그림을 통해 간단히 도식화 하였다.

🤫  solution_2023 (시간초과)

import sys, math
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input())

dec = [i for i in range(2, 8*10**(N))]
dec_front = []
for i in range(2, int(math.sqrt(10**(N+1))) + 1):
    if i in dec:
        dec_front.append(i)
    dec = [j for j in dec if j % i != 0]
decimal = dec_front + dec

single_decimal = [2, 3, 5, 7]

def DFS(num):
    if len(str(num)) == N:
        print(num)
    else:
        for i in range(1, 10, 2):
            if num*10 + i in decimal:
                DFS(num*10 + i)

for i in single_decimal:
    DFS(i)

🤫  solution_2023

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input())
single_decimal = [2, 3, 5, 7]

def decimal(num):
    for i in range(2, num//2 + 1):
        if num % i == 0:
            return False
    return True

def DFS(num):
    if len(str(num)) == N:
        print(num)
    else:
        for i in range(1, 10, 2):
            if decimal(num*10 + i):
                DFS(num*10 + i)

for i in single_decimal:
    DFS(i)

cf. // 는 정수형 나눗셈이다. 

🧐 백준 13023 (DFS)   Gold V 

🤔 Algorithm 과정 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. DFS를 수행하는데, 아래와 같이 진행한다.
4. 최종적으로 DFS의 재귀 횟수가 5회 이상이면 되므로 5회가 된 순간이 바로 임계점이다.
5. 따라서 재귀횟수가 5회면 바로 1을 출력하고 5회 미만이라면 0을 출력한다.

🤫  solution_13023

# 백준 11724
# 친구 관계 5개를 찾는 문제 = 재귀 깊이가 5번 이상이면 된다.
import sys
input = sys.stdin.readline

V, m = map(int, input().split())
vertex = [[] for _ in range(V+1)]

# 방문 리스트 생성
visit_list = [False] * (V+1)

for _ in range(m):
    u, v = map(int, input().split())
    vertex[u].append(v)
    vertex[v].append(u)
# print(vertex) => [[1], [0, 2], [1, 3], [2, 4], [3], []]
# 인접 리스트 생성       [0]   [1]     [2]     [3]    [4]

threshold = False
def DFS(curr_vertex, depth):
    global threshold
    if depth == 5:
        threshold = True
        return
    visit_list[curr_vertex] = True
    for i in vertex[curr_vertex]:
        if not visit_list[i]:
            DFS(i, depth+1)
    visit_list[curr_vertex] = False

for i in range(V):
    DFS(i, 1)
    if threshold:
        break

if threshold:
    print(1)
else:
    print(0)

🧐 백준 11724 (Connected Component)

- connected component 즉, 연결요소는 다음과 같은 조건에서 성립한다.

• 연결요소에 속한 모든 정점(vertex)을 연결하는 간선(edge)가 있어야 한다.
• 또 다른 연결요소에 속한 정점(vertex)과 연결하는 간선(edge)이 있으면 안된다.

🤔 Algorithm 과정 
0.  노드의 최대 개수가 1000이므로 시간복잡도 n^2이하의 알고리즘을 모두 사용할 수 있다.
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. DFS를 수행하는데, 아래와 같이 진행한다.

🤫  solution_11724

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

V, E = map(int, input().split())
CC = [[] for _ in range(V+1)]  # [[], [], [], [], [], [], []]
visit_list = [False] * (V+1)

for _ in range(E):
    u, v = map(int, input().split())
    # 양방향 간선이므로 양쪽에 정점 더하기.
    CC[u].append(v)
    CC[v].append(u)
# print(CC) => [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]
# 인접리스트 생성         [1]     [2]   [3]    [4]     [5]   [6]


def DFS(v):
    visit_list[v] = True
    for i in CC[v]:
        if not visit_list[i]: # 연결요소가 방문리스트에 F로 되어있으면 True로 고치기 위한 재귀
            DFS(i)

cnt = 0
for i in range(1, V+1):
    if not visit_list[i]:  # 1 2 3 4 5 6의 방문리스트에 대해 방문한적이 없다면
        cnt += 1
        DFS(i)

print(cnt)

procedure backtracking(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtracking(s)
        s ← next(P, s)

reject(P,c): 만약 다음의 노드가 후보가 아닌다면 return으로 종료.
accept(P,c): 만약 현재 노드까지가 답과 일치한다면 답을 출력.
first(P,c): 후보 C의 첫번째 확장을 시작한다.
답이 없을때까지 다음 함수를 계속 반복.

🧐 딕셔너리 (Dictionary). { key : value }

🤔 딕셔너리 개념

key-value를 하나의 쌍으로 갖는 자료구조로 다른 언어에의 map과 같은 기능을 한다.

이때, 딕셔너리는 키가 중복되는것을 허용하지 않는다!

이때, 딕셔너리는 키가 중복되는것을 허용하지 않는다!

🤔 딕셔너리의 생성과 삭제

dict_a['name'] = 'b'
dict_b[3] = 2

del dict_a['name']  # del a[key]

🤔 딕셔너리 key, value에 대한 접근-1

dict_a.keys() 	# key 객체들을 return
dict_a.values() # value 객체들을 return 
dict_a.items()	# key-value 쌍을 return

🤔 딕셔너리 key, value에 대한 접근-2. (key로 value얻기, value로 key얻기)

dict_a.get(key)  # key에 해당하는 "value값 출력"

for i in dict_a  			# 기본적으로 for문에서 i를 통해 key값을 사용할 수 있음
for i in dict_a.values()    # 기본적으로 for문에서 i를 통해 value값을 사용할 수 있음

for key, value in dict_a.items():  # key와 value를 한번에 사용
for key, value in dict_a: 		   # 위와 동일한 사용법

😶 활용 

for i in construct.keys():
    if construct[i] == n:  # key의 어떤 값이 n과 같다면
        ans.append(i)      # {construct[i] : i} key에 해당하는 value, i를 추가

🧐 백준 2798  (딕셔너리 활용)

🤫 해결의 실마리 1. brute force (완전탐색)

처음부터 끝까지 모두 탐색하는 방법의 brute force를 사용한다,.

🤫 해결의 실마리 2.  딕셔너리와 set 

cf. 딕셔너리 객체의 get()함수

dict.get(key, default = None) 
# 매개변수로 넘긴 값 (괄호 안의 값)이 키에 속하지 않으면? None 출력

get함수의 return값은 첫번째 인자의 키값이다.

🤔 Algorithm 과정 
1. 입력받은 숫자 리스트들에서 3개의 숫자를 골라 더한 값을 set에 집어넣는다.
2. 이 sum_set에 대해 입력된 M을 넘지 않는 것들에 대해 딕셔너리 형태로 세 숫자의 합과 m과의 차이를 저장한다.
3. 이때, 저장한 m과의 차이가 가장 작은 것이 m과 가장 가까운 것이므로 답임을 알 수 있다.
 

🤫  solution_2798

n, m = map(int, input().split())
num = list(map(int, input().split()))

sum_set = set()
sum_dict = {}

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            sum_set.add(num[i] + num[j] + num[k])

for i in sum_set:
    if m - i >= 0:
        sum_dict[i] = m - i
    else:
        pass

print(min(sum_dict, key = sum_dict.get))

🧐 백준 2231  (딕셔너리 활용)

🤫 해결의 실마리 1. 자연수의 자릿수에 해당하는 숫자 구하기.

# 각 자릿수의 숫자의 합을 출력하는 함수
def digit(n):
    if n < 10:
        return n
    else:
        return digit(n // 10) + digit(n % 10)

🤫 해결의 실마리 2.  딕셔너리의 사용 

construct = {}
for i in range(n+1):
    construct[i] = i + digit(i)

ans = []

for i in construct:
    if construct[i] == n:
        ans.append(i)

🤔 Algorithm 과정 

216 => 198 + 1 + 9 + 8  ... 이런 방식은 거의 불가 (역추적 진행 시 생성자가 여러개임을 도출할 수 없음)

맵핑을 통해 1~N까지 똑같은 value들 중 최소 key를 찾는 방식으로 문제를 해결해 나갈 것이다.

{1:1}
{2:2}
...
{13:17}
{14:19}
{15:21}
...
{198:216}
...
{N:N'}

 

🤫  solution_2231

n = int(input())

# 각 자릿수의 숫자의 합을 출력하는 함수
def digit(n):
    if n < 10:
        return n
    else:
        return digit(n // 10) + digit(n % 10)

construct = {}
for i in range(n+1):
    construct[i] = i + digit(i)

ans = []

for i in construct:
    if construct[i] == n:
        ans.append(i)
print(0) if len(ans) == 0 else print(min(ans))

🧐 완전 탐색 (Exhaustive Search)

🤫 완전 탐색이란?

이름에서도 알 수 있듯 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.
모든 경우를 탐색하니 당.연.히 정답을 찾을 수 있다.

장점: 모든 경우를 고려해서 정답을 확실히 찾을 수 있으며 복잡하지 않고 빠르게 구현이 가능
단점: 당연하게도 모든 경우를 다 찾기에 효율적이지 않고 실행시간이 오래걸린다.

🤫  완전탐색의 종류 

🤔브루트포스(https://www.acmicpc.net/step/22)
- 조건문/반복문을 이용해 모든 경우의 수를 찾는 방법
- https://chan4im.tistory.com/119

 

브루트 포스 단계

체스판을 만드는 모든 경우를 시도하여 최적의 방법을 찾는 문제

www.acmicpc.net

 

🤔백트래킹(https://www.acmicpc.net/step/34)
- 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 방법

 

백트래킹 단계

조금 더 복잡한 백트래킹 문제 1

www.acmicpc.net

 

🤔BFS,DFS(https://www.acmicpc.net/workbook/view/1833)

- BFS(너비 우선 탐색): 정점과 같은 레벨에 있는 형제노드를 탐색

- DFS(깊이 우선 탐색): 정점의 자식노드들을 탐색

아래 문제집에서는 완전탐색의 유명한 예시인 순열도 포함되어 있다.
순열과 조합 : (https://buyandpray.tistory.com/52)

 

문제집: DFS, BFS 추천문제 (c3171700)

 

www.acmicpc.net

 

🤔비트마스크(https://www.acmicpc.net/workbook/view/804)
- 2진수인 컴퓨터의 연산을 이용하는 방법

 

문제집: 비트마스크 (cokcjswo)

 

www.acmicpc.net

🧐 백준 14425

🤔 Algorithm 과정 
1. s와 string 리스트에 입력에 해당하는 각각의 문자열을 넣음
2. for문으로 string을 돌면서 string에 있는 문자열과 일치하는 단어가 s에 있다면?
3. cnt값 1 증가 (= 일치하는 문자열이 있다는 것)
4. 최종적으로 cnt값 출력

🤫  solution_14425

N, M = map(int, input().split())
s = [input() for _ in range(N)]
string = [input() for _ in range(M)]

cnt = 0
for i in string:
    if i in s:
        cnt += 1
print(cnt)

🧐 백준 10815, 10816(이진탐색)

🤔 Algorithm 과정 
1. 중복되어 입력되어도 비교만 하면 되기에 n이라는 set과 m이라는 리스트를 생성
2. 이후 m안의 원소를 돌면서 만약 m의 원소가 n에 있다면 1을 출력, 아니면 0을 출력해주면 된다.
3. 물론 위의 경우 m 리스트의 원소에 순서대로 접근하기 때문에 순서를 상관쓰지 않아도 된다.

🤫  solution_10815

# cf. n을 list로 했더니 시간초과가 났음.
# 즉, 중복된 결과가 들어가게 되어 set보다 시간복잡도가 더 걸리게 되는 것.
N, n = input(), set(map(int, input().split()))
M, m = input(), list(map(int, input().split()))
m_set = list(set(m))

for i in m:
    print(1, end = " ") if i in n else print(0, end = " ")



# 리스트를 실제로 분할해서 새로 저장하는 것은 O(N)으로 매우 무거운 연산

 

🤫 해결의 실마리(10816): 이진탐색

🤔 count 함수를 무턱대고 쓰면 안된다??
count함수는 시간복잡도가 O(n)시간이 걸려서 for문과 같이 쓰면 시간초과가 발생할 확률이 높다.

🤔 Algorithm 과정 
1. cnt = {}로 딕셔너리를 생성한다.
2. cnt라는 비어있는 딕셔너리에 i 즉, n의 원소가 없다면 cnt[i] = 1로 원소와 개수를 맵핑
3. 만약 i in cnt라면 원소의 개수를 증가시켜줘야 하므로 cnt[i] += 1을 통해 value(원소의 개수)를 증가
4. 이후 m 안의 어떤 원소 i에 대해 cnt에 i가 있으면 value를 출력, 없으면 0을 출력한다.

🤫  solution_10816(시간초과  ∵ count함수의 사용)

N, n = int(input()), list(map(int, input().split()))
M, m = int(input()), list(map(int, input().split()))

for i in m:
    print(n.count(i), end = " ") if i in n else print(0, end = " ")

🤫  solution_10816

N, n = int(input()), list(map(int, input().split()))
M, m = int(input()), list(map(int, input().split()))

cnt = {}
for i in n:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

# 딕셔너리 생성
# print(cnt)  => {6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}

for i in m:
    if i in cnt:
        print(cnt[i], end = " ")
    else:
        print(0, end = " ")

🧐 백준 11478

🤔사실 문제에서 말하는 바는 등수를 출력하는 것과 동일!

🤔 Algorithm 과정 
1. s에 바로 문자열을 입력받는다.
이때, s에 "abcde"라는 문자열이 들어왔을때, s[1:3]으로 bc에 접근할 수 있다.]

2.  set_s = set()를 통한 set을 생성해주고
3. 이중 for문에서 위의 인덱스 슬라이싱원리를 이용해 부분문자열을 구한다.
4. 이때, set_s에 넣어주는데, 중복된 문자열은 추가되지 않는다.

🤫  solution_11478

s = input()
# print(s[1:3])  ba출력

set_s = set()

# 이중 for문을 돌면서 부분 문자열을 구하고 set_s에추가한다.
# 이때, set_s는 집합이기 때문에 중복된 문자열을 추가되지 않는다.
for i in range(len(s)):
    for j in range(i, len(s)):
        set_s.add(s[i:j+1])

print(len(set_s))