[친환경사과] Week 4 #816
[친환경사과] Week 4 #816
Conversation
There was a problem hiding this comment.
안녕하세요 @EcoFriendlyAppleSu 님!
열정이 넘치시는 것 같아서 정말 보기 좋네요.
제가 코틀린을 거의 몰라서, 코드에 대해 심도있는 리뷰는 못드려서 아쉬울 뿐입니다
그래도 우선, 모든 문제에 +@로 지난 문제까지 풀어주셔서, 우선 승인 드립니다!
리뷰 내용에 복잡도 분석 등의 의견을 드렸는데,확인 부탁드려요!
| /* | ||
| * target을 구성할 수 있는 모든 조합의 수를 구하는 문제 | ||
| * 재귀를 사용해 모든 경우의 수를 구한 후 구한 결과값에서 중복을 제거하는 방식으로 문제 해결 | ||
| * 시간 복잡도: O(2^(target size)) |
There was a problem hiding this comment.
target size가 혹시 어떤것을 의미하시는걸까요?
decode-ways/EcoFriendlyAppleSu.kt
Outdated
| * 메모이제이션을 사용한 문제 해결 | ||
| * 시간 복잡도: O(n) | ||
| * -> 주어진 문자열의 길이 만큼 순회 | ||
| * 공간 복잡도: O(1) |
There was a problem hiding this comment.
메모할 수 있는 공간이라면 아무래도 이 공간도 O(n) 만큼 복잡도가 필요하지 않을까요?
| * 주어진 숫자 배열에서 Subarray가 가장 큰 수를 구하는 문제 | ||
| * 시간 복잡도: O(n) | ||
| * -> 주어진 배열만큼 계산 | ||
| * 공간 복잡도: O(n) |
There was a problem hiding this comment.
지금 제출해주신 풀이도 충분히 훌륭한데요,
코드 내에서 dp[i]와 dp[i-1]만을 사용하고 있는것 같아요.
그렇다면 좀 더 최적화가 가능하지 않을까요?
| /* | ||
| * 오름차순으로 정렬된 두 노드 리스트를 크기 순서대로 병합하는 문제 | ||
| * 기준 노드와 다음 노드를 가리키는 포인터 노드를 상용해 문제 해결 | ||
| * 시간 복잡도: O(n) |
There was a problem hiding this comment.
두 리스트 길이의 합을 n으로 표기해주신것으로 보여요.
잘못된것은 아니지만, 두 리스트의 길이가 다를 수 있고, 이들을 합친다는게 중요하다는 점도 분석에 표현(O(m + n))해 주시면 더 좋을것 같아요!
| * -> nums 배열을 순회하며, 각 요소에 대해 board 배열에 값을 설정: O(n) | ||
| * -> board 배열을 순회하며, 값이 0인 인덱스 검색: O(n) | ||
| * --> O(n) + O(n) = O(n) | ||
| * 공간 복잡도: O(n) |
There was a problem hiding this comment.
열정이 넘치셔서, 괜시리 더 해주셨으면 하는 욕심이 좀 나네요..ㅎㅎ
가능하시다면 공간복잡도도 더 최적화 해 주시면 어떨까요?!
| * 주어진 문자열에서 자른 개별 문자열이 회문일 경우를 판단하는 문제 | ||
| * 시간 복잡도: O(n^2) | ||
| * -> 주어진 문자열을 자를 때 이중 반복문 수행: O(n^2) | ||
| * -> subString() 함수는 내부적으로 주어진 k 만큼 배열을 자르기 때문에 O(k)의 시간 복잡도를 가짐 |
There was a problem hiding this comment.
k의 최댓값이 결국 n이라고 볼 수 있지 않을까요?
그렇다면 O(n^3)으로 볼 필요가 있지 않을까 싶어요
| /* | ||
| * dfs로 문제 해결 | ||
| * 정해진 순서의 단어를 처리하는 부분에서 대부분의 시간 사용 | ||
| * 시간 복잡도: O(m *n) |
There was a problem hiding this comment.
m * n 크기의 지도를 주어진 단어의 길이(l) 만큼 반복해서 읽어야 하는 만큼, 단어의 길이도 복잡도에 영향을 꽤나 주지 않을까요?
또한 11 line의 공간복잡도에서도 단어의 길이가 영향을 끼칠것같아요.
최소한 단어 길이만큼은 재귀 스택이 반복 생성될 것으로 예상됩니다!
답안 제출 문제
체크 리스트
In Review로 설정해주세요.