당니의 개발자 스토리

1주차 개념 #9. 누적합(prefix sum) 자 오늘은 누적합이라는걸 배워보도록 할게요. 누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다. 오늘은 prefix sum 이라는 걸 배워보도록 할거에요. 뭐냐면 예를 들어서 배열이 1, 10, 11, 100 이라는 요소의 배열이 있다라고 칩시다. 이따가 코드 보면서 설명을 드릴건데, 누적합을 만들 때는 원본 배열 자체를 0번째는 아무런 값을 담지 않고 첫번째, 두번째, 세번째, 네번째 이런 식으로 담아야 돼요. 그러니까 보통 배열을 만들 때는 0번째부터 시작한다고 하잖아요. 그런데 prefix sum을 만들 때는 1번째부터 배열을 담아놔야 돼요. 이제..

1주차 개념 #8. 공간복잡도(space complexity) 공간 복잡도에 대해서 얘기를 해보도록 할게요. 공간 복잡도는 입력 크기에 대해서 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양이에요. 그러니까 예를 들어서 저희가 어떤 변수를 선언을 한다던가, 어떠한 요소들을 배열이든, map이든, set이든 담을 공간이 필요하다면, 사실은 이런 것들이 다 컴퓨터 메모리에 올라가게 되거든요. 그런 양을 뜻하는 게 바로 공간 복잡도다 라는 겁니다. 이는 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할경우도 포함하며, 배열이든 맵이든 셋이든 요소들을 담을 공간이면 다 적용됩니다. 이거 보시면은 a[10000000]가 지역변수고 b[1004]가 전역 변수잖아요. 이거 두..

1주차 개념 #7. 문제로 연습하는 시간복잡도 Q5 여러분 이 코드의 시간복잡도는 얼마일까요? 힌트는 등비수열의 합이 힌트입니다. 우리가 이런 for 문 같은 경우에는 시간 복잡도가 O(N)이라는 게 되게 쉽잖아요. 그런데 우리가 익숙치 않은거는 사실은 이러한 재귀함수, recursion이 좀 어렵습니다. 근데 여러분 제가 지금부터 정말 쉽게 이 재귀함수의 시간 복잡도를 구하는 것을 알려드리고자 합니다. 기억하세요. 재귀함수의 시간 복잡도는 재귀함수의 main 로직이 있어요. 재귀함수의 시간복잡도는 main 로직 X 그 함수가 몇 번 호출되느냐 인거에요. 자 여러분 이 함수의 main 로직이 뭐죠? 이 함수의 main 로직은 정말 간단해요. cnt++ 하고 출력하는 상수 시간의 시간 복잡도를 가지는 로직..

1주차 개념 #6. 문제로 연습하는 시간복잡도 Q4 자 오늘은 조금 어려운 거를 해보려고 해요. 여러분 이 코드의 시간 복잡도는 얼마일까요? solve라는 함수를 보면, 입력 n을 받아 가지고 i는 0보다 클 때까지 루프를 돌립니다. 여기서 이 부분은 상수니까 이 루프가 몇 번 반복되는가가 이 알고리즘의 핵심이다, 즉 이 알고리즘의 시간 복잡도를 측정하는 핵심이다. 라는 걸 알 수가 있죠. 그럼 이게 몇 번 반복될까 라는 거를 오늘 차근차근 얘기를 해보도록 할 텐데, 로그는요 지수함수의 역함수구요. 로그는 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다고 볼 수가 있습니다. 자 뭐냐면 차근차근 설명을 해볼게요. 밑이 2인데, 이 밑을 몇 번 곱해야 x가 되냐 라는 거를 log2(x..

