19로그 - 반에서 가장 키 큰 사람 찾기 : 선형 알고리즘

1. 반에서 가장 키 큰 사람을 찾는 방법

• 한 명씩 물어보면서 키가 제일 큰 사람을 기억하고 다음 사람이 이전에 제일 큰 사람보다 크다면 그 사람을 기억한다. 이 과정을 끝까지 진행하면 가장 큰 사람을 찾을 수 있다.

 

2. 상황이 복잡해 진다면?

• 가장 키 큰 사람이 두명이라면?
• 가장 같은 키를 많이 가진 수의 사람들을 구한다면?

 

3. 자료구조의 중요성

• 이 로그에서는 자세히 설명해주지는 않지만 보다 빠르고 편리하게 계산하기 위해서는 적절한 자료구조를 선택해야 한다.
• 배열, 리스트, 맵, 셋 등등 자료구조의 특성과 장단점을 이해하고 사용해야 한다.

 

4. 예외 처리(멍청한 컴퓨터 말썽 못부리게 하기)

• 평균 값을 구하는 알고리즘을 만들 때 sum이라는 변수에 모든 값을 더한다.
• N이라는 변수에 개수를 구한다.
• 하지만 N이 0개라면? > 컴퓨터는 sum/N을 진행해버리고 0으로 나누는 참사(에러)가 발생할 것이다.
• 따라서 N이 0일 때는 계산을 하지 말라는 예외 처리가 필요하다.

5. 선형 알고리즘

• 처리 시간이 데이터양에 정비례 하는 알고리즘을 의미한다.
• 이 로그에서는 선형 알고리즘만 딱 말했지만 정비례하지 않는 알고리즘이 있을 것이다.
  • for 문을 n만큼 2번 돌면 n의 제곱만큼 계산된다. 이것은 정비례가 아닌 제곱에 비례하는 것이다.

6. 빅-오 표기법

• 책에서는 안알려주는 것 같지만 자주 사용하는 용어이다.
• 가장 높은 차수의 항만 표기하는 것이다.
  • for문을 n+1만큼 2번 돌면 n^2+2n+1만큼 돈다.
  • 이것을 O(n^2)으로 아주 쉽게 표현해주는 것이다.
  • 수학적으로 접근한다면 n이 3일때는 n^2=9, 2n+1=7이다 . 거의 반반씩 비율을 차지하고있다.
  • 하지만 n이 10000이라면? n^2=100000000, 2n+1=20001이다. 0.02% 비율이다.
  • 숫자가 커질 수록 가장 높은 차수의 항만 의미를 가지며 빅-오 표기법을 통해 시간 복잡도의 경향성만 표기하는 것이다.
• O(1) : 데이터 양에 상관없이 처리 시간이 일정함
• O(n) : 데이터 양에 비례하여 처리 시간이 증가
• NLogN, n^2, n^3, 2^n 등등 이 있다.
• 참고로 시간 복잡도를 구하는 방법은 최악의 경우를 생각하는 것이다.
  • n명의 사람 중 유재석를 찾으라고 했을 때 마지막(n) 번째 사람이 유재석인 경우