패스트캠퍼스 Python 코딩테스트 강의 3주차

 

개발자 취업 합격 패스 with 코딩테스트, 기술면접

 

패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓

 

Content

Part 2부터는 알고리즘 이론이 나온다.

 

알고리즘 이론

버블정렬 등 유명한 정렬 알고리즘들은 이미 다 구현이 되어 적용되어 있는데 왜 공부해야 할까?

지금까지 만들어진 알고리즘들 중에 가장 잘 만들어진 것을 익히고 배우는 과정이기 때문.

미술에서의 모사처럼 알고리즘도 따라 하며 배워야 할 필요가 있다. 이를 기반으로 알고리즘을 풀어나가면 더 잘 만들 수 있을 것이다.

 

알고리즘을 구현을 연습할 때에는 바로 코드를 작성하지 않고,

연습장에 쓰며 알고리즘을 고안한 다음에, 에디터에 옮겨 동작하는지 확인하는 방식으로 하면 좋다.

그래야 효율적인 알고리즘을 고안하기 좋다.

 

권장되는 알고리즘 연습 방법은 아래와 같다.

1. 연습장과 펜을 준비

2. 알고리즘 문제를 읽고 분석 후

3. 간단하게 테스트용으로, 매우 간단한 경우부터 복잡한 경우 순서대로 생각해 보며, 연습장과 펜으로 알고리즘 고안해 보고

4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어 적어봄

5. 코드화 하기 위해 데이터 구조 또는 사용할 변수를 정리

6. 각 문장을 코드 레벨로 적음

7. 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지 손으로 적으며, 임의 데이터로 코드가 정상 동작하는지 연습장과 펜으로 검증

 

정렬(Sorting) 알고리즘

다양한 정렬 알고리즘을 이해하며, 동일 문제를 해결하는 데에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고,

각 알고리즘 간 성능 비교를 통해, 알고리즘 성능 분석에 대해 이해할 수 있음.

 

버블 정렬 알고리즘

n번째와 n+1번째 항목의 값을 비교해 나가는 방식

1 바퀴를 돌 때, 제일 마지막 index에는 제일 큰 값이 가게 되므로, 2번째 바퀴에서는 맨 마지막 index를 확인하지 않아도 된다.

ex. 10개 데이터,

첫 번째→ 9번째 index에 최댓값

두 번째→ 8번째 index까지만 순회, 8번째 index에 최댓값

... 

아홉 번째 → 2번째 index까지만 순회, 2번째 index에 최댓값

 

하여 아래와 같이 구현했다

위에서 시간 복잡도는 O(n^2)이다. n까지 도는 반복문이 2개가 중첩되어 있기 때문.

 

잘 구현했는지 확인해 봅니다

구뜨

 

삽입 정렬 알고리즘

어떠한 데이터를 어떠한 위치에 삽입하는 방법

2번째 데이터부터 확인하여 앞의 데이터와 비교해 나가다가 바꾸어야 할 때 이동

 

간단하게 위와 같이 구현될 수 있다.

시간복잡도는 버블정렬과 같이 O(n^2)임.

 

잘 구현되었는지도 확인 완료우

 

선택 정렬 알고리즘

최솟값을 찾아 바꾸어 정렬하는 방법

가장 최솟값부터 앞에서 정렬하기 때문에, 정렬된 후에는 확인하지 않아도 됨

 

필요한 변수는 기준 인덱스, 비교 인덱스가 있겠고,

기준 인덱스는 0부터 data 길이 -1 까지,

비교 인덱스는 기준 인덱스+1부터 data 길이만큼까지 가면 되겠다.

 

이렇게 구현 및 확인해봅니닷

이 선택정렬도 시간 복잡도 O(n^2)이다

 

공간 복잡도

시간 복잡도와 공간 복잡도는 어느 정도 반비례 관계를 갖는다

최근에는 컴퓨터 메모리가 저렴해졌기 때문에, 시간 복잡도가 더 우선이다.

 

프로그램 실행 및 완료하는 데에 필요한 저장 공간을 뜻하는데,

총 필요 저장공간으로

1. 고정 공간: 알고리즘과 무관한 공간, 코드 저장공간, 단순 변수 및 상수

2. 가변 공간: 알고리즘 실행과 관련 있는 공간, 실행 중 동작으로 필요한 공간

이 있다.

 

빅오 표기법과 같이 고정 공간은 상수 이므로 무시되고 가변공간에 좌우된다.

 

