[부스트 코딩 뉴비 챌린지 2020] week4_코벤져스 LIVE 강의

PDF 파일 받기

 

모두를 위한 컴퓨터 과학(CS50 2019) 알고리즘 되짚어 보기

개발자가 되기 위해서 알고리즘은 가장 중요하며 반드시 거쳐야하는 것이다.

알고리즘은 생각하는 능력을 기르는 것이다. 컴퓨터가 어떻게 사고하게 할 것인지 배우는 과목이므로, 코딩을 얼마나 잘했냐보다는 얼마나 생각했는지가 중요하다.

 

알고리즘 효율성

컴퓨터 프로그래밍에서 "주어진 문제를 얼마나 효율적으로 푸느냐"는 매우 중요하다.

 

1024명의 학생 명단이 있을 때, 한 명의 이름을 확인하는데 걸리는 시간이 1초라 하면, '이진원'이라는 이름의 학생을 찾는데 걸리는 시간은?

- 선형 검색 : 최악의 경우 1024초 필요함

- 이진 검색: 최악의 경우 10초(=log_2 1024)가 필요함  (정렬되어있다는 가정하에)

따라서 효율적으로 계산할 수 있도록 짜야 한다.

하지만 한 가지 더 생각해야 하는 것이, 이진 검색을 하려면 정렬이 되어 있다는 가정하에 하는 검색이기 때문에 정렬하는데 걸리는 시간이 더 오래 걸린다면 선형 검색이 더 효율적일 것이다. 위는 정렬이 되어있다는 가정하에 이다. 

정렬하는데 걸리는 시간은 n log n이고 선형 검색은 n이다. n long n > n 이므로 정렬을 해놓고 한 명을 찾을 거라면 그냥 선형 검색을 하는 게 더 좋다. 하지만 찾아야 할 사람의 수가 더 늘어난다면 이진 검색이 더 효율적이다. 따라서 상황에 따라 효율적인 알고리즘이 계속 달라지므로 경우에 따라서 잘 생각해야 한다. 따라서 생각하는 능력이 중요하다.

1. 선택 정렬

 

2. 버블 정렬

큰 숫자를 오른쪽으로, 혹은 작은 숫자를 왼쪽으로 위치를 이동시키는 두 가지 방법이 있다.

3. 병합 정렬

알고리즘을 배우면 맨 처음에 정렬 알고리즘을 가장 처음에 배운다. 위의 세 가지 정렬 알고리즘을 잘 알아놓으면 나중에 배울 때 수월하다.

 

Big-O가 가장 중요하다. 이를 계산할 줄 알아야 한다. 인터뷰에서 자신이 작성한 알고리즘의 Big-O를 묻고, Big-O가 더 작아지도록 개선할 수 있는지 묻기도 한다.

정렬 알고리즘은 종류가 엄청 많으므로 많이 알수록 좋다.

4. 삽입 정렬

책꽂이에 이미 책이 꽂혀있는 경우에 책 정리하는 방법. 왼쪽과 비교하면서 하나씩 적당한 위치에 옮긴다. 이의 Big-O는 무엇일까? 

O(n^2) nxn이 되므로

오메가(n). 정렬이 되어있을 때 상황을 생각하면 된다. n번을 하는데 각각이 한 번만 비교하면 되기 때문에 n번이다.

 

4주차 알고리즘 미션 풀이

1번 문제)

1-2팀. 정렬 사용하지 않고 해결

0~9까지 배열을 만들고 첫 번째 배열은 각 숫자를 +n하고, 두 번째 배열은 각 숫자를 -n하여 그 배열의 결과가 0인지 보는 방법. 0이면 두 배열이 같으므로 

 

2번 문제)

답 : 친구들 집의 숫자의 중앙값에 위치한 좌표에 집을 구하면 합이 최소가 된다.

시간복잡도까지 분석

중앙값 찾는 알고리즘도 따로 있으므로 검색하여 찾아보도록 하자.

 

3번 문제)

 

모든 경우를 커버해주어야 한다.

1명일때 2명일 때 3명일 때 4명일 때 ... 4명 이상일 때는 모두 같음

4명씩 만들어서 2명씩 보내주면 되기 때문에.

4명이 있을 때 건너는 방법이 상황에 따라서 그 예시의 방법 말고 다른 방법이 또 있다. 

1 3 4 10의 경우 더 빠른 경우가 있다. 그래서 4명이 있을 때 상황에 따라서 다르다. 1 4랑 가고 1이 돌아오고 1이랑 10이 가고 1이 돌아오고 1 3이 가는 방법. 1이 왓다갓다하는 방법이 더 짧다. 이를 캐치하고 답안을 작성하면 미션pic인 14-9팀 답안이 완벽해진다.

 

4번 문제)

오른쪽으로 하는 것과 똑같기때문에 오른쪽의 빈칸이 몇개인지 찾아내기만하면 되는 문제였다. 

두 팀 모두 완벽하게 풀고 설명과 시각화까지 완벽하게 해줬다.

모든 상자에 대해서 다 계산을 해주려고한다면, 최대 움직일 수 잇는 거리는 n이기 때문에 n^3만큼 시간이 필요하다. 모든 알고리즘에 대해서 다 계산하려면.

근데 잘 보면 제일 꼭대기에 있는 상자가 열에서 젤 많이 움직이게 되어있다. 따라서 제일 꼭대기에 있는 상자들에 대해서만 각각 거리를 계산하면 되는 문제였다. 두 팀들은 제일 상단에 있는 상자에 대해서만 계산을 해주었다.
그러면 n개의 상자에 대해서 옆으로 n번만 오면 되므로 최종적으로 5n^2이 된다.

 

AI분야에 대한 설명

파이썬을 기본적인 언어로 사용한다.

텐서플로우와 파이토치