BAEKJOON : 1260, 2529, 1193

No. 1260

1. Problem

2. My Solution

• 주어진 노드부터 탐색을 시작하고 낮은 숫자를 우선으로 탐색
• 낮은 숫자를 우선으로 탐색하기 위해서 해당 노드와 연결된 노드를 나타내는 graph[i] 를 오름차순 정렬

import sys
import copy
from collections import deque
sys.setrecursionlimit(10**8)

def dfs(v, visited):
    visited[v] = True
    print(v, end=" ")

    for u in graph[v]:
        if visited[u] == False:
            dfs(u, visited)


def bfs(v, visited):
    queue = deque()
    queue.append(v)
    visited[v] = True

    while(queue):
        v = queue.popleft()
        print(v, end=" ")

        for u in graph[v]:
            if visited[u] == False:
                queue.append(u)
                visited[u] = True



n,m,start = map(int,sys.stdin.readline().rstrip().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)):
    graph[i].sort()

dfs(start, visited.copy())
print("")
bfs(start, visited.copy())

---

No. 2529

1. Problem

2. My Solution

• 첫 번째 방법
• itertools 모듈의 permutations 순열 함수 사용
• PyPy3 메모리 초과, Python3 시간 초과

from itertools import permutations
import sys
sys.setrecursionlimit(10**4)

k = int(sys.stdin.readline())
sign = sys.stdin.readline().rstrip().split()
seq = list(permutations(range(10),k+1))

for i in seq[::-1]:
    flag = False
    for j in range(k):
       if eval(str(i[j]) + sign[j] + str(i[j+1])) == False:
           flag = True
           break
    
    if flag == False:
        print(*i,sep="")
        break

for i in seq:
    flag = False
    for j in range(k):
        if eval(str(i[j]) + sign[j] + str(i[j+1])) == False:
           flag = True
           break
    
    if flag == False:
        print(*i,sep="")
        break

• 두 번째 방법
• 순열, 백트래킹 알고리즘 이용
• eval(str(res[level-1])+ sign[level-1] + str(i)) 부분으로 인해 시간 소요 ↑

import sys
sys.setrecursionlimit(10**8)

def solution(level):
    if level >= (k+1):
        ans.append(res.copy())
        
    else:
        for i in nums:
            if visited[i] == True:
                continue
            elif level > 0 and eval(str(res[level-1])+ sign[level-1] + str(i)) == False:
                continue
            else:
                res[level] = i
                visited[i] = True
                solution(level+1)
                visited[i] = False


k = int(sys.stdin.readline())
sign = sys.stdin.readline().rstrip().split()
nums = [0,1,2,3,4,5,6,7,8,9]
visited = [False] * 10
res = [0] * (k+1)
ans = []

solution(0)

print(*max(ans),sep="")
print(*min(ans),sep="")

• 세 번째 방법
• 시간이 많이 걸리는 부분을 최대한 low 레벨의 연산을 이용하여 수행

import sys
sys.setrecursionlimit(10**8)

def check(a,b,op):
    if op == ">":
        return a > b
    else:
        return a < b

def solution(level):
    if level >= (k+1):
        ans.append(res.copy())
        
    else:
        for i in nums:
            if visited[i] == True:
                continue
            elif level > 0 and check(res[level-1],i,sign[level-1]) == False:
                continue
            else:
                res[level] = i
                visited[i] = True
                solution(level+1)
                visited[i] = False


k = int(sys.stdin.readline())
sign = sys.stdin.readline().rstrip().split()
nums = [0,1,2,3,4,5,6,7,8,9]
visited = [False] * 10
res = [0] * (k+1)
ans = []

solution(0)

print(*max(ans),sep="")
print(*min(ans),sep="")

3. Learned

• 해결 아이디어를 생각하고 "이건 안될거야" 라고 생각하지말고 일단 구현해보자
• 긴 코드를 짧은 코드로 바꾸는 것은 좋지만 시간이 더 소요되는 코드가 될 수 있으니 조심해야함

---

No. 1193

1. Problem

• 분수 찾기 복습

2. My Solution

• 이전 코드는 level = 1, level_max =1 부터 시작함

import sys

n = int(sys.stdin.readline())

level = 0
level_max = 0

while(n > level_max):      
    level += 1
    level_max += level


if level % 2 == 0: 
    top = level - (level_max - n)
    bottom = level_max - n + 1
else:
    top = level_max - n + 1
    bottom = level - (level_max-n)

print(f"{top}/{bottom}")                         

3. Learned

• top 과 bottom 을 구할 때 어떤 값을 덧셈 뺄셈해서 조합해야할 지 모르겠다면 직접 값을 넣어서 구해보기