4월25일 제로베이스에서 공부한 것과 Leetcode 코딩한것에 대해서 간략히 작성 합니다.
목차
- 알고리즘 평가 지표
- 경우의 수
- 점화식
- 코딩테스트에 대한 접근 법?
1. 알고리즘 평가 지표
1)알고리즘 성능 평가 지표
ㄴ 정확성
ㄴ 작업량
ㄴ 메모리 사용량
ㄴ 최적성
ㄴ 효율성
=> 시간 복잡도
=> 공간 복잡도
1-1) 시간 복잡도
ㄴ 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법
ㄴ 3가지 점근적 표현법
=> 빅오 : 최악의 상황을 고려하여 성능 측정 결과 표현 (대부분 빅오로 표현)
=> 세타 : 평균적인 경우에서의 성능 측정 결과 표현
=> 오메가 : 최선의 상황일 때의 성능 측정 결과 표현
ㄴ for문이 한개 일때 O(n)으로 표기 for문이 2개 일때 O(n제곱)으로 표기
해당 내용을 토대로 강의가 진행이 되었지만 최악에 상황을 고려하여 성능 측정 결과를 표현 한다는거 외에 다른 방법에 대해서는 아직 이해되는 부분이 부족함.
2.경우의 수
경우의 수
- 어떤 사건 혹은 일이 일어날 수 잇는 경우의 가짓수를 수로 표현
- 주사위 : 던지는 결과, 1 ~6 사이의 숫자이므로 경우의 수는 6
- 윷 : 던지는 결과 도,개,걸,윷,모 이므로 경우의 수는 5
1) 완전탐색으로 경우의 수를 푸는 알고리즘
ㄴ 순열 : 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수
ㄴ 조합 : 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수
ㄴ 중복 순열 :서로 다른 n개의 원소 중에서 r를 중복 있게 골라 순서에 상관 있게 나열하는 경우의 수
경우의 수에 대해서 순열과 조합을 for문과 재귀함수 강의가 구성되어 있었고, 재귀함수에 대해서 익숙해지고 이해하는 과정이 된 거 같다.
3. 점화식(=== 재귀식)
- 점화식이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식
- 대표적인 점화식
ㄴ 등차수열: F(n) = F(n-1) + a ( a는 고정된 상수)
ㄴ 등비수열: F(n) = F(n-1) x a
ㄴ 팩토리얼: F(n) = F(n-1) x n
ㄴ 피보나치 수열: F(n) = F(n-1) + F(n-2)
해당 식에 대해서 한번씩 사용 해봤지만 실제 코딩에서 사용하는건 더 사용 해봐야 익숙해질 것 같아서 어떠한 문제에 대해 식으로 접근 하는 방법에 알게 된 부분이 너무 좋았다.
LeetCode 코딩테스트 리뷰
문제번호 | 문제 이름 | 난이도 | 해결 여부
1 || Two Sum || Easy || 해결 완료
20 || Valid Parentheses || Easy || 해결 완료
21 || Merge Two Sorted Lists || Easy || XXX
35 || Search Insert Position || Easy || 해결 완료
53 || Maximum Subarray || Easy || 해결 완료
1번 문제와 35번은 for문과 if문으로 해결 할수 있었다.
20번 문제와 53번 문제는 문제를 이해 하는 과정부터 어려움이 있어서 시간도 오래 걸리고, 1시간 동안 풀지 못해서
20번 문제는 참고 사이트에서 문제 설명 부분만 읽으면서 코딩으로 변경 작업으로 해결 했다.
53번 문제는 참고 사이트에서 풀이코드가 있었지만, Math.max() 함수를 사용하지 않고 주어진 코드 내에서 텍스트로 설명된 부분을 이해 하며 구현 하니 해결 하게 되었다.
다만 20번,53번 문제 같은 경우 응용문제나 변형문제가 나오면 접근을 해당 내용을 기억해서 할수 있을지 확신이 없어, 다른 코딩 테스트 문제를 풀면서 접근 방식에 익숙해 지려 한다.
빅오같이 여러 가지로 알고리즘 시간 복잡도나 기초적인 걸 공부하는 게 너무 좋아보입니다. 저도 따라 공부하겠습니다.