09.27 ~ 29 (알고리즘)

 

 

3일 간 알고리즘에 대해서 학습했다.

알고리즘이란, 문제를 해결하는 최선의 선택이다.

우리는 최선의 선택을 하기 위해서 수도코드와 시간 복잡도를 신경 써야 한다.

 

---

수도코드 (의사코드)

 

컴퓨터는 사람처럼 한마디를 받음으로써 많은 것을 해결할 수 있지 않다.

예를 들어

빵에 잼을 발라줘라고 했을 때 우리는 알아서 식빵을 빵 봉투에서 꺼낸 후 잼 뚜껑을 열고

잼 나이프를 이용해서 식빵에 바르는 과정에 도달한다.

하지만 컴퓨터는 다르다.

컴퓨터에게는 빵에 잼을 발라달라는 요청을 매우 세분화해서 요청해야 한다.

식빵을 빵 봉투에서 꺼낸다. 만약 비어있다면 이 요청을 멈춘다.

잼 뚜껑을 연다. 잼 나이프의 앞부분을 이용해서 잼을 푼다. 잼 나이프를 이용해서 잼을 식빵에 넓게 펴 바른다.

위와 같이 우리는 컴퓨터답게 생각해야 한다. (물론 더 세분화할 수 있을 것이다.)

컴퓨팅적 사고를 해야 하는 것이다.

그 컴퓨팅적 사고에 가까워 지기 위해서 우리는 수도 코드를 이용한다.

수도코드를 이용해서 전체적인 흐름을 잡고, 그 흐름 속에서 시간을 단축시키고 디버깅을 할 수 있으며

다른 사람과의 소통도 원활하게 진행할 수 있게 된다.

따라서 수도 코드에 자신의 논리적인 부분을 더 녹여내는 것이 중요하다.

 

시간 복잡도

 

입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마만큼 걸리는 가를 따지는 개념이다.

즉, 효율적인 알고리즘은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한다.

시간 복잡도를 표기하는 방법은 세 가지가 있다.

 

• Big-O(빅-오) = 최악의 경우
• Big-Ω(빅-오메가) = 최선의 경우
• Big-θ(빅-세타) = 평균의 경우

Big-O를 가장 많이 사용하며,

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 따진다.

 

• O(1) = constant complexity, 즉시 출력
• O(n) = linear complexity, 입력값이 증가함에 따라 시간 또한 증가 (반복문)
• O(log n) = logarithmic complexity, BST의 탐색과 비슷
• O(n^2) = quadratic complexity, 시간이 n제곱으로 증가 (이중, 삼중 반복문)
• O(2^n) = exponential complexity, 종이를 반으로 계속 접어나가는 것과 비슷

시간 복잡도는 이 보다 더 다양한 개념이 많다.

내가 이해하기에는 아직 어려운 부분이라고 생각해서 큰 개념만 이해하고 넘어가야겠다고 생각했다.

나중에 다시 돌아와서 더 세부적인 포스팅을 통해 짚고 넘어가도록 할 것이다.

 

+

greedy(탐욕) 알고리즘 = 선택의 순간마다 최적의 상황만을 쫓아 최종적인 해답을 얻어내는 알고리즘

구현 = 알고리즘 문제를 푼다는 것은 내가 생각한 문제를 컴퓨팅 사고로 전환하여 코드로 구현하는 것을 말한다.

완전 탐색 알고리즘(BFA, Brute Force Algorithm) 

= 특정한 암호를 풀기 위해 모든 값을 대입하는 방법 ex) 자물쇠 암호 0000~9999까지 다 입력하기

이진 탐색 알고리즘 

= 데이터가 정렬된 상태에서 절반 씩 범위를 나눠 분할 정복 기법으로 특정한 값을 찾아내는 알고리즘 ex) up&down게임

순열 = 요소 n개 중에 m개를 선택하여 순서에 상관있게 뽑는 경우의 수

조합 = 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수

 

---

 

오늘의 일기

 

알고리즘에 특별한 개념을 신경 써야 한다고 생각해본 적이 없었다.

그냥 문제를 풀면서 나의 논리적인 부분들을 키워나간다는 생각뿐이었다.

하지만 3일 간 알고리즘에 대한 문제들에 헤딩을 하면서 새로운 개념들에 대해 습득할 수 있었다.

분명 시간 복잡도는 어려운 개념이라 아직까지 피부에 와닿지 않지만

수도코드는 정말 크게 와닿았다.

컴퓨팅적 사고를 해야 한다라는 것이 와닿으니 문제를 바라볼 때 더 많은 부분을 바라볼 수 있게 되었다.

요번 챕터의 문제들은 많이 어려웠다.

손을 못 댈 정도의 문제도 있어서 10분 넘게 문제만 바라볼 때도 있었다.

그래도 순열의 재귀 방법에 대해 혼자 이해했다.

재귀가 무척이나 어려웠는데, 순열의 재귀에 대해서 혼자 이해하게 되어서 속으로 뿌듯했다.

그런 뿌듯함을 얻으면서 어려움 속에 재미를 느낀 것인가 생각하기도 했다.

더욱 어려운 알고리즘 문제들이 많고, 알고리즘을 못한다고 해서 개발자가 되지 못하는 것은 아니다.라고 크루님이

말해주셨지만 그래도 틈틈이 알고리즘에 도전해서 내 논리적 사고방식을 기르는 시간을 갖도록 해야겠다.