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]까지의 영역을 탐색한다고 보시면 됩니다.
감사합니다.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
50
2
2주차 개념#12 트리 순회
0
24
2
백준사이트가 종료된다고 합니다.
0
273
2
백준 서비스 종료
9
866
1
sk 하이닉스 코테 대비
0
367
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
102
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
169
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
51
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
68
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
91
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2