시간복잡도

시간복잡도란 알고리즘을 이루고 있는 연산들이 몇번이나 수행되는지를 숫자로 표시하는 방식이다
예를 들어서 입력 n번에 대해서 프로그램A의 연산은 3n+2번이고 프로그램 B는 연산 5n^2+2번일 경우이 시간 복잡도를 이용해서 프로그램 A가 더 효율적이라는 것을 알 수 있다

이렇듯 같은 결과를 내는 프로그램일지라도 알고리즘을 어떻게 짜는 가에 따라서 그 효율성이 달라 질수 가 있다 그 극단 적인 예가 아래이다

최대차이 구하기

배열 A= [2,3,4....11,10,16] 이 있을 때 요소사이의 최대 차이를 구하는 문제이다

첫번째 방법 : 모든 요소를 비교한다
두번째 방법 : 최대값과 최소값을 찾아서 비교한다
세번째 방법 : 이미 정렬되어 있는 배열이라면 처음 요소와 마지막 요소를 비교한다

위 예시에서 각 사례의 시간 복잡도는 아래와 같다

1. o(n^2)
2. o(n)
3. o(1)

스프린트 리뷰

오늘 스프린트는 json 파일을 문자열로 변환해주는 함수인 JSON.stringify 함수를 구현해보는 것을 했다 이번 과제가 재귀를 이용한 스프린트 과제이기 때문에 재귀를 이용했다 처음에는 일단 배열과 객체일 경우 내부의 요소가 객체가 없을 경우만 생각해서 함수를 만들었는데 그렇게 만들고 나니 재귀를 해야할 떄 제대로 호출할 수 없었다 그래서 다시 뒤엎고 그림을 그려 가면서 알고리즘을 다시 짜보았다

그래서 위와 같은 그림을 그리고 다시 풀기 시작했는데 원하는 대로 정확히 나오지 않았다 문자열을 저장하는 result의 값이 제대로 유지가 안되는 것이었다 그래서 이를 해결하기 위해서 내부에서 저장 요소를 선언해서 그 값을 기준으로 재귀를 통해 얻어 오는 값을 할당하였더니 해결되었다. 재귀함수를 짤때 항상 고민되는 것이 현재값을 유지하면서 어떻게 그 다음 계산을 진행할지를 신중하게 정해야한다는 것을 알게 되었다.