3-e 질문드립니다
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요! 시간복잡도 관련한 질문입니다.
모든 경우를 생각했을 때 (60,60,60) 에서 계속 (9,3,1)을 빼는게 최악이라 생각했고 이 경우까지 도달하기 위해선
1+6+6^2+..6^60 이라 생각해서 그래프로 풀 생각을 하지 못했습니다.
그런데 강의에선 bfs로 최단거리를 구했더군요. 최악의 경우에 도달하기 전에 0,0,0이 되는 순간이 존재하니 가능한 풀이인가요? 아니면 제가 최단거리 개념에 대해 잘못 알고 있는걸까요? 감사합니다.
답변 1
0
안녕하세요 ㅎㅎ
모든 경우를 생각했을 때 (60,60,60) 에서 계속 (9,3,1)을 빼는게 최악이라 생각했고 이 경우까지 도달하기 위해선
1+6+6^2+..6^60 이라 생각해서 그래프로 풀 생각을 하지 못했습니다.
->
처음에 시간복잡도 판단은 좋았는데요. ㅎㅎ
BFS로 풀게 되면 반복되는 경우의 수를 visited로 걸러내고 해당 부분부터 시작되는 경우의 수가 감소하기 때문에 풀 수 있다고 생각하시면 됩니다.
예를 들어 어쩌다 보니 30, 30, 30 까지 오는 경우의 수가 10개가 존재한다라고 하면 그 다음부터 최대는 10* 6 ... 이런식으로 가게 됩니다. (만약 방문처리를 안하면요.)
하지만 bfs - visited로 방문처리를 하기 때문에 해당 경우의 수는 1개만 존재하게 되어 계산해야 하는 경우의 수가 줄어들게 됩니다.
어차피 우리가 원하는 것은 최솟값인데 예를 들어 해당 경우의 수를 12, 15, 9번만에 방문했을 때 필요한 것은 9번부터 시작되는 경우의 수임이 자명합니다.
만약 각각 9, 9, 9번만에 방문하더라도 방문처리가 되어있으면 이 중 단 한번만 체크하면 되기 때문에 그 이후로부터 경우의 수가 기하급수적으로 증가하지 않게 되는 효과가 있는 것이죠.
이러한 부분들을 생각해서 bfs로 접근하면 되지 않을까? 하고 들어가시면 됩니다.
감사합니다.
1
안녕하세요 ㅎㅎ
O(N^3)이라고 할 수 있습니다.
방문된 정점은 방문하지 않기 때문에 최대 visited[0][0][0] ~ visited[n][n][n]까지의 영역을 탐색한다고 보시면 됩니다.
감사합니다.
문제를 고민하는 시간 관련
0
13
2
코딩살구클럽
0
26
2
코딩살구클럽 문의
0
30
2
코딩살구클럽 승인
0
31
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
32
2
3-F 채점 관련 질문
0
29
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
32
2
코딩살구클럽 승인
0
43
2
코딩살구클럽승인
0
39
3
코딩살구클럽 승인
0
51
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
45
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
56
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
63
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
64
2
코딩살구클럽 로그인문제
0
78
3
코딩 살구 클럽 로그인 문제
0
85
2
2-J 채점관련 질문
0
67
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1
1-O 코딩살구클럽 채점관련 질문
0
61
2