재귀 용법 Recursive Call

고급 정렬 알고리즘으로 들어가기에 앞서, 재귀용법을 미리 익힘

함수 안에서 동일한 함수를 호출하는 형태 

 

가장 대표적인 Factorial 함수를 구현해 보자

 

이제 여기에서 시간 복잡도와 공간 복잡도를 구해보면,

n-1번의 factorial() 함수를 호출하여 곱셈하기 때문에 O(n-1)

factorial() 함수를 호출할 때마다 지역변수 n이 생성되기 때문에 O(n-1)

따라서 시간/공간 복잡도는 모두 O(n) 이다

 

재귀 호출을 사용할 때는 비슷하게 구현이 되는데 2가지 케이스가 있다.

첫 번째는 factorial 함수 구현한 것과 같은 케이스이고,

두 번째는 이런 형태로 사용된다.

 

1부터 입력받은 num까지의 곱을 출력하는 함수를 구현할 때,

아래는 재귀용법을 사용하는 multiple_r() 함수와 사용하지 않고 구현된 multiple() 함수의 예이다.

처음 사용할 때에는 어떻게 구성해야 하는지 감이 잡히지 않아 어려울 수 있으나 연습하다 보면 편안해질 것이다😊

 

과거 손코딩으로 많이 물어보던 회문 함수를 재귀를 사용하여 구현해 봅니다

 

동적 계획법과 분할 정복

동적 계획법 Dynamic Programming

가장 최하위 해답 구한 후 → 저장 → 결과값 이용하여 상위 문제 해결

상향식 접근 방법

Memoization 기법을 사용 (이전에 계산한 값 저장하여 다시 계산하지 않도록 함. 실행 속도 향상)

ex. 피보나치 수열

분할 정복 Divide and Conquer

문제를 나눌 수 없을 때까지 나누어 각각 해결하며 문제 해결

하향식 접근 방법

일반적으로 재귀함수로 구현

ex. 병합 정렬, 퀵 정렬 ...

 

두 방법 모두 문제를 잘게 쪼개 해결해 간다는 점이 있다.

차이점으로는

동적 계획법: 부분 문제는 중복되어, 상위 문제 해결 시에 재활용됨. Memoization 기법 사용하여 부분 문제의 해답을 재활용하는 최적화 기법 사용

분할 정복: 부분 문제는 서로 중복되지 않음. Memoization 사용하지 않음.

 

 

강사님이 말씀하시기를~~

강사를 포함한 많은 개발자들은 처음 알고리즘 문제 풀이를 할 때에는 여러 번 실패한다.

어떻게 하면 문제 풀이 역량을 기르는데 도움이 될 것인가 고민한 결과, 동일한 알고리즘을 사용하는 문제를 연이어 풀어 보는 것이 답인 것 같다고 함.

알고리즘을 이해하는 것도 어려운데, 문제 풀이는 알고리즘 이해를 넘어 문제에 적용하고, 시간제한 내에 풀어야 하기 때문에, 가능하다면 문제를 읽고 바로 어떤 유형인지 파악한 후 알고리즘 패턴에 맞게 풀어야 제한 시간 내에 풀 수 있다고 함.

이를 위해서는 알고리즘 각 문제에 대해서도 익숙해져야 함.

그러다 보면 문제를 봤을 때 어떤 알고리즘과 연관된 문제구나, 하고 알아차릴 수 있다고 함.

우선은 각 알고리즘을 이해할 수 있어야 하고, 후에 각 알고리즘에 대한 문제를 풀어보면 좋을 것 같다~!

 

최대한 쉬운 문제부터 다뤄 볼 예정이지만,

쉬운 문제라 하더라도 강사조차도 머리가 하얘지면서 감을 못 잡을 때도 있고, 문제 풀이를 보고도 어떻게 풀어야 할지 감을 잡기 어려울 때도 있다. 이러한 과정들을 겪으며 조금씩 나아지는 것이 알고리즘 풀이의 일반적인 과정이기 때문에~~

처음부터 고통받지 말고 좌절하지 말오라

라고 하셨따

 

Link

https://fastcampus.co.kr/dev_online_devjob

개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online. | 패스트캠퍼스

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

#패스트캠퍼스 #패캠 #FASTCAMPUS #자바 #자바스크립트 #파이썬 #코딩테스트 #패스트캠퍼스후기 #코딩교육 #코딩자격증