홍석진 / 7월 4주차 / 3문제

[seokbangguri]

ladder1 및 미로1

ladder1(swea 1225)

• 알고리즘 이론이 부족해 목표지점에서 백트래킹
• 코드를 보면 올라가는 함수, 왼쪽으로 가는 함수, 오른쪽으로 가는 함수 다 작성

미로1(swea 1226)

• 실습시간 두문제정도 dxy 방법으로 작성해보니 코드가 많이 익숙해졌는지 자연스럽게 품

한마디

• 완전탐색으로 길찾기 문제는 이제 날 막지 못한다.

+++추가

제가 미로 문제를 DFS로 풀었는데 07/26 BFS를 배우니 BFS로 푸는게 맞는 것 같습니다..ㅜㅜ

[RomanticBear]

저도 DFS로 접근해서 풀었습니다.

해당 문제는 통로를 통해 특정 인덱스에 도달하는지 판단만 하면 되는 간단한 문제라 DFS도 괜찮다고 생각했어요 (●'◡'●)

[seokbangguri]

BFS로 구현한 부분 추가했습니다.

[ramge132]

이번주도 수고 많으셨습니다~

암호생성기(커밋에는 쇠막대기 자르기 코드라고 되어있음)에서 deque를 사용하면 시간 복잡도를 아~~~~주 약간 줄일 수 있음

원래 코드 복잡도:

1. 값 감소 반복문 : O(N)
2. 리스트 회전 : O(N)
3. 최종 회전 : O(N)

deque 버전 복잡도:

1. 값 감소 반복문 : O(N)
2. deque 회전 : O(N)

3N 과 2N은 BigO에서 둘다 N이지만 deque가 아주 약간 더 빠름

deque버전:

from collections import deque

def password(numbers: list):
    q = deque(numbers)
    while True:
        for i in range(1, 6):
            num = q.popleft() - i
            if num <= 0:
                q.append(0)
                return list(q)
            q.append(num)

T = 10
for test_case in range(1, T + 1):
    t = int(input())
    input_list = list(map(int, input().split()))
    result = password(input_list)
    print(f'#{t} {" ".join(map(str, result))}')