땅지원
땅지원's Personal blog
땅지원
전체 방문자
오늘
어제
  • 전체 (353)
    • Frontend (2)
      • React (2)
    • Backend (90)
      • Java (16)
      • Python (19)
      • Spring (23)
      • Database (21)
      • Troubleshooting (8)
    • DevOps (27)
      • ELK (13)
    • CS (40)
    • OS (2)
      • Linux (2)
    • Algorithm (95)
      • concept (18)
      • Algorithm Problem (77)
    • 인공지능 (25)
      • 인공지능 (12)
      • 연구노트 (13)
    • 수업정리 (35)
      • 임베디드 시스템 (10)
      • 데이터통신 (17)
      • Linux (8)
    • 한국정보통신학회 (5)
      • 학술대회 (4)
      • 논문지 (1)
    • 수상기록 (8)
      • 수상기록 (6)
      • 특허 (2)
    • 삼성 청년 SW 아카데미 (6)
    • 42seoul (12)
    • Toy project (3)
    • 땅's 낙서장 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 20.11.6 BB21플러스 온라인 학술대회
  • 20.10.30 한국정보통신학회 온라인 학술대회

인기 글

태그

  • ㅗ
  • 이것이 리눅스다 with Rocky Linux9
  • I
  • E
  • D

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
땅지원

땅지원's Personal blog

Algorithm/Algorithm Problem

백준 9019 DSLR(시간복잡도, BFS)

2022. 5. 6. 18:44

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

 

9019번: DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에

www.acmicpc.net

문제를 이해하기에는 어렵지 않았다. D,S,L,R에 따른 연산을 하고 연산결과가 B랑 같으면 어떤 연산을 했는지 출력한다

 

최소한의 연산을 해야하기 때문에 그리디, BFS적으로 접근을 했고 한 경우가 계속 4가지로 나가는 완전 트리의 형태를 생각해서 그래프 문제라고 생각하고 BFS적으로 접근했다.

 

여기까지의 생각은 어렵지 않았는데 python으로 풀다보니 시간초과에서 많이 애를 먹었다.

 

1. 그래프 탐색하는 중 DP적으로 한번 연산된 결과는 다시 연산 안하기 위해서 visited list를 만들어 관리한다

visited = [False] * 10000
visited[A] = True

while queue:
    num, command = queue.popleft()
    if num == B:
        print(command)
        return
    temp = func_D(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'D'))

    temp = func_S(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'S'))

    temp = func_L(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'L'))

    temp = func_R(num)
    if not visited[temp]:
        visited[temp] = 1
        queue.append((temp,command+'R'))

2. L,R의 연산을 형변환 str(), int()를 사용하게 되면 O(logN)만큼의 시간이 든다는 것을 알았다.

숫자 연산으로 바꾸면 O(1)이 되기 때문에 숫자 연산으로 바꿨다

 

<Before>

def func_L(data):
    data = str(data)
    data = data[1:] + data[0]
    return data

def func_R(data):
    data = str(data)[-1::-1]
    return data

<After>

def func_L(data):
    front = data % 1000
    back = data // 1000
    res = front *10 + back
    return res

def func_R(data):
    front = data % 10
    back = data // 10
    res = front * 1000 + back
    return res
def func_L(data):
    return data % 1000 * 10 + data // 1000

def func_R(data):
    return data % 10 * 1000 + data // 10

code

def func_D(data):
    data = 2 * data
    if data > 9999:
        data %= 10000
    return data

def func_S(data):
    if not data:
        return 9999
    else:
        return data-1

def func_L(data):
    data = str(data)
    data = data[1:] + data[0]
    return data

def func_R(data):
    data = str(data)[-1::-1]
    return data

from collections import deque
def search(A):
    queue = deque()
    queue.append((A,''))
    visited = [False] * 10000
    visited[A] = True

    while queue:
        num, command = queue.popleft()
        if num == B:
            print(command)
            return
        temp = func_D(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'D'))

        temp = func_S(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'S'))

        temp = func_L(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'L'))

        temp = func_R(num)
        if not visited[temp]:
            visited[temp] = 1
            queue.append((temp,command+'R'))

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    A, B = list(map(int,input().split()))
    search(A)

 

 

 

 

 

 

 

'Algorithm > Algorithm Problem' 카테고리의 다른 글

백준 16928 뱀과 사다리 게임(BFS)  (0) 2022.05.10
백준 14500 테트로미노(Brute-Force, DFS)  (0) 2022.05.09
백준 7569 토마토(3차원배열, BFS)  (0) 2022.05.06
백준 5430 AC(Queue)  (0) 2022.05.06
백준 1107 리모콘(Brute-Force)  (0) 2022.05.04
    'Algorithm/Algorithm Problem' 카테고리의 다른 글
    • 백준 16928 뱀과 사다리 게임(BFS)
    • 백준 14500 테트로미노(Brute-Force, DFS)
    • 백준 7569 토마토(3차원배열, BFS)
    • 백준 5430 AC(Queue)
    땅지원
    땅지원
    신입 개발자의 우당탕탕 기술 블로그

    티스토리툴바