1주차 개념 #5-2. 문제로 연습하는 시간복잡도 Q3 점화식 설명 저희가 앞선 문제의 시간 복잡도를 구할 때 cnt라는 녀석을 기반으로 해서 디버깅을 했죠. 근데 이렇게 한 건 사실은 cnt를 기반으로 디버깅을 하면서 어림잡아서 한 거죠. 한 3가지를 기반으로 해서 어림 잡아서 시간 복잡도가 뭐뭐이다. 하면서 이렇게 계산을 한 거예요. 근데 사실은 정석적으로 얘기를 하면 이러한 걸(cnt, 디버깅) 기반으로 점화식을 만들어야 돼요. 점화식을 만들고 이 점화식을 기반으로 시간 복잡도를 파악을 해야 돼요. 근데 사실상 코딩 테스트를 하면서 이 점화식을 만들기라는 것은 굉장히 어려워요. 정말로 이거는 실력이 매우 뛰어난 사람 아니면 코딩 테스트를 하면서 점화식을 만들어서 시간 복잡도를 계산한다? 이거는 힘들..

1주차 개념 #5-1. 문제로 연습하는 시간복잡도 Q3 이 코드의 시간복잡도는 얼마일까요? 이 코드 go 라는 재귀함수가 들어가 있네요. '아니 선생님 재귀함수를 갑자기 어떻게 풉니까! for 반복문도 어려운데' 여러분 어려울 땐 생각만 하지 말고 뭐 하라고요? 디버깅을 하십시오. 그러니까 사실 시간 복잡도는 단순해요. 시간 복잡도는 몇 번 반복되느냐, 어떠한 로직 자체가 몇 번 일어났냐라는 걸 판단해서 그걸 식으로 만들어가지고 빅오 표기법으로 표현하는 거예요. 그러면 자 이거는 반복문이 아니죠? 대신 이런 식으로 재귀함수로서 go 라는 함수가 이렇게 호출이 되고 있죠? 그러면 이 go라는 함수가 몇 번 호출됐는지가 이 코드의 시간복잡도를 결정되는 핵심이겠네요. 자 그럼 어떻게 하면 돼요? cnt 만들고..

1주차 개념 #4. 문제로 연습하는 시간복잡도 Q2 다음 코드의 시간복잡도는 얼마일까요? '아니 선생님 저희 그냥 지금까지 n 제곱, 이런 식으로 하나의 입력 값을 기반으로 시간 복잡도를 재지 않았나요? 지금처럼 N도 들어오고 M도 들어오면 어떡해요?' 그냥 여러분 더하시면 됩니다. 물론, 이런 식으로 N x M 의 시간복잡도가 발생할 수도 있어요. 그냥 이렇게 N 따로, M 따로 라고 생각을 하시면 돼요. 지금 이 코드의 시간복잡도는 정말 단순해요. 중첩되지 않고 그냥 나열되어 있으면 플러스 라고 보시면 되는데, N + M 이죠. 근데 만약에 이 코드가 이렇게 되어있으면 얼마일까요? 그러면 플러스가 아니라 곱하기 겠죠. NM의 시간복잡도를 가지는 거예요. 자 다시, 입력 값이 하나가 아니라 여러개가 들..

1주차 개념 #3. 문제로 연습하는 시간복잡도 Q1 여러분 이 코드의 시간복잡도는 얼마일까요? 강의를 중지하시고 풀어보세요. 이 로직은 정말 단순하죠. a를 출력하는 건데, 이 코드의 시간복잡도는 얼마일까요? 간단한 로직이기 때문에 상수 시간입니다. 그러면 얼마만큼 반복되느냐가 이 시간 복잡도를 결정하는 척도인 건데, 자 그러면 얼마만큼 반복되고 있을까요? 여러분 생각을 하지 말고 실천을 합시다. 디버깅을 한번 해볼까요? 이렇게 해서 정말 몇 번이나 반복되는가를 cnt를 통해서 디버깅을 해보는 거예요. 자 그러면은 디버깅을 해보면, n이 3일 때 3번 반복이 됐죠. 그리고 n이 4일 때 6번, n이 5일 때 10번, n이 6일때 15번 반복된 걸 볼 수가 있어요. 이거를 제가 표로 한번 나타내 볼게요. ..