-
ICE BREAKING
10대 때 꿈이 있다고 하니 모의고사가 몇 등급인지 물었다.
30대 때 꿈이 있다고 하니 다들 그만하라고 했다.
그리고 그 말을 그대로 들었으면
오늘날의 나도 없었을 것이다.
내가 성공하니 내가 안될 거라던 놈들의 말이 제일 빨리 바뀌더라
남의 말을 듣지 말고 너의 꿈을 믿어라
너는 이미 정답을 알고 있다.
"100억대 자산가가 100만원 밖에 없었을 때 들은 말"
-
우리의 자세!
-
포기하지 않고 어떻게든 해결하는 끈기,
-
(새로운 것에 대한) 두려움 깨기
2-1. 아는 것과 모르는 것을 구분하는 메타 인지
2-1-1. 모르는 것에 대해 물어보는 용기(불취하문)
2-2. 막연함을 구체적임으로 바꾸는 전략 & 계획성
-
하나의 언어를 마무리하고 이를 확장하기
-
각종 세부 스킬(Github, 디자인, 비즈니스 모델 등)
강의를 왜 이렇게 빨리 시작하게 되었나요? 알고리즘 테스트를 기반으로 코딩 역량 테스트 시험을 진행할 예정인데, 다들 막연한 어려움에 의해서 알고리즘 테스트에 대한 시도를 두려워할 거 같아 10월 16일인 오늘 두려움을 최대한 깨서 주말동안 많은 노력을 통해 모두가 성장했으면 하는 마음에.....
작성시점인 목요일(10월 15일)인 지금 자료를 만들어 나갑니다...
이를 기반으로 모두가 파이썬 관련 강의가 어느 정도 마무리되는 시점에 프로젝트를 기본적으로 수행할 역량까지 올라갔으면 합니다.
-
-
- 20대 때 꿈이 있다고 하니 어느 대학 나왔는지 물었다.
-
00 알고리즘 소개
-
영화 "소셜 네트워크" 중에서
https://youtu.be/L9bXhoHkpGw?start=151&end=190
상황 설명(영화 "소셜 네트워크") : 페이스북의 창립자 마크주커버그는 여친에게 이별을 통보받고, 이를 복수하고자 하버드 내에 있는 DB를 기반으로 여자를 평가하는 사이트를 기획한다.
조건
-
사람 둘을 비교하는 프로그램
-
내장된 데이터 : 하버드 기숙사에 등록된 사진 시련( 중앙 DB가 없기 때문에)→해결( 모든 이미지는 사람들이 든 각 '기숙사'에서 빼온다.)
"역시 공개지만 인덱스는 없는 아파치, 빈 검색이면 이미지와 데이터를 페이지에 돌려준다. 그 페이지를 저장하면 브라우저로 이미지가 저장된다. "
- 입력 데이터 : 개별 인물의 호감도를 점수로 매기는 것이 아닌 두 사진중 호감가는 선택으로 순위 매기기
4)평가 함수 :
$Ea=1/(1+10(Rb*Ra)/400)$
$Ea=1/(1+10(Rb*Ra)/400)$
"각 여자의 기본 등급을 1400으로 두고, 일정 시각에 여자-a는 Ra등급, 여자-b는 Rb, 여자 둘을 붙여놓을 때 예상이 나간다. 현 등급이 예상되지?"
-
- 위의 사례처럼, 알고리즘은 어떤 조건들과 원하는 결과물을 뽑기 위해서 필수적이다.
-
-
0. 강의소개
-
알고리즘 강의 목차
-
Chap 1. 알고리즘 : 효율, 분석 차수
1.1 알고리즘이란?
1.2 알고리즘의 효율성
1.3-1.4 알고리즘의 분석과 차수
-
Chap 2. 분할정복
2.1-2.2 이분 검색과 합병 정렬
2.3-2.4 분할정복과 퀵 정렬
2.5 쉬트라쏀의 행렬 곱셈
2.6 큰 정수의 계산법
2.7 분할정복과 트로미노 퍼즐
-
Chap3. 동적계획
3.1 동적계획과 이항계수
3.2 최단 경로 문제와 플로이드 알고리즘
3.4 연쇄 행렬 곱셈
3.5 최적 이진검색트리
3.6 외판원 문제와 동적 계획법
-
Chap4. 탐욕 알고리즘
4.1 서로소 집합과 크루스칼 알고리즘(최소비용 신장트리 문제)
4.2 최단 경로와 다익스트라 알고리즘
4.3 마감시간 있는 스케쥴 짜기
4.4 허프만 코드와 허프만 알고리즘
4.5 배낭 문제와 동적 계획법
-
Chap5. 되추적(백트래킹)
5.1 백트래킹과 n-Queens 문제
5.2 n-Queens 문제의 구현
5.4 부분집합의 합 구하기
5.6 해밀턴 경로와 외판원 문제
-
-
알고리즘을 공부하는 이유
**1) 원론적인 이유** - 어떤 문제를 컴퓨터로 해결하는 방법에 대한 탐구 - 컴퓨터 과학 연구의 가장 기초적인 분야 **2) 현실적인 이유** - 각종 프로그래밍/코딩 경진대회 출전 및 입상을 위해 - 코딩 테스트/코딩 인터뷰를 통해 취업을 하기 위해3) 현재 시점
- 알고리즘 테스트/ 코딩 역량 테스트 통과하려고 하는데, 막상 알고리즘 테스트라고 해서 보았더니.. **너무 막막해서 기초가 부족한 거 같아서 들어야 할거 같아서???**그런데!!! 위 구문들을 살펴보면, 내가 모르는 것이 없다. (if, else, for in, range) 그럼에도 불구하고, 알고리즘 테스트가 하기 어려운 것은 전략의 부재&익숙하지 않음!!
관련 책만 보더라도 **"Foundations of Algorithms" 5th Ed.**로 뭔가 보기 싫은 원서일 수 있다.
-
우리는 고등학교 수학 문제에서 쉽게 문제를 풀었던 경험들이 있다.
-
<문제><특징> → 혹은 패턴, 특성, 성질 등등등우리는 그동안 알고리즘이라는 형태의 해결방안을 써보지 않은 것이지,
수학 문제 등 다양한 문제에서 전략&논리와 함께 문제를 해결을 못한 적은 없았다.
그러기에 더더욱 가깝고도 먼 알고리즘의 세계!
- <전략&논리> → 알고리즘 수립 → 코딩
-
알고리즘 역량 강화를 위한 로드맵
-
첫번째에 주석을 통해서 Workflow를 계획 및 설정하도록 한다. → 이때 세부적인 조건들을 계속적으로 작성해나가면서 예외사항은 어떻게 핸들링할지를 고려한다.
-
이를 기반으로 나만의 알고리즘을 작성해나간다. (명확한 알고리즘 작성을 위해 엔코아에서 제공해준 알고리즘 기초 지식을 공부한다. )
-
이후에는 코드를 작성해나가고, 문법 오류는 없는지, 실제 알고리즘과 연동성의 오류는 없는지 체크해나가면서 검토한다.
-
코드 실행에 대해서 조급해하지 말고, 코드 실행 전에 검토를 한번 하고, 예외나 실수등을 점검한다.
4-1. 코드 맞으면, 그 과정에서 나타난 실수는 오답노트처럼 정리한다.
- 코드를 마무리하게 되면, 나보다 뛰어난 코드 중에 어떤 로직을 통해서 코드를 작성해나갔는지에 대해 정리하도록 한다. (한줄씩 곱씹어보면서, 나의 로직에 적용할 수 있는 것을 고민해보기!)
-
-
본 강의의 목적 및 응용
1) 이론보다는 **응용**(수학적 증명은 최소한으로) 2) C 언어가 아닌 **파이썬 언어**를 사용 3) Pseudo Code에서 완전한 구현까지 (??) -
강의 이후 일정
- 책을 기반으로 스터디 진행(혹은 조별로 강의하기) ← 그저 제안.....
-
-
-
Chap 1. 알고리즘 : 효율, 분석, 차수
-
1.1 알고리즘이란?
- 1.1.1 알고리즘과 친해지기
-
정의
알고리즘이란?
정의 : 알고리즘 (라틴어,독일어: Algorithmus,영어:algorithm, 어원 : 페르시아 수학자 알콰리즈미의 이름에서 유래 )이란 어떠한문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다. 수학과 컴퓨터 과학에서 알고리즘이란 작동이 일어나게 하는 내재하는 단계적 집합이다. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다.
- 어떤 문제를 컴퓨터로 풀기위한 효율적인 절차
- 문제를 푸는 단계별 절차를 명확하게 기술
-
목적
- 어떤 문제를 컴퓨터로 해결하는 방법을 공부함.
- 특정 프로그래밍 언어나 문법과 무관함.
- 다양한 문제해결 방법(알고리즘 설계 기법)을 공부함.
- 알고리즘 문제를 이해하고 효율적으로 해결하는 방법을 공부함
- 새로운 문제를 만났을 때, 그것을 해결할 수 있는 능력을 배양함
-
알고리즘의 조건
알고리즘은 다음의 조건을 만족해야 한다.
-
입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
-
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)
-
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
-
유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
-
효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.
명확성과 효율성을 위해서 우리는 알고리즘 이론을 배우는 것이다!
-
-
좋은 알고리즘의 분석 기준
- 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
- 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
- 기억 장소 사용량 : 수행에 필요한 저장 공간
- 최적성 :그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 **'가장 좋은'**의 의미이다
- 복잡도 (점근 표기법 : Big-O Notation) : 입력 자료의 크기가 N일 경우, 계산되는 수행시간의 (매우 중요하므로, 추후에 설명)
-
Break Time "벌새 프로젝트"
https://youtu.be/yMOxBB5gAKQ?start=5&end=37
상황 설명 : 증권 전산 데이터 센터(캔자스)와 증권 거래 서버(뉴욕)간의 데이터 전송 및 처리를 1ms (0.001초)를 줄일 경우, 하루에 500만 달러 정도의 시세차익을 거둘 수 있음.
이 경우, HW(캔자스와 뉴욕 간의 직선 거리로 통과하는 지하 통신선)와 이를 연결하는 SW(최대한 빠른 처리를 위한 알고리즘, 여기서는 1ms를 줄이기 위해 알고리즘을 계속해서 보완해나간다.)
-
- 1.1.1 알고리즘과 친해지기
-
1.1.2 알고리즘의 구성 요소
-
문제와 해답
- 문제란 해답을 찾으려고 물어보는 질문
- 파라미터는 문제에서 특정한 값이 지정되어 있지 않은 변수
- 입력 사례란 문제의 파라미터에 지정된 특정한 값
- 특정 입력사례의 해답은 해당 파라미터를 입력사례로 질문한 문제의 해답
- 어떤 문제의 모든 입력 사례에 대해서 해답을 찾아주는 단계별 절차
- 입력 파라미터에 어떤 입력 사례가 주어지더라도 해답을 찾을 수 있어야 함.
-
👍 고등학교 수학과정("순서도와 알고리즘")
-
알고리즘에 대한 이해를 돕기 위한 함수의 구성요소 : def(), return
def() 란? 파이썬에서 함수를 정의할 때는 def문을 사용한다. def는 '정의하다'라는 뜻의 영어 단어 define에서 앞 글자를 딴 것이다. def 문은 다음과 같은 양식으로 작성함
def 함수이름(): #1. 첫행 본문 #2. 함수를 호출했을 떄 실행할 코드 블록- def 예약어로 시작하는 첫 행에는 함수의 이름을 쓴다. 함수의 이름(t식별자 규칙(2.2.4)에 따라 의미를 알 수 있게 짓는다. 함수 이름 뒤에는 괄호를 붙인다.
- 함수의 본문은 함수를 호출했을 떄 실행할 파이썬 코드다. 원하는 만큼 여러 행의 코드를 작성할 수 있음.
return 이란? 반환 및 종료를 의미, return 문을 만나면 현재 함수를 종료하고, 호출한 곳으로 이동, 반환 값이 있을 경우 해당되는 반환값과 함께 호출한 곳으로 이동.
0 → 정상 종료 -1 → 에러 발생 1이상 → 정상 종료되었으나 다른 인자가 있음을 나타냅니다. -2이하 → 에러 발생했고 구체적으로 어떤 것인지 나타냅니다.
실제 활용 예시
-
1. 순차 탐색 문제
- 문제 : 어떤 수 x가 n개의 수로 구성된 리스트 S에 존재하는가?
- 해답 : x가 존재하면 x의 인덱스가, 존재하지 않으면 0에 해답
- 파리미터 : 정수 n (>0), 리스트 S(인덱스 범위는 1부터 n까지), 원소 x
입력 사례 : S = [0,10, 7, 11, 5, 13, 8], n = 6, x= 5, x = 9
입력 사례에 대한 해답 : location = 4, location = 0
-
알고리즘 : 모든 S에 대해서 x의 인덱스를 찾아주는 단계별 절차
-
S의 첫째 원소에서 시작하여 x를 찾을 때까지(x가 없는 경우 끝까지)
-
각 원소를 차례로 x와 비교한다.
-
만약, x를 찾으면 x의 인덱스를 리턴하고,
-
x를 찾지 못하면 0을 리턴한다.
-
Jupyter Notebook을 활용하거나 코드가 막히거나 이해하는 것이 어려운 경우,
한 줄씩 보는 것이 가장 중요하기 때문에,
꼭!!꼭!!! 파이썬 튜터를 써주세요...(python tutor)
n을 세거나 -
2. 리스트(배열) 원소의 합 구하기
-
문제 : n 개의 원소를 가진 리스트(배열) S의 원소의 합을 구하시오.
-
해답 : 리스트(배열) S의 모든 원소들의 합
-
파라미터 : 리스트 S, 정수 n
-
입력 사례 : S = [-1, 10, 7, 11,5, 13, 8], n =6
-
출력 사례 sum = 54
-
알고리즘 : S의 모든 원소를 차례대로 sum에 더하는 절차
- sum을 0으로 초기화 - 모든 S의 원소에 대해서 sum += S[i]를 실행 - sum의 값을 리턴
-
-
3. 리스트의 정렬 문제
-
문제 : n개의 수로 구성된 리스트 S를 비내림차순으로 정렬하시오.
-
해답 : S를 비내림차순으로 정렬한 리슽
-
파라미터 : S,n
-
입력 사례 : S = [-1, 10, 7, 11, 5, 13, 8]
-
입력 사례에 대한 해답 : S' = [-1, 5,7,8,10,11,13]
-
알고리즘 : 모든 S에 대해서 S'을 찾아주는 단계별 절차
- 교환 정렬, 삽입 정렬, 선택 정렬, 합병 정렬, 퀵 정렬 기타 등등 - 여러 가지 정렬 알고리즘 중에서 교환 정렬 방법으로 구현.
-
-
-
(Plus) 복잡도를 확인하기 위한 Big-O 판별법
미리보기 <복잡도를 표현하는 Big-O Notation >
- 복잡도. (점근 표기법 : Big-O Notation)
-
시간 복잡도 T(n)
: 실행시간이라는 관점에서 알고리즘의 효율을 측정하고, 연산자의 숫자 혹은 연산 과정의 수
ex) n 이라는 인자가 주여졌을 때, 1부터 n까지를 더하는 함수 sumOfN을 정의
$T(n) = 1 +n$
**T(n)**은 사이즈가 n인 문제를 푸는데 걸리는 시간을 의미, 여기서는 즉 1+n steps를 말한다.
-
Pop quiz
while 구문이 경우, i를 하나씩 증가시켜, n번을 시행하게 된다.
for 구문이 경우는 하나의 for loop에서 n회 시행, 또 다른 for loop에서 n회 시행하여, 총 $n^2$회를 진행하게 된다.
-
Big-O
문제의 사이즈가 커질수록, 최고 차항의 차수가 결과에 가장 많은 영향을 미친다. 이처럼 시간 복잡에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 것을 Big-O 표기법이라고 한다.
-
$O, \Omega, \Theta$ (Big O, Omege, Theta)
-
O(빅 오)
- **복잡한 함수의 점근적 상한**을 표기 - 주어진 알고리즘의 증가율보다 크거나 같은 **최소의 증가율**을 찾는 것이 목적 -
$\Omega$(오메가)
- 복잡한 함수의 **점근적 하한을 표기** - 주어진 알고리즘의 증가율보다 작거나 같은 **최대의 증가율**을 찾는 것이 목적 **** -
$\Theta$(빅 세타)
- 주어진 함수의 상한과 하한이 같은지 아닌지를 결정 - 세타 표기버은 항상 상한과 하한 사이에 존재
프로그래머스 알고리즘 테스트 수행시 최악의 경우과 최고의 경우를 고민해보는 것도 좋을 거 같습니다.
-
-
- 복잡도. (점근 표기법 : Big-O Notation)
-
'Identity_Protfolio&Interview > 07_Presentation & Lecture' 카테고리의 다른 글
| [문지의 알고리즘 강의 5강] 자료구조 알기 (0) | 2020.12.18 |
|---|---|
| [문지의 알고리즘 강의 3강] 알고리즘 테스트 1단계 맛보기 2 (0) | 2020.12.18 |
| [문지의 알고리즘 강의 2강]알고리즘 테스트 1단계 맛보기 (0) | 2020.12.18 |
| 비즈니스 모델 알아가기 (0) | 2020.12.18 |
