TIL

시간 복잡도 (time complexity)

• 시간 복잠도는 주어진 프로그램에 인풋값이 늘어날때 늘어난 인풋값에 비해 늘어나게 되는 시간 의 비율을 의미한다.
• 이러한 시간복잡도는 최선 평균 최악 등등으로 구분되지만 프로그래밍 에서는 최악을 기준으로 평가한다.(Big O)
• 아래 몇 가지 시간 복잡도를 표로 나타내었다.

  종류
  O(1)
  O(log n)
  O(n)
  O(n2)
  2O(n)
  O(n!)

탐욕법 (greedy algorithm)

• 매 선택에서 지금 최선인 답을 찾아가면서 문제를 풀이 하는 방식
• 다만 이게 문제를 풀수 있는 최선의 답이라고 말할수는 없다.
• 따라서 적용하려한다면 적용하려는 문제에 맞는지 확인해볼 것
• 프로그래머스에서 몇번 봄적있는 문제 패턴이지만 아직도 익숙하지는 않다.

동적 계획법(dynamic programming)

동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

• 코플릿을 풀면서 경험 해보았지만 아직 감이 잘 잡히지 않는다. 더 고민해봐야 할듯하다.

  ---

  오늘 한 것

• 휴식
• 스프린트 진행
• 리트코드 문제풀이
  • Running Sum of 1d Array (easy)
  • Shuffle the Array (easy)
  • Number of Good Pairs (easy)

---

To Do

• node.js를 이용한 서버관리나 서버와 클라이언트 간의 정보 교환 등 미리 공부할수 있는 부분에 집중해보는것도 좋은 선택이라고 생각한다.

• scss 도 활용을 생각해보면 좋을것 같다.

• typescript 공부 예제를 생각해보자

---

오늘은...

오늘은 알고리즘 스프린트를 진행하였다. 시간 복잡도, 탐욕법, 동적 계획법 등등 이전까지 들어만 보고 익숙치 않았던것들이 한꺼번에 올라오니 머리가 복잡하다. 코플릿 풀이도 막막해져가고 있다 4시간동안 4문제를 풀이하는 것이었지만 풀이법자체가 빠르게 생각나지가 않았다. 한 문제 정도는 빠르게 정리가 되었었고 다른 하나도 어찌저찌 풀어 내었지만 동적 계획법을 바탕으로 하는 풀이는 감이 잡히질 않는다. 빠르게 연살할수 있는 방법을 고민해야하는데 머리가 멍하다.