<항해99 2주차 WIL>

(1) WIL 개요

항해 99에서의 두번째 주가  지났다. 하루종일 알고리즘 문제를 풀면서 이번주를 보냈다. 저번주 금요일을 부터 시작해서 달려온 알고리즘 주차는 힘들기도 했지만 성장이 느껴졌다. 주로 나는 DP,BackTracking이 부족하여 공부를 했다. 이번주에는 내가 물제를 풀면서 다른사람들과 다르게 생각했던 문제들이나, 풀면서 어려웠던 부분, 어떤식으로 개념을 구체화 했는지 작성할 계획이다. 

 

(2) 일정

• 알고리즘 기본 지식 습득

• 알고리즘 문제은행

(3) 얻은 지식

알고리즘 기본 지식 습득

 

소수구하기

소수구하기는 대표적으로 에라토스테네스체를 사용하면 쉽게 풀린다. 에라토스테네스체는 처음 0~구간 까지의 소수를 구할 때 사용하는 방법이다. 그러나 그 수가 소수인지 아닌지만 판단할 때는 연산이 많아지는 편이다.

 

하노이탑

학교다닐 때 부터 정말 하노이탑이 이해가 되지 않아서 거의 포기했었던 문제였다. 수업을 들은지 2년이 지나서야 이해한 내가 너무 바보 같지만 그래도 지금도 확실히 이해했다기 보다는 받아드리는 편이다. 하노이탑의 경우 3개의 부분으로 나눠서 생각한다. 첫번째는 N-1개를 보조에 옮긴다. 두번째 마지막에 있는 것을 최종적으로 옮기는 곳에 놓는다. 세번째 보조를 첫번째로 바꿔서 N-1개를 보조에 옮기면서 반복한다. 

 

mergeSort

mergeSort는 왼쪽과 오른쪽으로 쪼개고 정렬을 진행한다. 즉 모두 1개씩 쪼개고 난 후 부터 merge함수를 진행한다.

 

나무자르기

내가 원하는 수를 찾는다면 무조건 이분탐색으로 찾자

 

DFS,BFS

DFS,BFS를 만날 때는 무조건 python에 dictionary를 이용해서 그래프를 만들자. list는 어려워..ㅜㅜ

 

DP

DP는 현재의 값이 이전의 값을 통해서 만들어서 해결하는 방법이다. dp같은 문제를 만나면 우선 피보나치를 생각하고

memmemorization (top down) 배열을 이용한 풀이 (bottom up) 방법을 생각하자.

 

가장 긴 수열의 합

가장 긴 수열의 합은 대표적으로 DP를 이용한 풀이다. 보통은 앞으로 진행하려고 한다면 너무 어렵다 하지만 그 지점에서의 최적의 합을 구한다. 즉 뒤에 것을 본다는 생각을 하게 되면 풀 수 있다.

 

알고리즘 문제 은행

 

그룹단어 체커

문자가 중복되는 것을 막는다. 중복을 제거한다. 그러면 스택으로 우선 접근해보자.

 

RGB

미로찾기 문제와 동일한 대표적인 DP문제 DP를 생각하는 습관을 갖자

 

기본수학

최대공약수(유클리드 호제법) ,최소공배수 , 이항계수 nCr 같은 것은 기본적으로 숙지하자

nCr = n-1Cr-1 + n-1Cr

 

다리 놓기 

이 부분은 수학을 정말 잘하는 여자친구님의 설명을 듣고 이해하게 되었다. 

답은 nCr인데 

크로스가 될 수 있다면 123 321이 다른 경우이므로 순열을 써야하지만 

사실상 123만 정답이므로 조합을 쓰는 것이다.

 

색종이 만들기

색종이 만들기를 통해서 분할 정복 및 재귀함수를 완전히 극복 할 수 있었다. 개인적으로 재귀함수 1타강사라고 생각한다. 재귀함수 및  backtracking에 대해서는 나중에 따로 포스터를 올릴 예정이다 정말 정성적으로 ㅎㅎ

 

 

ㅇ

(4) 느낀점

이번에도 진짜 조원들을 너무 잘 만났다. 내가 학교에서도 수업을 들었고 작년에 알고리즘을 조금 준비해봐서 알고리즘 초보자는 아니지만 엄청 잘하는게 아닌데 조원들 모두 엄청난 칭찬을 해주셔서 너무 고마웠다. 개인적으로는 팀원들 모두가 나 처럼 삽질하지말고 정말 최단거리로 가셨으면 하는 마음으로 이것저것 많이 알려줬는데 팀원들이 다행이 너무 좋아해주셔서 고마웠다. 그래서 나도 최대한 잘 설명하도록 노력했고 사람들에게 내 코드를 어떻게 하면 쉽게 알려 줄 수 있을 까 많이 고민하면서 코드를 보는 눈과 나의 실력도 많이 올랐다. 역시 혼자 하는 것보다 스터디 하는 것이 실력 향상에 도움이 많이 되는 것 같다. 조장님이 너무 분위기 메이커라서 정말 기분좋게 알고리즘을 진행했고 나를 제외한 다른 팀원님은 정말 열심히 노력하시고 배우시는 것을 바로 적용하려는 모습이 나한테는 없는 모습이라 배울게 많았다. 다음주 토요일날 시험을 신청했다. 1주차때 팀하신 분들과 준비할 예정이다. 토요일 까지 잘해보자 알고리즘!!!