오늘 할일
- 알고리즘 문제풀이
- 포트 폴리오 예시템플릿 적용해보기
- 포트 폴리오 템플릿 찾기
- 채용공고 읽기
- 소프티어 코테체험
오늘 한 것 & 배운 내용
알고리즘 문제 풀이
최소공배수
- 연산을 통해 최대공배수를 구할까 고민하다 유클리드 호제법을 사용하는게 연산을 더 줄여줄것 같아서 그쪽으로 풀기로 계획을 했다
- 내풀이
- 먼저 유클리드 호제법을 이용해 최대공약수를 구하는 메소드를 작성한다
- 테스트 수 만큼 a,b를 입력받아 최대공약수를 구하고 a * b / d(최대공약수)라는 간단한 공식을 통해 최소공배수를 구해준다
- 유클리드 호제법 복습을 위해 푼 문제인데 다행이 아직까지는 잘기억하고 있어 수월하게 풀이할 수 있었다
다리 놓기
-
문제풀이를 위해 3시간정도를 할애했지만 재귀함수로 답까지는 구했지만 시간초과로 인해 결국 풀이하지 못하였다
- DP를 사용해야하는것 까지는알겠는데 어떻게 DP가 사용될 수 있는 식으로 분화시킬지를 찾아내지 못했다
-
결국은 문제 풀이를 보고 숙지하여 다음에 다시 푸는 것으로 해야될 것 같다
-
다른사람 풀이
-
허무하게도 지난번에 푼 '이항 계수'문제에 조합을 이용해서 푸는 문제였고 그 때 명확히 숙지 하지 못한 나는 결국 같은문제에서 해메고 있던 것 이었다
-
다리를 서로겹치지 않게 놓는 것이 조합의 문제임을 해석하는게 포인트였던것 같은데 그렇게 보지를 못해서 아쉽다
- M개에서 N개를 선택하고 서로 중복이 되지 않는다고 해석했으면 조합을 생각할 수 있었을 것 같다
- 중복 되지 않기 때문에 조합상으로 겹치는건 신경을 쓰지 않아도되는데 겹치는 경우여도 어차피 겹치지 않는 한개의 값을 선택한다고 생각해주면 되기 때문이었다
-
조합의 성질을 다시 복습하는걸로 마무리하고 다음주에 다시풀어봐야될 것 같다
- n개에서 k를 중복되지 않고 뽑는 방법은 n! / k!(n-k)!으로 구할 수 있다
- 조합의 성질을 이용해서 구할 수 도있다
- 성질1 :nCr = n-1 C r-1 + n-1 C r 가 같다
- 성질2: nC0 = n Cn = 1이다 (n=k일때 1)
- 위의 성질을 이용해 재귀함수를 통해 n = (n-1, k-1)+ (n-1, k ) 를 구해주면된다
- 이때 dp를 사용해서 연산한 값들을 활용하여 연산 횟수를 줄여줄 수 있다
- 월간 코드 챌린지 시즌1 문제를 풀어보려고 선택한 문제인데 시간을 오래들였지만 어려워서 못풀고 말았다
- 내일 이어서 풀기위해 남겨둔다..
사담
- 오늘은 알고리즘 공부는 시간 대비 많은 문제를 풀지못한날이었다.. 어려운문제는 어느정도 보고 넘어가야되나 싶기도 한데 또 제대로 이해안하고 넘어간 문제는 결국 다음에도 발목이 걸리기 때문에 볼 때 최대한 열심히 보자라는 마음으로보다보니 시간이 많이들어간다
- 여러가지 문제유형을 접하고 어려운것도 자주보면서 익숙해져야되기 때문에 한문제에 너무 오래보는건 효율이 떨어지는것 같다
- 내일부터는 유효시간 1시간정도로 정해놓고 안되면 답안을 보는 방식으로 진행을 해바야겠다
소프티어 코테체험
- 소프티어가 코딩테스트 체험 이벤트가 있어서 지나번에 신청을 해놨는데 오늘 참여를 하였다
- 1시간에 간단한 알고리즘 문제 2개를 푸는 형식이었는데 체험 이벤트라 그런지 문제가 어렵지 않아서 수월하게 풀어낼 수 있었다
- 아쉬운점은 체험이지만 제출만되고 전체 테스트코드에 대한 점수는 공개되지 않아서 뭔가 빼먹은게 있지않은가 하고 찜찜한 기분이 들었다
내일 할일
-
포트 폴리오 템플릿 찾기
-
채용공고 읽기
배우는 개발 일기