7번 비밀 번호 문제에 시간복잡도가 궁금합니다!
162
1 asked
안녕하세요! 선생님 덕분에 매일 알고리즘 푸는 법을 재밌게 배우고 있습니다 🙂
문제의 제한 사항에 "password의 길이는 200,000을 넘지 않습니다." 라서 효율성을 생각하고 풀어야 된다고 하셨는데, 인접한 숫자를 찾는 과정에서 삼중 for문을 사용하는 것이 괜찮은지 궁금합니다!
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
치킨님, 알고리즘 문제 해결에 대한 궤적을 듣고 정말 기쁩니다. 😊
문제에서 password의 길이가 최대 200,000이라고 명시되어 있다면, 실제 대회나 면접 등에서는 시간 제한을 고려해야 할 경우가 많습니다. 이런 상황에서 삼중 for문은 O(n^3)의 시간복잡도를 가지기 때문에 문제를 효율적으로 풀기에는 적합하지 않을 수 있습니다.
보통 이러한 큰 입력 범위에 대해 O(nlogn) 이하의 시간복잡도를 갖는 알고리즘을 생각해야 제한 시간 내에 문제를 해결할 수 있습니다. 인접한 숫자를 찾는 과정에서 이진 탐색, 투 포인터, 해시 테이블, 또는 세그먼트 트리 같은 다양한 데이터 구조를 활용하여 시간복잡도를 줄일 수 있는 접근법을 고려해보시는 것이 좋을 것 같습니다.
계속해서 효율적인 알고리즘을 학습하며 실력을 키우시면 더 높은 단계의 문제 해결능력을 갖출 수 있을 겁니다. 화이팅입니다! 🌟
비밀번호
0
65
1
과일 가져가기 이러한 경우에는 반례가 생기지 않나요?
0
161
2
cpu 스케줄링
0
105
2
외부 문제 질문
0
122
2
가장 많이 사용된 회의실
0
117
2
심사위원 문제 시간복잡도 질문
0
127
1
현관문 출입순서
0
96
1
미로의 최단거리 통로
0
74
1
집으로 이동 문제 코드
0
124
1
채점 사이트 개설
0
161
2
송아지를 잡자
1
110
1
다익스트라 + 환승횟수
0
135
2
문제풀이 해설 질문입니다.
0
124
2
"이동 횟수" 문제가 변형된다면?
0
155
2
예제 3번의 정답이 이해가 되지 않아요 선생님 ㅜㅜ
0
248
1
"비밀번호" 문제 확인 부탁드립니다!
0
170
1
최대 길이 연속수열 질문
0
192
1
잃어버린 강아지 문제 count 관련 질문있습니다
0
202
1
바둑대회 질문입니당
0
221
1
5. "최대 길이 바이토닉 수열" 에서 설명해주신 방법과 제가 직접 구현한 방법이 달라, 확인 한번 부탁드립니다
0
310
1
알파코드 풀이질문입니다
0
216
1
혹시 이렇게 작성해도 괜찮나요?
0
284
2
문제풀이 확인 부탁드립니다.
0
244
1
혼자서 푼 문제 확인 부탁드립니다.
0
298
1