this.code();

🧐 백준 11659 (구간 합 구하기)    Silver III 

🤫  solution_11659

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

prefix_sum = [0]
p_sum = 0
for i in num:
    p_sum += i
    prefix_sum.append(p_sum)


for _ in range(m):
    i, j = map(int, input().split())
    print(prefix_sum[j] - prefix_sum[i-1])

🧐 백준 11660(구간 합 구하기 _ 이차원 배열)    Silver I 

🤫  Algorithm 

 

🤫  solution_11660

n, m = map(int, input().split())
num = [list(map(int, input().split())) for i in range(n)]

S = [[0 for i in range(n + 1)] for i in range(n + 1)]

for i in range(n):
    for j in range(n):
        S[i + 1][j + 1] = (S[i][j + 1] + S[i + 1][j] - S[i][j]) + num[i][j]

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(S[x2][y2] - (S[x2][y1-1] + S[x1-1][y2]) + S[x1-1][y1-1])

🧐 백준 10986(구간 합 구하기)    Gold III 

부분 합 개념을 이용해서 풀 때, 부분 합을 계산한 배열을 i, j로 순차적으로 접근할 경우 
O(n^2)으로 시간 초과가 발생하므로 다른 풀이 방법이 필요하다.

🤫  Algorithm 

미리 구해둔 prefix sum에서의 부분합은 S[j] - S[i - 1]의 과정이다.

이때, S[j]와 S[i-1]이 각각 m으로 나눴을 때의 나머지가 동일하다면?
S[j] - S[i - 1] 연산 후 나머지는 0이 되기에 m으로 나눠 떨어진다.

결국 m으로 나눠떨어지는 부분합을 구하는 것은 
나머지가 동일한 idx 중 임의로 nC2를 선택하는 것과 같으므로 다음 알고리즘을 거친다.

[1] [2] [3] [1] [2] -> [0] [1] [3] [6] [7] [9] -> [0] [1] [0] [0] [1] [0] 
-> [0 : 4, 1 : 2] -> 6 + 1 -> 7

 

🤫  solution_10986

import sys
input = sys.stdin.readline

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

rest_list = [0 for _ in range(m)]
rest_list[0] = 1

prefix_sum = 0
for i in range(n):
    prefix_sum += num_list[i]
    rest = prefix_sum % m
    # 나머지 값에 따라서 idx 정보 저장
    rest_list[rest] += 1

cnt = 0
for i in rest_list:
    cnt += i*(i - 1) // 2

print(cnt)

🧐 백준 17609 (회문)    Gold V 

🤫  solution_17609(시간초과)

string_list = [input() for _ in range(int(input()))]

def palindrome(string):
    # 회문인 경우
    if string == string[::-1]:
        print(0)
    # 회문이 아닌경우
    else:
        ans = 2
        for i in range(len(string)):
            new_string = string[:i] + string[i+1:]
            if new_string == new_string[::-1]:
                ans = 1
        print(ans)

for i in string_list:
    palindrome(i)

 

🤫  solution_17609

# 유사 회문 판단 함수
def palindrome_like(string, left, right):
    while left < right:
        if string[left] == string[right]:
            left += 1
            right -= 1
        else:
            return False
    return True
# 회문 함수
def palindrome(string, left, right):
    while left < right:
        if string[left] == string[right]:
            left += 1
            right -= 1
        else:
            pseudo1 = palindrome_like(string, left+1, right)
            pseudo2 = palindrome_like(string, left, right-1)

            if pseudo1 or pseudo2:
                return 1
            else:
                return 2
    return 0

for string in list([input() for _ in range(int(input()))]):
    print(palindrome(string, 0, len(string) - 1))

🧐 백준 1253 (Good Number)    Gold IV 

  

🤫  Algorithm 

# 해당 원소를 제외한 리스트에서 투 포인터(Two-Pointer)를 통해 
# 두 원소의 합이 선택한 원소와 같은지 비교하는 방식으로 해결할 수 있다.

1. num 리스트를 정렬한다.

2. 0부터 N - 1 까지 반복문을 통해 특정 원소(num[i])를 선택하고, 해당 원소를 제외한 except_num 리스트를 생성

3. except_num 리스트에서 투 포인터를 통해 두 원소의 합(sum)이 num[i] 인지 비교한다.
  t < num[i]이면 left를 증가
  t > num[i]이면 right를 감소

4. 2, 3 과정을 반복한다.

🤫  solution_1253

N = int(input())
num = list(map(int, input().split()))
num.sort()
cnt = 0

for i in range(N):
    except_num = num[:i] + num[i + 1:]
    left, right = 0, len(except_num) - 1
    while left < right:
        sum = except_num[left] + except_num[right]
        if sum == num[i]:
            cnt += 1
            break
        if sum < num[i]:
            left += 1  # t 를 증가시켜야 하므로 left 증가
        else:
            right -= 1  # t 를 감소시켜야 하므로 right 감소
print(cnt)

🧐 백준 11003 (최솟값 찾기,  슬라이딩 윈도우 이용)    Platinum V 

  

🤫  Algorithm 

특정 새로운 원소가 추가될 때 이 원소보다 큰 값은 유지될 필요가 없다.
(인덱스로 볼 때에도 새로 추가되는 원소가 가장 오래 남기 때문.)

덱으로 구성하고 덱의 앞에 항상 최소값이 오도록하기 위해
삽입은 append를 이용해 값과 인덱스로 진행한다.

1. 삽입하기전에 덱을 뒤에서 while로 삽입하려는 요소보다 큰값을 모두 제거.
(삽입한다면 덱은 항상 오름차순으로 정렬된 상태를 자동적으로 유지할 것이다.)
(이는 정렬로 인한 시간복잡도를 없애줘 시간초과가 발생하지 않게 할 수 있다.)

2. 추가적으로 슬라이딩 범위를 벗어난 요소들을 생각하면 아래와 같다.
삽입하기전에 덱을 앞에서부터 보며 인덱스 범위가 벗어난 요소들을 빼준다.

i) 뒤에서부터 확인하며 삽입하려는 요소보다 큰 값들을 제거
ii) 앞에서부터 보며 슬라이딩 범위를 벗어난 요소들을 제거
iii) 현재 요소 삽입
모든 연산이 O(1)으로 전체 배열을 확인하는데 O(n)으로 해결가능하다.

🤫  solution_11003

from collections import deque

N, L = map(int, input().split())
A = list(map(int, input().split()))
dq = deque()


for i in range(N):
    first, end = i - L, i
    # 현재 들어온 값보다 큰 값들을 제거하여 시간복잡도를 줄임
    while dq and dq[-1][0] > A[end]:  # 덱의 마지막 위치에서 현재값보다 큰 값 제거
        dq.pop()
    dq.append((A[end], end))  # A, A_idx, 마지막 위치에 현재값 저장
    if dq[0][1] <= first:
        dq.popleft()
    print(dq[0][0], end = " ")

# 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