2021.03.08 ~ 2021.03.13 항해 99 2주차 일기

이번주는 일주일 내내 알고리즘 구현에 관한 이론 학습과 응용의 연속!

 

그래서 이번주 회고록은 날짜별로 나열하기보다 배웠던 개념으로 작성하겠습니다 .🎈

 

재귀 함수

재귀 함수의 특징은 하나의 함수 안에서 똑같은 함수를 다시 호출한다는 점이다.

하노이의 탑 문제를 예시로 풀면서 개념을 배웠다.

재귀 함수를 이해하면서 숫자가 작아지거나 커지면서, 혹은 값이 계속해서 바뀌면서 내가 원하는 값을 찾아내는 함수를 구현할 수 있게 됐고, 다른 개념들을 함수로 구현할 때 도움이 됐다.

하노이의 탑

 

이분탐색

이분 탐색은 새내기 시절 학교 술자리에서 많이 했던 업다운 게임 개념이었다.

가장 큰 값과 작은 값의 중간을 지정해서 내가 원하는 값보다 작은지 큰지를 비교하고, 그 지점을 기준으로 잡고 계속해서 중간 값으로 탐색하는 방식이었다.

숫자를 하나 하나 찾는게 아니라 중간으로 뚝 잘라 찾아내기 때문에 시간 복잡도를 줄이는데 큰 도움이 됐다. 

스택,큐

빨래 바구니처럼 구멍이 하나라서 들어온 순서대로 나가는 것이 아니라 마지막에 들어온 값이 먼저 나가는 것이 스택의 큰 특징이었다. 

큐는 놀이기구 대기줄처럼 먼저 들어간 녀석이 먼저 나오는 입구와 출구가 따로 있는 저장소였다.

https://lewis-kku.tistory.com/5

2021.03.09 TIL 알고리즘 공부

 

DFS,BFS

DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다.

깊이 우선 탐색은 하나의 노선이 끝날 때까지 완벽하게 탐색을 마치고 다시 다른 노선으로 가는 방법이고 너비 우선 탐색은 마치 거미줄처럼 가장 가까운 곳을 하나 하나 탐색하는 방식이다.

그렇다 보니 DFS가 BFS보다 조금 더 간단하지만 BFS에 비해 값을 찾아내는 속도는 조금 느린 듯.

https://lewis-kku.tistory.com/6

2021.03.10 TIL 알고리즘 공부

브루트포스

brute : 무식한 force: 힘 이 두 단어가 합쳐진 용어처럼 무식하게 가능한 모든 경우의 수를 탐색하며 결과를 가져오는 방법이다. 이 알고리즘을 사용하면 예외 없이 100%의 확률로 정답을 찾아낼 수 있다.

하지만 시간이 오래 걸리는 단점이 있다. 위에서 언급했던 너비 우선 탐색(BFS)와 비슷한 방식.

 

동적 계획법

복잡한 문제를 여러개로 나눠 푸는 방식으로 재귀 함수를 이용해 내가 원하는 값을 쪼개서 해결할 수 있다.

이때 메모이제이션 (Memoization)이라는 개념이 한 가지 더 있는데, 함수가 작동하면서 구해진 값들을 저장소에 넣어놓고 같은 함수를 작동시키면 그 값을 불러와 대체해주는 역할을 해준다. 

전체 문제를 작은 문제로 나눠서 단순화 시키는 동적 계획법에서 여러번 수행될 수 있는 작은 문제들의 값을 메모이제이션을 통해 불러오면서 전체적인 시간 복잡도를 낮추고 효율적으로 만들어준다.

 

그리디 알고리즘

동적 계획법은 전체 문제를 쪼개는 과정과 그 작은 문제들을 해결하고 저장하거나 불러오는 과정이 필요하기에 지나치게 많이 일을 한다는 것에서 착안해 그리디 알고리즘이 나타났다.

항상 그 순간 순간마다 최고의 값을 판단하는 알고리즘으로 모든 경우에서 통하는 알고리즘은 아니지만 (알고리즘 예제를 푸는 과정에서 난 대부분 그리디 알고리즘으로 생각을 하다보니 처음 만든 코드는 반례가 항상 있었다...)

미래를 생각하지 않고 그 단계에서 최선의 선택을 하는 기법으로 설계하기에 가장 간단했다.

 

느낀점

이번주부터는 매일 혹은 2일에 한번씩은 꼭 그 날 배웠던 개념이나 활동에 대해 포스트하기로 마음 먹었는데 지키지 못해서 너무 아쉽다. 하루종일 알고리즘 예제만 보고있다보니 10시쯤 되면 지쳐서 더 생각하기가 싫었다..

그 날 바로 바로 기록해야 더 생생한 느낌을 적고, 더 자세하게 적을 수 있을텐데.. 다음주엔 꼭 실천하자!

 

항해 99가 3주차로 접어들면서 이젠 문제들이 초반보다 어려워진 느낌이다.

분명 문제를 다 풀고나서 보면 결국 쉬운 방법으로 알고리즘을 설계했는데, 문제를 딱 봤을땐 왜 그게 안떠오르는지 !

그리고 머리로만 생각하지 말고 수첩에 메모하면서 알고리즘을 펼쳐보는게 어느정도 도움이 된다는 점을 깨닳았다.

 

이번주 금요일과 토요일에는 뭔가 조금 지쳐서 문제 풀이에 속도가 확 낮아졌고 집중을 좀 못했다. 

2주가 넘게 낮에 계속 컴퓨터 앞에 앉아있다보니 체력이 떨어진게 아닌가 싶어서 오늘부터는 밖에서 가볍게 산책을 하더라도 꼭 체력을 기르는 것도 스케쥴에 추가해야겠다.

 

100일 후에는 내가 지금보다 더 멋진 사람이 되어있기를.