✨ 소감 ✨

-- 코치님 피드백으로 코드를 조금 더 깔끔하게 작성하는 방법과 if-elif-else 구문의 단이 많으면 좋지 않을 것같다는 의문도 해결되서 좋았다.

-- 그리고 4주차 때 우수미션 팀으로 뽑혔고, 내가 작성한 코드도 라이브 방송 때 소개 되어서 뿌듯한 경험이 되었다.

👉 딕셔너리와 튜플 ✨

👀 코드 보러가기 (colab)

Q1. 고려 및 조선 두 시대에 모두 사용된 이름의 개수

출력조건

1. 중복되는 왕 이름 목록 2. 중복되는 왕 이름의 수

Q2. 실적 평가

요구사항

1. 보너스 대상자는 평균 실적 1등과 2등 입니다. 2. 면담 대상자는 평균 실적 5등과 6등 입니다. 3. 보너스 대상자의 평균 실적이 5보다 크지 않으면, 보너스 대상자에서 제외됩니다. 4. 면담 대상자의 평균 실적이 3보다 크면, 면담 대상자에서 제외됩니다.

Q3. 수익률 계산

Q4. VIP 회원 구분

VIP 회원 조건

1. 구매 횟수가 8회 이상인 회원 2. 쿠폰 발행을 위한 전화번호가 있어야 함 (전화번호가 없을 경우, "000-0000-0000"으로 출력할 것)

• 학습목표 - Pythonic Code는 간단하게, 다른 사람의 코드를 잘 이해하기 위해서 파이썬 특유의 문법을 활용하여 효율적으로 코드를 표현하는 기법을 말한다. - Pythonic Code 를 작성하는 방법과 Matrices 와 Vector 의 연산을 Pythonic Code 로 구현하는 방법을 배운다.

1) 여러 단어를 하나로 붙일 때

colors = ['red', 'blue', 'green', 'yellow']
result = ''
for s in colors:
    result += s

colors = ['red', 'blue', 'green', 'yellow']
result = ''.join(colors)

2) Pythonic Code

• 파이썬 스타일의 코딩 기법
• 파이썬 특유의 문법을 활용하여 효율적으로 코드를 표현함
• 고급 코드를 작성 할 수록 더 많이 필요해짐

- Split & Join
- List Comprehension
- Enumerate & Zip

3) Why Python Code?

• 남 코드에 대한 이해도 -- : 많은 개발자들이 python 스타일로 코딩함

• 효율 -- : 단순 for loop append 보다 list가 조금 더 빠르고, 익숙해지면 코드도 짧아짐 --_ ↪ numpy가 훨씬 빠름_

2. Split & Join

• 학습목표: Split & Join 을 사용하여 String Type 의 값을 List 형태로 변환하고, List Type 의 값을 String Type 의 값으로 변환하는 Python Code 작성법을 알아본다.

• 핵심단어 - Split
  - Join
  - String
  - List
  - Unpacking

1) Split 함수

--String Type의 값을 나눠서 List 형태로 변환 --_ ↪ 많이 쓰이는 경우: 뉴스와 같은 데이터에 특정 단어가 몇번 등장하는지 등_

items = 'zero one two three'.split()
    ## ['zero', 'one', 'two', 'three']

example = 'python,query,javascript'
example.split(',')
    ## ['python', 'query', 'javascript']

a, b, c = example.split(',')
    ## a is 'python', b is 'query', c is 'javascript' : Unpacking

example = 'cs50.gachon.edu'
subdomain, domain, tld = example.split('.')
    ## subdomain is 'cs50', domain is 'gachon', tld is 'edu'

2) Join 함수

-- String List를 합쳐 하나의 String 으로 반환할 때 사용

colors = ['red', 'blue', 'green', 'yellow']
''.join(colors)
    ## 'redbluegreenyellow'
' '.join(colors)
    ## 'red blue green yellow'
', '.join(colors)
    ## 'red, blue, green, yellow'
'-'.join(colors)
    ## 'red-blue-green-yellow'

3. List Comprehension

• 학습목표: 파이썬에서 가장 많이 사용되는 기법 중 하나인 List Comprehension 을 사용하여 Pythonic Code 를 작성하는 방법을 알아본다.

• 핵심단어 - List Comprehension
  - Nested For loop

1) 정의

• 기존 List 사용하여 간단히 다른 List를 만드는 기법

• 포괄적인 List, 포함되는 리스트라는 의미로 사용됨

• 파이썬에서 가장 많이 사용되는 기법 중 하나

• 일반적으로 for + append 보다 속도가 빠름

2) 예시 (1)

result = []
for i in range(10):
    result.append(i)

    ## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[i for i in range(10)]    # list comprehensions
    ## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[i for i in range(10) if i % 2 == 0]    # list comprehensions & filter
    ## [0, 2, 4, 6, 8]

3) 예시 (2)

word_1 = "Hello"
word_2 = "World"

[i+j for i in word_1 for j in word_2]    # Nested For loop

## ['HW', 'Ho', 'Hr', 'Hl', 'Hd', 'eW', 'eo', ...]

4) 예시 (3)

case_1 = ["A", "B", "C"]
case_2 = ["D", "E", "F"]

[i+j for i in case_1 for j in case_2]

result = [i+j for i in case_1 for j in case_2 if not(i==j)]

result.sort()

5) 예시 (4)

words = 'The quick brown fox jumps over the lazy dog'.split()

stuff = [[w.upper(), w.lower(), len(w)] for w in words]
# list의 값 elements 들을 대문자, 소문자, 길이로 변환하여 two dimensional list로 변환

for i in stuff:
    print(i)

6) Two dimensional vs One dimentional

case_1 = ["A", "B", "C"]
case_2 = ["D", "E", "F"]

[a+b for a in case_1 for b in case_2]
# ['AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF']

[[a+b for a in case_1] for b in case_2]        # for b in case_2 부분이 먼저 고정 됨
# [['AD', 'BD', 'CD'], ['BD', 'BE', 'BF'], ['CD', 'CE', 'CF']]

4. Enumerate & Zip

• 학습목표: 리스트의 값을 추출할 때 함께 인덱스를 추출할 수 있는 방법으로 이용되는 enumerate 와 두 개 이상의 list 값을 병렬적으로 추출할 수 있는 zip 모듈을 사용하여 pythonic code 를 작성하는 방법을 알아본다

• 핵심단어 - Zip
  - Enumerate

1) Enumerate

-- List 의 element 를 추출할 때 번호를 붙여서 추출

for i, v in enumerate(['tic', 'tac', 'toc']):
    print(i, v)
## 0 tic / 1 tac / 2 toc

mylist = ['a', 'b', 'c', 'd']
list(enumerate(mylist))        # list의 index 와 value 를 unpacking 하여 list로 저장
## [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]

{i:j for i, j in enumerate("Gachon University in an academic institute located in South Kores.".split())}
# 문장을 list로 만들고 그 list의 index 와 value 를 unpacking 하여 dict 로 저장

2) Zip

-- 두 개의 list 의 값을 병렬적으로 추출함

alist = ['a1', 'a2', 'a3']
blist = ['b1', 'b2', 'b3']

for a, b in zip(alist, blist):    # 병렬적으로 값을 추출
    print(a, b)

## a1 b1 / a2 b2 / a3 b3

a, b, c = zip((1, 2, 3), (10, 20, 30), (100, 200, 300))    # 각 tuple 의 같은 index 끼리 묶음
## ((1, 10, 100), (2, 20, 200), (3, 30, 300))

[sum(x) for x in zip((1, 2, 3), (10, 20, 30), (100, 200, 300))]    # list comprehension 이랑 같이 사용해보기
## [111, 222, 333]

3) Enumerate & Zip

alist = ['a1', 'a2', 'a3']
blist = ['b1', 'b2', 'b3']

for i, (a, b) in enumerate(zip(alist, blist)):
    print(i, a, b)    # index alist[index] blist[index]

## 0 a1 b1 / 1 a2 b2 / 2 a3 b3

5. Lambda & MapReduce

• 학습목표: 함수처럼 사용가능한 익명함수인 Lambda, Sequence 자로형의 데이터에서 함수를 적용하는 방법인 Map Function 과 Reduce Function 에 대해서 여러 예제 코드를 이용해 실습하면서 Pythonic Code 를 작성하는 방법에 대해 공부합니다.

• 핵심단어 - Lambda
  - Map Function
  - Reduce Function

1) Lambda

• 함수 이름 없이 함수처럼 쓸 수 있는 익명함수로 수학의 람다 대수에서 유래함
• map 함수와 함께 쓰면 더 효율적임

f = lambda x, y: x+ y
print(f(1, 4))    # 5

f = lambda x: x ** 2
print(f(3))    # 9

f = lambda x: x / 2
print(f(3))    # 1.5

print((lambda x: x + 1)(5))    # 6

2) Map

• Sequence 자료형 각 elemnet 에 동일한 function 을 적용함 ↪ map(function_name, list_data)

ex = [1, 2, 3, 4, 5]
f = lambda x: x ** 2
print(list(map(f, ex)))    ## [1, 4, 9, 16, 25]

f = lambda x, y: x+ y
print(list(map(f, ex, ex)))    ## [2, 4, 6, 8, 10]

list(map(
    lambda x: x ** 2 if x % 2 == 0 else x,
    ex))
# lambda 에 filter 가능, else 는 필수로 넣어야 함
## [1, 4, 3, 16, 5]

3) Reduce

-- map function 과 달리 list 에 똑같은 함수를 적용해서 통합 (map과 같이 쓰는 경우가 많음, pandas 사용시 map과 함께 유용하게 쓰임)

from functools import reduce
print(reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]))    ## 15

## x = 1, y = 2
## x = 3, y = 3
## x = 6, y = 4
## x = 10, y = 5

def factorial(n):
    return reduce(
        lambda x, y: x*y, range(1, n+1))

factorial(5)    ## 120

⨁ Summary

• Lambda, map, reduce 는 간단한 코드로 다양한 기능을 제공
• 그러나 코드의 직관성이 떨어져서 lambda 나 reduce 는 python3 에서 사용을 권장하지 않음
• Legacy library 나 다양한 머신러닝 코드에서 여전히 사용중

6. Asterisk

• 학습목표: 단순 곱셈, 제곱연산, 가변인자 활용 등 여러 부분에서 다양하게 사용되는 Asterisk(*) 의 사용법을 여러 예제 코드를 직접 실습하며 공부한다.

• 핵심단어: Asterisk

1) Asterisk

-- 흔이 알고 있는 * 를 의미하며, '단순곱셈' '제곱연산' '가변인자활용' 등 다양하게 사용됨

def asterisk_test(a, *args):
    print(a, args)
    print(type(args))

asterisk_test(1, 2, 3, 4, 5, 6)
##    1 (2, 3, 4, 5, 6)
## <class 'tuple'>

def asterisk_test(a, **kargs):
    print(a, kargs)
    print(type(kargs))

asterisk_test(1, b=2, c=3, d=4, e=5, f=6)
## 1 {'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6}
## <class 'dict'>

2) Asterisk - unpacking a container

• tuple, dict 등 자료형에 들어가 있는 값을 unpacking
• 함수의 입력값, zip 등에 유용하게 사용 가능

  def asterisk_test(a, *args):
    print(a, args)
    print(type(args))
  asterisk_test(1, *(2, 3, 4, 5, 6))
  ## 1 (2, 3, 4, 5, 6)    /    <class 'tuple'>
  

def asterisk_test(a, args): print(a, *args) print(type(args)) asterisk_test(1, (2, 3, 4, 5, 6))

1 2 3 4 5 6 / <class 'tuple'>

```python
def asterisk_test(a, *args):
    print(a, args[0])
    print(type(args))
asterisk_test(1, (2, 3, 4, 5, 6))
## 1 (2, 3, 4, 5, 6)    /    <class 'tuple'>

def asterisk_test(a, *args):
    print(a, args)
    print(type(args))
asterisk_test(1, (2, 3, 4, 5, 6))
## 1 ((2, 3, 4, 5, 6), )    /    <class 'tuple'>

• 예시

  a, b, c = ([1, 2], [3, 4], [5, 6])
  ## a is [1, 2] / b is [3, 4] / c is [5, 6]
  

data = ([1, 2], [3, 4], [5, 6]) print(*data)

[1, 2] [3, 4] [5, 6]

def asterisk_test(a, b, c, d): print(a, b, c, d) data = {"b": 1, "c": 2, "d": 3} asterisk_test(10, **data)

asterisk_test(10, **data)

for data in zip(*([1, 2], [3, 4], [5, 6])): ## [1, 2] [3, 4] [5, 6] print(data)

(1, 3, 5)

(2, 4, 6)

</br>

---


# 7. Data Structure - Collections
> - **학습목표**: tuple, dict 에 대한 확장 데이터 구조를 제공하는 Collections 안에 포함된 모듈을 이용하여 Data Structure 의 기본 개념을 이해하고 사용하는 방법을 알아본다.
- **핵심단어**
\- Collections</br>\- Data Structure</br>\- deque</br>\- Counter</br>\- orderdDict</br>\- defaultdict</br>\- namedtuple

## 1) Collections
- List, Tuple Dict 에 대한 Python Built-in 확장 자료 구조 (모듈)
- 편의성, 실행 효율 등을 사용자에게 제공함
- 아래의 모듈이 존재함
```python
from collections import deque
from collections import Counter
from collections import OrderedDict
from collections import defaultdict
from collections import namedtuple

2) deque

• Stack 과 Queue 를 지원하는 모듈
• List 에 비해 효율적인 자료 저장 방식을 지원함

  from collections import deque
  

deque_list = deque() for i in range(5): deque_list.append(i) print(deque_list) ## [0, 1, 2, 3, 4]

deque_list.appendleft(10) print(deque_list) ## [10, 0, 1, 2, 3, 4]

- rotate, reverse 등 Linked List 의 특성을 지원함
- 기존 list 형태의 함수를 모두 지원함
```python
deque_list.rotate(2); print(deque_list)

deque_list.rotate(2); print(deque_list)

deque_list.extend([5, 6, 7]); print(deque_list)

deque_list.extendleft([5, 6, 7]); print(deque_list)

print(deque_list)
print(deque(reversed(deque_list)))

• deque 는 기본 list 보다 효율적인 자료구조를 제공
• 효율적 메모리 구조로 처리 속도 향상

  ### deque
  from collections import deque
  import time
  

start_time = time.clock() deque_list = deque()

Stack

for i in range(10000): for i in range(10000): deque_list.append(i) deque_list.pop() print(time.clock() - start_time, 'seconds')

general list

import time start_time = time.clock() just_list = [] for i in range(10000): for i in range(10000): just_list.append(i) just_list.pop() print(time.clock() - start_time, 'seconds')

## 3) OrderedDict

### (1) OrderdDict
- Dict 와 달리, 데이터를 입력한 순서대로 dict 를 반환함
```python
d = {}
d['x'] = 100; d['y'] = 200; d['z'] = 300; d['l'] = 500

for k, v in d.items():
    print(k, v)

## l 500  /  x 100  /  y 200  /  z 300

from collections import OrderedDict

d = OrderedDict()
d['x'] = 100; d['y'] = 200; d['z'] = 300; d['l'] = 500

for k, v in d.items():
    print(k, v)

## x 100  /  y 200  /  z 300  /  l 500

• Dict type 의 값을, value 또는 key 값으로 정렬할 때 사용 가능

  for k, v in OrderedDict(sorted(d.items(), key=lambda t: t[0])).items():
    print(k,v)
  

l 500 / x 100 / y 200 / z 300

```python
for k, v in OrderedDict(sorted(d.items(), key=lambda t: t[1])).items():
    print(k,v)

## x 100  /  y 200  /  z 300  /  l 500

(2) defaultdict

-- Dict type 의 값에 기본 값을 지정, 신규 값 생성 시 사용하는 방법

d = dict()
print(d["first"])    ## KeyError

from collections import defaultdict
d = defaultdict(object)    # Default dictionary 를 생성
d = defaultdict(lambda: 0)    # Default 값을 0으로 설정함
print(d["first"])    ## 0

예시

from collections import OrderdDict
from collections import defaultdict

word_count = defaultdict(object)    # Default dictionary 를 생성
word_count = defaultdict(lambda: 0)    # Default 값을 0으로 설정함

for word in text:
    word_count[word] += 1
for i, v in OrderedDict(sorted(word_count.items(), key=lambda t: t[1],
                                reverse=Treu)).items():
    print(i, v)

## a 12  /  to 10  /  and 9  /  the 0  /  press 8  /  release 8   /  that 7

4) Counter

(1) counter

-Sequence type 의 data element 들의 갯수를 dict 형태로 반환

from collections import Counter

c = Counter()    # a new, empty counter
c = Counter('gallahad')    # a new counter from an iterable

print(c)    ## Counter({'a': 3, 'l': 2, 'g': 1, 'd': 1, 'h': 1})

• Dict type, keyword parameter 등도 모두 처리 가능

  c = Counter({'red': 4, 'blue': 2})    # a new counter from a mapping
  

print(c) # Counter({'red': 4, 'blue': 2}) print(list(c.elements())) # ['blue', blue', 'red', 'red', 'red', 'red']

c = Counter({cats=4, dogs=8}) # a new counter from keyword args

print(c) # Counter({'dogs': 8, 'cats': 4}) print(list(c.elements())) # ['dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs','dogs','dogs', 'cats', 'cats', 'cats', 'cats']

### (2) namedtuple
<span style='color: #0000'>--</span> Tuple 형태로 Data 구조체를 저장하는 방법으로 저장되는 data 의 variable 을 사전에 지정해서 저장함
<span style='color: #bbbbbb'>_↪ C의 struct 와 비슷_</span>

```python
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(11, y=22)
print(p[0] + p[1])

x, y = p
print(x, y)
print(p.x + p.y)
print(Point(x=11, y=22))

학습 커리큘럼 📝 01. Pythonic Code 02. Python for Machine Learning (ML) 03. Data Handling 04. 선형 회귀 (Linear Regreesion) 05. 로지스틱 회귀 (Logistic Regreesion) 06. Classification

수강신청 하러가기

👉 리스트 ✨

👀 코드 보러가기 (colab)

Q1. 베스킨라빈스31 게임

Q2. 답안 채점

Q3. Up & Down 게임

Q4. D-Day 계산기 프로그램

조건

1. 입력한 날짜를 하루로 포함 2. 연도는 구분하지 않으며, 윤년을 고려하지 않고 2월은 항상 28일로 가정

✨ 소감 ✨

-- Java를 다시 배우는 기분이었다. Python 만 실컷하다가 오랜만에 각잡힌 언어 배우니 머릿속이 좀 복잡했지만! 그래도 Java 언어를 배운 적이 있어 많이 어렵지 않았다.

-- 그리고 do-while, string 자료형 존재X, pointer 등등 C 에서 몇몇 새로운 걸 배웠다. 특히 string 자료형은 없다는 것과 pointer 는 가장 흥미로웠다! python 처음 배울 때 주소 가르키는 거나 메모리 누수 같은 거에 대한 건 조금 알고 있었는데 pointer 를 배우니 정말 반가웠다.

-- 추가로 개인적으로 컴파일러, bit byte 등, 메모리 구조 같은 컴퓨터의 기초 지식..! 을 배울 수 있어서 정말 만족스러웠다.

• 학습목표: 포인터의 개념과 malloc 함수의 용법을 잘 이해할 수 있다.

• 핵심단어: 포인터, malloc

- 포인터를 선언한 후 malloc 사용하여 메모리를 할당한 후 값을 넣을 수 있다.

- 메모리를 할당하지 않고 값을 넣으려고 한다면 error 발생

2. 배열의 크기 조정하기

• 학습목표: 배열의 크기는 조정하는 코드를 작성할 수 있다.

• 핵심단어: malloc, realloc

- 메모리 주변에 다른 것들이 있을 경우 배열에 새 값을 추가할 수 없다.

- 메모리를 할당할 때마다 NULL이 반환되는지 확인하는 것이 좋은 방법이다.

- realloc(재할당할 것, 배열크기, sizeof(자료형)) -- ex) realloc(list, 4, sizeof(int)); -------------- ↪ int *list = malloc(3 * sizeof(int));

3. 연결리스트 도입

• 학습목표: 연결리스트의 정의를 설명할 수 있다.

• 핵심단어: 연결리스트

- . (dot) : 구조체의 속성 값을 가져올 때 -- ex) 이름.~

- * : 역참조 연산자 (using pointer)

- 메모리 덩어리 여러개를 포함한 데이터 구조를 연결리스트라고 한다.

ex) 하나의 메모리 덩어리만 사용하지 않고 두 배의 메모리를 주어 더 유연하게 만들 수 있다.

※ 컴퓨터 공학에서 node 는 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미함

• ex_wrong : node 정의되기 전이므로 사용 X

  typedef struct{
    int number;
    node *next;
  }node;    // node가 정의 되는 때

• ex_right : struct node : 구조체의 정식 명칭

  typedef struct node{
    int number;
    struct node *next;
  }node;    // node가 정의 되는 때, 구조체의 별칭

4. 연결리스트 : 코딩

• 학습목표: 연결리스트를 구현하고 사용할 수 있다.

• 핵심단어: 연결리스트

node *n = malloc(sizeof(node));

- ↪ 3번에서 정의한 node 크기만큼 메모리를 할당 받는다. - ↪ pointer n 은 node를 가르키는 주소를 담고 있다.

-----------------------------------———————————————

(*n).number = 2;

- ↪ n 은 pointer 이므로 n.number 는 잘못된 방법 - ↪ 화살표를 사용한 다른 방법 O ----- ex) n → number = 2; ----- ex) n → next = NULL;

-----------------------------------———————————————

if(n != NULL)

- ↪ n 이 NULL 인지 확인 (= 끝인지 확인)

-----------------------------------———————————————

node *tmp = list;
while (tmp -> next != NULL){
    tmp = tmp -> next
}
tmp -> next = n;

-----------------------------------———————————————

1을 앞에 끼우고 싶을 때

• wrong 새로운 node를 할당하는 코드를 사용한다. - ↪ ❗ 메모리 누수 발생

• right 1이 2를 가르키게 한 후 list가 1을 가르키게 한다.

n -> next = list;
list = n;

-----------------------------------———————————————

순서에 맞춰 중간에 값을 넣고 싶을 때

--반복문 등으로 대소 비교하고 포인터를 업데이트 하는 과정이 필요하다.

↪ 2의 next 가 3으로 가르키는 것으로 바꾸기 전에 3의 next 가 2의 next 와 같도록 한 후 2가 3을 가르키도록 해야 한다.

5. 연결리스트 : 시연

• 학습목표: 연결리스트와 배열의 장점을 설명할 수 있다.

• 핵심단어: 연결리스트, 배열

- 장점: 배열처럼 숫자를 추가하기 위해 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다는 것

- 단점: 임의 접근법 X -- ex) 이진탐색

- Big O : O(n) -insert

// Represents a node

typedef struct node{
    int number;
    struct node *next;
}
node;

int main(void){
    // List of size 0
    node *list = NULL;

    // Add number to List
    node *n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    n -> number = 1;
    n -> next = NULL;
    list = n;

    // Add number to List
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    n -> number = 2;
    n -> next = NULL;
    list -> next = n;

    // …
    // …(생략 및 반복)…
    // …

    // Print list
    for (node *tmp = list; tmp != NULL; tmp = tmp ->next){
        printf("%i\n", tmp -> number);
    }

    // Free list
    while (list != NULL) {
        node *tmp = list -> next;
        free(list)
        list = tmp;
    }
}

6. 연결리스트 : 트리

• 학습목표: 트리의 구조를 설명하고 활용하는 코드를 작성할 수 있다.

• 핵심단어: 트리, 루트

--연결리스트는 역동성을 주기 때문에 값들을 옮기느라 시간을 낭비하지 않을 수 있다. 하지만 그렇기 때문에 임의 접근을 할 수 없다.

--그렇지만 1차원적인 자료구조만 만드는 것이 아닌 수직적인 개념을 사용해서 더 흥미로운 방식으로 요소들을 배열할 수 있다.

binary search tress

typedef struct node{
    int number;
    struct node *left;
    struct node *right;
}
node;

-- ↪ ▼ 재귀 알고리즘으로 생각해 보면 ▼

bool search(node *tree){
    if(tree == NULL){
        return false;
    }
    else if (50 < tree -> number){
        return search(tree -> right);
    }
    else if (50 > tree -> number){
        return search(tree ->left);
    }
    else {
           return true;
    }
}

- Big O : O (log n)

7. 해시 테이블

• 학습목표: 해시 테이블의 원리와 구조를 설명할 수 있다.

• 핵심단어: 해시 테이블, 해시 함수

- 배열과 연결리스트를 조합한 것이다.

- 데이터 검색에 대한 연산과정을 줄일 수 있는 자료구조이다.

- key-value 형태

8. 트라이

• 학습목표: 트라이의 원리와 구조를 설명할 수 있다.

• 핵심단어: 트라이

- 어떤 자원을 절약하기 위해 다른 자원을 소비하는 패턴을 가진다.

- 많은 메모리가 들지만, 자료 구조 안에 있는 이름이나 단어를 찾는데 일정한 실행시간을 가진다.

- 트라이는 각 노드가 배열로 구성되어 있는 트리이다.

- 자식 노드 등 인덱스로 이동

- Big O : O(k) 즉 O(1)-- * k 는 상수

- 속도는 빠르지만 메모리가 많이 필요하다.

9. 스택, 큐, 딕셔너리

• 학습목표: 스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있다.

• 핵심단어: 스택, 큐, 딕셔너리

1) queus

-- FIFO (선입선출) 의 특징을 가진 자료구조--cf) LIFO (Last In First Out)

2) stacks

-- LIFO (후입선출) 의 특징을 가진 자료구조--ex) 받은 메일함

3) dictionaries

- hash table 과 비슷하다 (key-value)

- 대표적인 차이점으로 hash table은 한 객체 안에 다양한 데이터 타입을 넣을 수 있지만 dictionary 는 객체 생성 시 타입이 정해진다.

• 학습목표 - 16진법을 읽고 쓸 수 있다. - 메모리 주소에 접근하고 값을 받아오는 코드를 C로 작성할 수 있다.

• 핵심단어: 16진법, 메모리주소

- 16진법 (hexadecimal) -- : 9보다 큰 숫자를 A B C D E F 라고 쓴다. 알파벳을 사용하는 이유는 한 자리로 09 뿐만 아니라 1015까지 셀 수 있기 때문이다.

- 8bit 로 표현할 수 있는 가장 큰 숫자 : 255

- 255 의 다른 표현 방식

- RGB : 000000 ~ FFFFFF

- 0x00 : 10진법 등과의 혼동을 방지하기 위해 16진수를 사용할 때는 모든 수 앞에 0x 를 붙여서 표현해야 함 (수학적 의미X)

- " ~ 의 주소" (메모리 속의 위치) -- ↪ & --- ex) printf("%i\n", &n); -- ↪ %p : 가리키는 포인터 값을 돌려 받음 -- ex) printf("%p\n", &n);

- "그 주소로 가줘" (& 과 반대) : *** -- _ex) printf("%i\n", *\&n); ⇒ n에 담긴 값 출력_

💁‍♀️ Thinking 💡 Q. CS50 16진법으로 표현한다면? A. 0x43 0x53 0x32

2. 포인터

• 학습목표: 포인터 변수를 정의하고 사용할 수 있다.

• 핵심단어: 포인터

- 변수 주소 저장하기 -- int n = 50; -- int p = &n; --_int: 포인터가 가르키는 값의 자료형을 뜻함, \p: 포인터라는 표시_

⚠ ' * ' 없이 한다면 clang 컴파일러가 경고하므로 주소는 반드시 포인터에 저장해야 함

- 아주 정교한 자료형(가계도, 배열)을 만들 수 있음

- 수 많은 데이터를 관리하기 위해 사용하는 알고리즘의 기초가 됨

포인터의 크기 ❔ - : 최신 컴퓨터는 64bit 포인터로 사용 (= long type 의 크기)되지만, 반드시 그런 것은 아니다. (하드웨어에 따름)

3. 문자열

• 학습목표: 문자열 형태의 새로운 자료형인 string이 어떻게 정의 되었는지 설명할 수 있다.

• 핵심단어: 포인터, 문자열

- 문자열의 포인터는 시작 문자의 주소를 저장

- c에는 사실 문자열이라는 자료형은 없다고 한다. 그렇기에 char의 포인터를 활용하여 문자열이라는 자료형을 만들어야 한다.

typedef char *string;

↪ char의 주소를 가지는 string 자료형 생성

4. 문자열 비교

• 학습목표: 문자열이 저장되어 있는 방식에 근거해서 문자열을 비교하는 방법에 대해 설명할 수 있다.

• 핵심단어: 문자열

-- 문자열은 비교연산자 사용 X

5. 문자열 복사

• 학습목표: 문자열을 복사할 수 있다.

• 핵심단어: malloc

char *s = "emma";
char *t = s;
t[0] = toupper(t[0]);
>
printf("%s\n", s); // Emma
printf("%s\n", t); // Emma

s는 'emma' 에서 첫글자인 'e'의 주소가 담기는데 그 주소를 가르키는 포인터 t가 있다. 즉 두 포인터는 같은 주소를 가르키고 있으므로 t를 수정하게 되면 s도 같이 수정된다.

서로 다른 메모리 공간에 복사하려면? ↪ 메모리를 추가로 사용해서 동일한 크기의 변수를 만들고 글자를 하나씩 복사해야 함

1) malloc

메모리 할당 함수 ↪ 인자: 할당받을 메모리 크기 --- ex) malloc(strlen(s)+1);

for (int=i; n=strlen(s); i<=n; i++){
    t[i] = s[i];
}

2) strcopy

위 for 구문을 간단히 할 수 있는 함수 ex) strcopy(t, s);

6. 메모리 할당과 해제

• 학습목표: 메모리를 할당하고 해제할 수 있다.

• 핵심단어: free, valgrind

-- malloc 사용 후 free를 사용하여 메모리 할당 해제를 해주어야 함. 만약, 해제하지 않고 계속 호출한다면 느려지고 error가 발생함

-- 이를 방지하기 위해 valgrind를 사용함 --ex) $ valgrind ./-out 파일 이름-

# include <stdio.h>
>
void f(void){
    int *x = malloc(10 * sizeof(int));
    x[10] = 0;
}
>
void main(void){
    f();
    return 0;
}

① sizeof (자료형) : 자료형의 크기 -- ↪ sizeof(int) : 4byte ② malloc (10 * sizeof(int)) : 10개의 정수를 담을 수 있는 메모리 할당 -- ↪ 10 * 4byte : 40byte ③ x[10] : error -- ↪ x에는 10개의 정수 즉, index 0~9 ④ free(x) : 메모리 할당 해제를 위해 추가 필요 -- ↪ 'x[10] = 0;' 밑에 추가

7. 메모리 교환, 스택, 힙

• 학습목표: 메모리에 저장된 두 값을 교환하는 코드를 작성할 수 있다.

• 핵심단어: 스택, 힙, 포인터

- 함수에 인자를 전달할 때 그 값을 복사해서 전달

- memory in computer : 조직적으로 메모리를 사용

- 값을 복사해서 전달하므로 원하는 결과를 얻을 수 없음

- 인자를 전달할 때 값이 아닌 주소를 전달 (포인터)

8. 파일 쓰기

• 학습목표: 사용자로부터 값을 입력받아 파일에 출력하는 프로그램을 작성할 수 있다.

• 핵심단어: scanf, fopen, fprintf, fclose

9. 파일 읽기

• 학습목표: 파일을 읽고 JPEG 파일인지를 검사하는 프로그램을 작성할 수 있다.

• 핵심단어: JPEG, fread

- fopen, malloc, get_string 과 같은 함수는 error 발생시 NULL 을 return

- fread(배열, 읽을 바이트, 읽을 횟수, 읽을 파일)

- JPEG 형식에 관한 설명문서에 따르면, 카메라로 사진을 찍을 때 생기는 모든 JPEG 파일의 첫 세 바이트는 무조건 'FF', 'D8', 'FF' 로 시작한다고 함

- file I/O (파일 입출력) -- ↪ 사진 또는 비트맵이 이미지의 픽셀을 나타냄

• 학습목표: 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다.

• 핵심단어: 선형검색, 이진검색

-- 선형검색, 이진검색 : 정렬 X, 정렬 O

2. 알고리즘 표기법

• 학습목표: 알고리즘의 실행시간의 상한과 하한을 표기할 수 있다.

• 핵심단어: Big O, Big Ω

1) Big O

-- 알고리즘을 수행하는데 필요한 시간의 상한선을 의미 (최악의 경우)

2) Big Ω

-- Big O 와 상반되는 관계 (최상의 경우)

bubbble sort 의 경우, 더 이상 교환이 일어나지 않을 때 멈추는 최적화 기법이 존재한다면 소요 시간이 줄어들어 하한선이 낮아짐

3. 선형 검색

• 학습목표: 주어진 배열 또는 구조체에서 선형검색을 할 수 있다.

• 핵심단어: 선형검색, 구조체

- 자바와 동일하게 문자열을 비교할 때 비교연산자를 사용할 수 없음

- strcmp 함수: 두 문자열이 같다면 0 반환

-- ↪ 양수를 반환한다면 첫번째 문자열이 큰 경우이고 음수를 반환한다면 작은 경우 (알파벳 기준)

-- ↪ # include string.h 필요

- typedef : 새로운 타입을 정의 (나만의 자료형 만들기)

-- ⨁ struct (구조체) : 그릇처럼 여러가지 자료형을 담을 수 있음

typedef struct {
    string name;
    string number;
} person;

중괄호로 감싸져 있는 것을 캡슐화 라고 하며 마지막에 person 은 구조체의 이름(별칭) 이다.

4. 버블 정렬

• 학습목표: 버블 정렬의 원리와 실행시간을 설명하고 구현할 수 있다.

• 핵심단어: 버블정렬

1) Big O : O (n²)

-- 선형 및 이진 검색보다 상한선이 높음

(n-1) ⨯ (n-1) n² - 1n - 1n + 1 n² -2n + 1

---

⨁ 이진 검색이 선형 검색보다 상한선이 낮지만, 이진 검색을 위한 조건이 정렬인 것을 생각해보면 이진 검색이 선형 검색보다 반드시 좋다고 할 수는 없다는 것을 알 수 있다.

2) Big Ω : Ω (n²)

-- 이미 정렬된 배열이더라도 작동하므로 하한선 역시 제곱이다. (최적화 기법이 없을 때)

5. 선택정렬

• 학습목표: 선택정렬의 원리와 실행시간을 설명 및 구현할 수 있다.

• 핵심단어: 선택정렬

1) Big O : O (n²)

-- 버블정렬과는 근본적으로 다른 알고리즘이지만, 수학적 혹은 실제로는 같은 성능을 가짐

n + (n-1) + (n-2) + … + 1 n(n+1) / 2 (n²+n) / 2 n²/2 + n/2

2) Big Ω : Ω (n²)

-- 버블정렬과 같은 의미로 최선의 경우에도 시간이 똑같이 소요됨

6. 정렬 알고리즘의 실행시간

• 학습목표: 여러 정렬 및 검색 알고리즘의 실행시간을 Big O, Big Ω 로 정의할 수 있다.

• 핵심단어: Big O, Big Ω

-- 교환이 없을 때 알고리즘을 일찍 종료한다면 최선의 경우에 n-1 번의 과정이 필요 ⇒ Ω (n²) → Ω (n)

7. 재귀 (Recursion)

• 학습목표: 함수를 재귀적으로 사용하는 코드를 작성할 수 있다.

• 핵심단어: 재귀

- 눈에 보보는 혹은 가상의 물체의 구조를 그 물체 자체를 이용하여 설명하는 것

ex) 슈퍼마리오에 있는 피라미드

↪ 높이 4 피라미드에서 하나씩 줄일 때 마지막 부분에서 반환 or 종료 or 정지 등 알고리즘에 맞게 처리가 필요

- 스스로 호출하면서 기존 문제보다 더 작은 크기의 문제를 풀어감 (like 이진탐색, 분할 정복법)

8. 병합 정렬

• 학습목표: 재귀를 활용한 병합 정렬을 구현할 수 있다.

• 핵심단어: 병합정렬

1) 재귀 알고리즘의 핵심

-- 왼쪽~오른쪽, 병합(else), return (if item==one)

ex) 두 배열 중 가장 작은 값을 꺼내 다른 배열의 가장 작은 값의 다음에 두는 과정

2) 병합정렬의 실행시간: n ⨯ log n

-- 크기 8인 배열을 쪼개서 크기 1인 배열 8개로 만드는데 필요한 과정으로 약 log n, 그 후 n개의 숫자를 다시 합치는 과정을 n번 반복

⨁ Theta 표기법: 어떤 알고리즘의 상한선과 하한선이 같을 때

-- ↪ 선택정렬 및 병합정렬은 맹목적으로 같은 알고리즘을 계속 반복하므로 상한선과 하한선이 같음

• 학습목표: 컴파일링의 네 단계를 설명할 수 있다,.

• 핵심단어: 컴파일러, 어셈블링, 링킹

-- 4개의 단계가 존재: preprocessing, compiling, assembling, linking

1) preprocessing

-- clang 혹은 make 즉 명령어를 사용하여 프로그램을 실행하면 해당 파일의 실제 코드로 대체

-- ex) # include stdio.h => string get_string(string prompt);

2) compiling

• 소스코드 → 머신코드

• 전처리가 된 코드가 clang 과 같은 컴파일러에 의해 어셈블리 코드로 바뀐다.

3) assembling

-- 어셈블리 코드가 생기면 그걸 실제 0과 1로 이루어진 머신코드로 바꿔야 하는데, 이걸 clang 이 수행하는 어셈블링이라고 하는 것이다.

4) linking

-- 위 세단계를 거친 후 모든 0과 1들을 하나의 큰 파일로 합치는 것

-- 프로그램은 여러 다른 파일과 연관되어 있으므로 그 파일들을 clang 이 컴파일 해야 한다. 이를 위해 clang 을 여러번 실행해야 한다면 시간 소요가 늘어나겠지만 컴퓨터가 자동으로 해주므로 괜찮다.

2. 디버깅

• 학습목표: 디버깅 하는 여러방법을 설명할 수 있다.

• 핵심단어: 디버깅, help50, debug50

-- 문법 오류 및 논리 오류 : help, debugging

3. 코드의 디자인

• 학습목표: 코드의 정확성과 디자인을 관리하는 방법을 설명할 수 있다.

• 핵심단어: check50, style50, 고무오리

-- 가독성이 좋아야 하는 이유 : 유지보수 및 협업시 큰 도움이 됨

4. 배열 (1)

• 학습목표: 배열을 정의하고 사용하는 방법을 설명할 수 있다.

• 핵심단어: 배열

- 모두 같은 자료형의 값들로 구성되어 있으며 길이를 선언해줘야 함

- c에서는 char를 사용할 때 쌍따옴표가 아닌 따옴표 !

- 형변환 변수 앞에 괄호 사용 ex) (int) a

- 2진법 ASCII 등 컴퓨터에 저장될 때 어떤식으로 저장되는지 대응 관계를 항상 인지하기

5. 배열 (2)

• 학습목표: 배열을 정의하고 사용하는 방법을 설명할 수 있다.

• 핵심단어: 배열, 전역변수

- 전역변수는 대문자로, 선언할 때 const

- main 이 위에 있는 것이 좋음

- C 에서는 정수를 정수로 나누면 정수가 나옴

- 강력한 자료형으로 반환 ex) int/float => float

6. 문자열과 배열

• 학습목표: 문자열이 C에서 정의되는 방식과 메모리에 저장되는 방식을 설명할 수 있다.

• 핵심단어: 문자, 문자열

- string 은 정해진 크기를 가질 수 없음

- 문자열이 언제 끝나는지를 알려주는 정보가 필요

-- ↪ null 문자 (\0) : 8개의 bit 가 모두 0인 상태

- %s 에 변수명을 넣으면 printf가 일종의 루프를 만들어 첫번째 글자부터 반복해서 널문자 전까지 출력

7. 문자열의 활용

• 학습목표: 문자열을 탐색하고 일부 문자를 수정하는 코드를 구현할 수 있다.

• 핵심단어: strlen, toupper

- # include <string.h> : 문자열과 관련된 다양한 함수들이 있는 라이브러리

- # include <ctype.h> : toupper 함수가 있는 라이브러리

⨁ 프로그래밍은 결국 추상화를 이용해서 복잡한 기계어를 간단하게 처리하는 것

8. 명령행 인자

• 학습목표: 명령형 인자를 받는 프로그램을 C로 작성할 수 있다.

• 핵심단어: 명령행 인자, argv, argc

- 실행하고자 하는 프로그램 뒤에 적는다. ex) $ clang -o hello hello.c

- 정보를 보호하기 위한 암호화

⨁ 송신자와 수신자가 사전에 어떤 키를 사용해서 문자를 암호화 할지 정해야 한다.

---

ex)

위와 같은 구조에서 key = 1, plaintext = I LOVE YOU 라고 가정할 때, 컴파일 과정에서 plaintext 는 ASCII 코드를 사용하여 변환 후 각 수에 1을 더해주어 ciphertext 로 ouput 한다면 다른 사람들은 원래 값을 알 수 없다.

• 학습목표: C로 "hello, word" 를 출력하는 프로그램을 만들 수 있다.

• 핵심단어: stdio.h, clang, 컴파일러

- #include <stdio.h> 하지 않으면 printf() 함수 사용 X

- 컴파일러

- $ clang: 코드를 컴파일 해줌

• 실행시 a.out 파일 생성 (머신코드)
• ./a.out : 현재 디렉토리에 있는 a.out 실행

- 파일 내용 수정 후 ./a.out 실행시 변경 전 내용 출력 (컴파일 하지 않았기 때문)

- $ clang 뒤에는 파일명만 적을 수 있는 것이 아닌 명령행 인자를 추가할 수 있음

• ex) $ clang -o hello hello.c
• $ ls → a.out* hello* hello.c '*' 표시는 머신코드라는 뜻(≒실행가능) ⨁ 이 외: rm, mkdir, rmdir 등

2. 문자열

• 학습목표: C로 문자열을 가진 변수를 선언 및 출력하는 프로그램을 만들 수 있다.

• 핵심단어: 형식지정자, string, make

1) 형식지정자

• %s, %i, %d 등 형태

⨁ #include 하는 과정 : clang 을 통해 컴파일, 이는 컴퓨터가 include 하려는 파일을 사용자의 소스코드에 추가하고 명령어로 연결을 시켜 두 코드가 한 프로그램으로 실행될 수 있도록 함 ex) $ clang -o string string.c -lcs50

2) make

바로 위 설명에서 clang 을 사용하여 컴파일하는 과정보다 보다 간단하다.

ex) $ make string make 뒤에는 프로그램 이름 인자만 입력해야 함

위 예시를 실행하게 된다면 string.c 파일을 찾고 string 이름으로 머신코드를 output 한다(string*).

3. 조건문과 루프

• 학습목표: 조건문과 루프를 C로 작성할 수 있다.

• 핵심단어: int, if, while, for

- ⊜: 할당 연산자

- type 선언은 한번만

- 구문설탕: 새로운 기능 추가X, 기존 기능을 더욱 보기 좋고 간결하게 활용할 수 있도록 해준다는 뜻

- c에서는 true 첫글자 소문자 가능 (Python은 True)

- for 구문: 인자 세개 (Java와 동일, 형태: (변수선언, boolean, 변수증감))

4. 자료형, 형식지정자, 연산자

• 학습목표 - 다양한 데이터 타입과 형식지정자를 나타내는 방법을 학습한다. - 다양한 연산자를 이용하여 조건문을 표현하는 방법을 학습한다.

• 핵심단어: char, long, float, double, %, &&, ||

- cd (경로 설정), pwd (경로 확인)

5. 사용자 정의 함수, 중첩루프

• 학습목표: 사용자 정의 함수와 중첩루프를 작성할 수 있다.

• 핵심단어: 사용자 정의 함수, 중첩루프

- void (return 값 X) 선언하는 등 생성

- 위에서 아래로 왼쪽에서 오른쪽으로 순차적으로 작동하기 때문에 main을 사용자 정의 함수보다 아래에 둔다면 error 발생. -- ⨁ main 위에 선언한다면 가능 ex) void cough(void);

- do-while 루프: boolean → 수행

6. 하드웨어의 한계

• 학습목표: 메모리 용량이 프로그램의 구동에 미치는 영향을 설명할 수 있다.

• 핵심단어: 메모리, 오버플로우

1) RAM

• 모든 프로그램이 실행 중 (열려있는 동안) 저장되는 곳
• 컴퓨터가 여러 일들을 한번에 할 때 기억하기 위해 사용되는 것
• 하드웨어로 성능은 유한함

2) overflow

-- 메모리 저장공간이 유한하다면 컴퓨터는 특정 지점에서 한계에 부딪힌다. float 은 32bit 를 사용하고 double은 64bit 를 사용하므로 보다 정확한 계산이 가능하지만 이 또한 완벽하지 않다. 왜냐하면 결국 저장할 수 있는 정보는 유한하기 때문이다.

-- 따라서 컴퓨터는 계산할 수 있는 값들 중 원하는 값과 가장 가까운 값을 저장한다. ex) 1 나누기 10을 한다면 0.1(1/10)에 가까운 값을 저장

-- overflow를 예시와 함께 설명한다면, 10진법인 세자리 숫자가 있을 때 1을 더하다보면 999가 되고 일 때 1을 더해주면 1,000 이ehlsek. 하지만 세자리 까지의 숫자만 저장할 수 있는 메모리 공간이라면 000만 남게 된다. 2진법도 같음

-- 이 설명은 Y2K 와 보잉 787 사례를 안다면 더 쉽게 이해할 수 있다.

학습 커리큘럼 📝 01. 컴퓨팅사고 (Computational Thinking) 02. C언어 03. 배열 (Arrays) 04. 알고리즘 (Algorithms) 05. 메모리 (Memory) 06. 자료구조 (Data structures)

수강신청 하러가기

• 학습목표: CS 정의 및 컴퓨터가 정보를 표현하는 방법에 대해 설명할 수 있다.

• 핵심단어: 컴퓨터과학, 2진법, 비트, 바이트

- 10진법은 10의 거듭제곱 ex. 123 = 1100 + 2\10 + 3*1

- 2진법은 2의 거듭제곱 ex. 010 = 04 + 1\2 + 0*1

📌 2진법을 위해서 더 많은 0과 1을 필요로 하는 데 이것을 비트(bit) 라고 표현한다. 컴퓨터는 수많은 bit를 활용하여 정보를 표현하고 bit 보다 더 많은 0과 1을 필요로 한다면 byte (바이트)를 사용한다.
byte = 8bit, 즉 8개의 1과 0을 의미한다.

---

🎓 50을 이진법으로 한다면 어떤 스위치를 켜야 할까 ? 🔑 32, 16, 2 (00110010)

🎓 13을 이진법으로 한다면 어떤 스위치를 켜야 할까 ? 🔑 8, 4, 1 (00001101)

※ 컴퓨터 안에 트랜지스터(컴퓨터 안에 있는 아주 작은 스위치) 를 물리적으로 이용해서 정보를 표현하고 값을 저장. + 컴퓨터는 수백만 수십억개의 트랜지스터를 가지고 있음

---

• 다양한 데이터 표현하기

단위	정의	저장공간 크기
bit	0 또는 1	예 / 아니오, true / false
byte	8bit	영어 알파벳 1개
KB	1,000 byte	몇 개의 문단
MB	1,000 KB	1분 길이의 MP3 노래
GB	1,000 MB	30분 길이의 HD 영화
TB	1,000 GB	'심슨네 가족' 열 여섯 시즌

2) 정보의 표현

• 학습목표: 컴퓨터가 문자, 사진, 영상, 음악 등 다양한 정보를 처리하는 방식을 설명할 수 있다.

• 핵심단어: ASCII, 유니코드, RGB

(1) ASCII

정보 교환을 위한 미국 표준 코드

ex. H I ! : 72 73 33

(2) 유니코드

ASCII 의 상위집합과 같다고 보면 된다. 차이점으로 8, 16, 24 혹은 32 bit 까지도 사용된다는 것이 있다.

ex. 이모티콘 : 😂 위 이모티콘의 10진법은 '128,514' 이라고 한다. 이모티콘은사진 그 자체로 수많은 작은 점들로 이루어져 있다.

(3) RGB

수 많은 점들을 표현한 것으로 그래픽을 사용하는 프로그램에서는 '72 73 33'을 숫자로 해석하여 'HI!'로 표현하는 대신에 빨강(R) 초록(G) 파랑(B)의 양으로 받아들인다.
즉, 어떤 방법을 사용해서 정보를 나타내든 결국 0과 1들로 표현된다.

🎓 CS 50을 이진법으로 표현한다면 ? 🔑 67, 83, 50 (01000011, 01010011, 00110010)

3) 알고리즘

• 학습목표 - 우리가 일상생활에서 하는 일들을 컴퓨터가 이해할 수 있는 알고리즘으로 표현할 수 있다. - 효율적인 알고리즘에 대해 설명할 수 있다.

• 핵심단어: 알고리즘, 의사코드

🔑 전화번호부에서 특정 인물을 찾기 위한 알고리즘을 구현하려고 했을 때, 아래의 3가지 알고리즘의 성능을 확인해 보자.

(a) 한장씩 차례대로 찾는다. (b) 두장씩 차례대로 찾는다. (c) 반으로 나눴을 때 찾고자 하는 것이 없는 범위의 것을 버리고 찾을 때까지 이를 반복한다.

전화번호부가 총 1,024장이라고 가정한다. a와 b를 비교해보면 시간 소요의 차이가 확연하다. 이 결과에 따르면 a보다 b가 더 좋은 알고리즘이라고 할 수 있다.
하지만, b 역시 문제의 크기가 클수록 시간소요가 증가한다는 점은 해결하지 못했다.
c를 보면 문제 양에 상관이 거의 없게 시간 소요 변동이 없다. 이는 효율성 측면에서 아주 큰 차이다.

4) 스크래치: 기초

5) 스크래치: 심화

위 두 과정은 프로그래밍 기초 (블록 만드는 것)에 대한 것으로 포스팅은 생략 한다.

📕 학습 커리큘럼 : 1주차 : 파이썬 소개, 변수 표현식 및 코드 2주차 : 조건부 실행, 함수 3주차 : 루프, 반복문 4주차 : 문자열과 파일 5주차 : 리스트 6주차 : 딕셔너리와 튜플

모집 페이지 보기

본 스터디는 현재 모집 기간이 끝났으며 8월 24일 목요일에 종료될 예정입니다.

네이버 부스트코스에는 다양한 스터디 및 무료강의가 있으니 참고 부탁드려요 :)

👉 문자열과 파일 ✨

👀 코드 보러가기 (colab)

➕ 추가 (230811)

4주차 우수미션 팀에 선정 됐다! 🎉 4번 문제의 코드는 라이브 중 소개도 되었다. (본인이 작성한 코드 ✌) 뿌-듯 (❁´◡`❁)

Q1. 숫자 3자리 표기

Q2. 특정 단어 개수 세기

조건

: 변수에 담긴 글을 함수에 넣어주면 txt 파일로 저장

Q3. 방명록

조건

1. 010 으로 시작함 2. 번호가 - 로 구분이 되어 있음 3. - 를 포함하여 길이가 13임 4. txt 파일로 저장

Q4. 주민등록번호

조건

1. 양식: 000000-0000000 (총 길이 14자리) 2. 뒷자리 시작번호 1,3: 남자 / 2, 4: 여자 3. 뒷자리 3, 4는 only 2000년생 이후 출생자 4. 조건 불충족시, "잘못된 번호입니다"라는 메세지 출력

👉 루프와 반복문 ✨

👀 코드 보러가기 (colab)

Q1. 구구단

조건

1. 홀 수 번째만 출력 2. 값이 50이하인 것만 출력

Q2. 업그레이드 가위 바위 보

조건 1. 게임 진행 횟수 입력 받기 2. 0, 1, 2, "가위", "바위", "보" 이외에 입력시 재입력 받기 3. 게임종료 후 나와 컴퓨터의 총 전적 출력하기

Q3. 숫자 사이 짝수만 출력 (중앙값도)

단, 중앙값이 짝수가 아닐 경우에는 중앙값은 출력을 하지 않고 짝수인 수만 출력

Q4. 특정 범위 내 소수 찾기

👉 조건문 실행과 함수 ✨

👀 코드 보러가기 (colab)

Q1. 학점 변환기

조건

Q2. 연봉 계산

조건

Q3. 버스요금 계산기

Q4. 가위 바위 보

조건

1. 0, 1 ,2 혹은 "가위", "바위", "보" (총 6가지 방법) 2. 누가 무엇을 냈고, 누가 승리 했는지 출력

👉 변수 표현식 및 코드 ✨

👀 코드 보러가기 (colab)

Q3. Error Message 이해

: Error를 발생 코드 및 Debugging 코드 만들기

Q4. 법 개정 전 한국 나이를 미국 나이로 변환

　또한, 데이터 분석시 종속변수와 유의미하다고 보이지 않던 변수들이 예측 및 평가시 영향을 미치는 경우도 있었고 그 반대의 경우도 있었습니다. 이는 독립변수들 간의 영향을 미치는 경우 등 다양한 요인으로 인한 것으로 분석가의 재량이 필요한 부분이 많았습니다.

　따라서 모델을 만들 때에는 각 변수들 간의 관계 및 해당 데이터에 대한 이해도가 필요하며 분석 목적을 잊어서는 안됩니다.

　종속 변수가 이항적인 경우(두 개의 범주를 가지는 경우)에 사용되는 통계적 분석 방법으로 종속 변수와 독립 변수간의 관계를 모델링하고 독립 변수의 값에 따라 종속 변수가 속하는 범주를 예측하는 데 사용됩니다.

　분류 문제에 널리 활용되며 예측 모델의 해석이 상대적으로 용이하고 계산적으로 효율적입니다.

1. 데이터 호출

　- 사용 데이터: 내장 데이터 mtcars
　- 분석 목적: mpg(연비)와 am(변속기종류)가 vs(엔진)에 미치는 영향 확인 및 평가

# 데이터셋 로드
data(mtcars)
help(mtcars)

　　▼ Console of help(mtcars) ▼

Format A data frame with 32 observations on 11 (numeric) variables. # 32개의 관측치와 11개의 변수로 구성 [, 1] mpg Miles/(US) gallon # 연비 [, 2] cyl Number of cylinders [, 3] disp Displacement (cu.in.) [, 4] hp Gross horsepower [, 5] drat Rear axle ratio [, 6] wt Weight (1000 lbs) [, 7] qsec 1/4 mile time [, 8] vs Engine (0 = V-shaped, 1 = straight) # 0: V-Shaped 엔진, 1: straight 엔진 [, 9] am Transmission (0 = automatic, 1 = manual) # 0: 오토, 1: 스틱 [,10] gear Number of forward gears [,11] carb Number of carburetors

2. 로지스틱 회귀분석

1) 데이터 분리

　모델 생성 전 훈련 및 검증, 테스트용으로 데이터를 분리해 주어야 합니다. 일반적으로 훈련 및 테스트 데이터를 7:3 or 8:2로 분리한 후 훈련 데이터를 훈련 및 검증 데이터로 나눕니다(7:3 or 8:2). 하지만 앞서 살펴본 바와 같이 사용할 데이터의 관측치는 32개로 굉장히 적은 양이고 분석 목적을 생각했을 때 2개의 독립변수만 사용할 예정이므로 검증 데이터 없이 훈련 및 테스트 데이터를 8:2로 나누어 줍니다.

# 데이터 분할
trIdx <- sample(1:nrow(mtcars), 0.8 * nrow(mtcars))
mtcTr <- mtcars[trIdx, ]    # 25
mtcTe <- mtcars[-trIdx, ]    # 7

2) 모델 생성

　- glm(): R에서 일반화 선형 모델을 생성하기 위해 사용되는 함수로 선형 회귀 뿐만 아니라 옵션을 조정하여 로지스틱 회귀 등 다양한 종류의 선형 모델을 만듦

# 로지스틱 회귀분석을 하기 위해 family 옵션을 binomial로 설정
glmModel <- glm(vs ~ mpg + am, data = mtcTr, family = binomial)

# 결과 요약
summary(glmModel)

　　▼ Console of summary(mtcTr) ▼

Call: glm(formula = vs ~ mpg + am, family = binomial, data = mtcars)

Deviance Residuals:

　Min　　　1Q　　　Median　　　3Q　　　Max
-2.0585 　-0.5189　　-0.2513　　0.3307　　1.6887

Coefficients:

　　　　　　Estimate　　Std. Error　　z value　　Pr(>|z|)
(Intercept)　 -12.5235　　　5.1727　　-2.421　　 0.0155 * mpg　　　　 0.6830　　　 0.2927　　 2.333　　 0.0196 * am　　　　　-3.2436　　　1.8636　　-1.740　　 0.0818 . --- Signif. codes:　0 ‘***’　0.001　‘**’　0.01　‘*’ 0.05　‘.’ 0.1　‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

　　Null deviance: 33.651 on 24 degrees of freedom Residual deviance: 18.333 on 22 degrees of freedom AIC: 24.333

Number of Fisher Scoring iterations: 6

※ 참고 ※ 　로지스틱 회귀분석에서의 Estimate는 로즈 오그 라는 것을 나타냅니다. 이는 종속 변수의 변화를 설명하기 위한 것으로, 해석하기 위해서는 지수함수인 오즈비를 계산해주어야 합니다. 오즈비는 독립변수의 값이 1단위 증가할 때의 확률를 의미합니다.

　위 기술 통계랑을 예로 들자면, am(변속기종류)의 로즈 오그는 -3.2436으로 am이 1단위가 증가할 때마다 로즈 오그는 3.2436만큼 감소한다는 뜻입니다. 이를 지수함수로 변환하여 해석하면, am이 1단위 증가할 때 vs(엔진)이 0이 될 확률이 1이 될 확률 보다 약 0.038배 낮다고 할 수 있습니다. 즉, am이 1일 때 vs가 1일 확률이 높다는 것입니다.

* 로그 오즈(Log Odds): 어떤 사건이 발생할 확률과 발생하지 않을 확률의 비율을 로그로 취한 값
* 로그 오즈비(Log Odds Ratio): 로그 오즈의 차이를 나타내는 개념, 지수함수 변환 필요(exp 함수사용)

2) 기술통계량 해석

　mpg(연비) 단위가 증가하게 되면 vs(엔진)이 0이 될 확률이 증가하고, am(변속기종류) 단위가 증가하게 되면 vs(엔진)이 0이 될 확률이 감소합니다.

　또한, Null deviance(귀무편차)의 값보다 Residual deviance(잔차편차)값이 상대적으로 낮고 알고리즘 반복회수가 6으로 모델이 빠른 속도로 최적화 되었으며 절편에서의 p-value가 유의수준보다 낮은 것 등을 살펴보았을 때 대체적으로 유의미한 모델이라고 판단 됩니다.

　비록 각 독립변수에 대한 p-value가 유의수준 보다 높지만, 분석 목적에 필요한 독립변수이므로 일단 제외하지 않고 진행 합니다.

※ 참고 ※

- Null deviance(귀무편차): 모든 독립변수를 사용하지 않고 종속변수의 평균값만 사용하여 예측하는 모델로 종속 변수의 변동성을 나타내며 낮을 수록 좋음
- Residual deviance(잔차편차): 모델이 예측한 값과 실제 관측값 간의 차이의 편차를 나타내는 것으로 모델이 데이터에 적합한 정도를 뜻하며 낮을 수록 좋음
=> 잔차편차의 값이 귀무편차에 비해 상대적으로 작다면 모델의 성능이 높다는 의미로 로지스틱 회귀분석에서 모델의 적합도를 평가하기 위해 사용되는 통계량임

- Number of Fisher Scoring iterations: Fisher Scoring 알고리즘이 반복적인 과정을 통해 모델의 매개변수를 조정하여 모델의 우도를 최대화 하는 값을 찾는 과정의 반복 횟수를 나타냄
　└ 일반적으로 반복 횟수가 많다면 모델은 더욱 정교하게 적합되지만 수렴하는 데 시간이 오래 걸릴 수 있는데 이는 모델 적합의 속도와 정확도 사이의 절충점을 나타내는 것
　└ Fisher Scoring: 로지스틱 회귀모델의 최적화 알고리즘 중 하나로 likelihood(최대우도) 추정을 수행
　└ likelihood 추정: 모델의 매개변수(회귀계수)를 데이터에 가장 잘 적합한 값을 찾는 과정

- Dispersion parameter for binomial family taken to be 1: 로지스틱 회귀분석에서 사용된 확률 분포인 'binomial'에서의 분산 파라미터(dispersion parameter)를 1로 설정했다는 것을 의미하는 것으로 이는 로지스틱 회귀분석에서는 일반적임

3. 예측 및 평가

1) 예측하기

　모델 생성 전 분리 해주었던 테스트 데이터를 사용하여 예측합니다. 종속변수가 0 아니면 1 이라는 이항적인 성격이므로, 0.5를 기준으로 작으면 0, 아니면 1 로 예측 값을 설정해줍니다.

# 모델을 적용하여 예측 수행
moPred <- ifelse(predict(glmModel, newdata = mtcTe, type = "response") >= 0.5, 1, 0)

# 예측 결과 확인
moRes <- data.frame(mpg = mtcTe$mpg, am = mtcTe$am, predVs = moPred, trueVs = mtcTe$vs)

　　▼ Console ▼

> 7개의 테스트 데이터 중 1개의 예측이 틀렸습니다.

2) 변수 간 관계 확인

　기술 통계 분석 시 Estimate의 값을 통해 예측 했던 변수 간의 관계를 시각화 하여 한번에 파악할 수 있게 시각화 하겠습니다.

# mpg와 vs의 관계 & 예측값과 관측값
ggplot(moRes, aes(x = mpg)) +
  geom_point(aes(y = predVs, color = "Predicted"), size = 3) +
  geom_point(aes(y = trueVs, color = "Observed"), size = 3) +
  geom_line(aes(y = predVs, color = "Predicted"), size = 1) +
  geom_line(aes(y = trueVs, color = "Observed"), size = 1, linetype = "dashed") +
  labs(x = "mpg", y = "vs", color = "Value") +
  scale_color_manual(values = c("Predicted" = "blue", "Observed" = "red")) +
  theme_minimal() + 
  coord_flip()

# am과 vs의 관계 & 예측값과 관측값 는 mpg의 것과 동일하므로 생략합니다.

(1) 독립변수 mpg & 종속변수 vs

　예측값된 값들이 표현된 파란색과 관측값들이 표현된 빨간색이 유사한 경향을 보이고 있습니다. 이는 모델이 mpg 값을 잘 활용하여 vs 값을 예측하고 있다는 뜻입니다. 또한 mpg가 증가할 수록 vs가 0에서 1로 바뀌는 것을 알 수 있습니다.

　두 변수의 관계를 통해 알 수 있는 사실은 연비(mpg)가 높으면 straight Engine(vs 값 1)일 것이고, 연비가 낮으면 V-shaped Engine(vs 값 0)이라는 것 입니다.

(2) 독립변수 am & 종속변수 vs

① 테스트 데이터

　예측값된 값들이 표현된 파란색과 관측값들이 표현된 빨간색이 유사한 경향을 보이고 있습니다. 이는 모델이 am 값을 잘 활용하여 vs 값을 예측하고 있다는 뜻입니다. 하지만 am의 값이 0일 때 vs 값이 0일 때도 있는 것을 보았을 때, am이 vs한테 미치는 영향이 미미한 것으로 보입니다.

　추가로 전체 데이터를 대상으로 하여 동일한 과정을 통해 그래프를 만들겠습니다.

② 전체 데이터

　얼핏보면 ①의 결과와 반대인 것처럼 보이지만 비슷한 경향을 띄고 있습니다. 자세히 살펴보면 관측 값(빨간색)들의 경우 am이 0일 때 vs가 0과 1 모두 존재하고(am 1일 때도 마찬가지) 예측 값(파란색)들의 경우 음의 선형 관계를 보여주는 데 이는 모델이 am과 vs의 관계를 보는 방식을 알려줍니다.

　예측 값과 관측 값은 서로 일치하는 경향을 보이지만, vs에게 am이 미치는 영향은 작거나 없다는 것을 알 수 있습니다.

3) 모델 평가

　이진 분류 모델의 성능을 평가하고 비교하는 데 주로 사용하는 ROC 그래프를 사용하여 시각화 합니다. ROC 그래프는 모델의 성능을 종합적으로 평가하는 데 사용되며 AUC(Area Under the Curve)를 계산하여 수치로 평가할 수 있습니다.

　AUC는 ROC 곡선 아래의 면적을 계산한 값으로 0부터 1까지의 범위를 가지며, 0.5보다 크고 1에 가까워질수록 모델의 성능이 좋다고 판단할 수 있습니다.
　└ AUC < 0.5: 무작위 예측보다 성능이 나쁨
　└ AUC 0.5에 가까움: 모델의 성능이 무작위 수준에 가까움
　└ AUC 1에 가까움: 모델의 성능이 좋음

　※ 참고 ※

- ROC 곡선은 모델의 예측 결과를 다양한 값으로 조정하면서 진짜 양성 비율(TPR)과 가짜 양성 비율(FPR) 사이의 관계를 표현
　⇒ TPR(True Positive Rate): 실제 양성 중 정확하게 예측한 비율, 예측 양성 → 실제 양성 (called 민감도 or 재현율)
　⇒ 민감도(Sensitivity): 예측 양성 → 실제 양성 비율
　⇒ FPR(False Positive Rate): 실제 음성 중 잘못 예측한 비율 (가짜 양성 비율), 예측 양성 → 실제 음성
　⇒ 특이도(Specificity): 예측 음성 → 실제 음성 비율, 1-특이도=FPR

library(pROC)

# ROC 그래프를 위해 mtcRes 타입 변환
mtcRoc <- roc(mtcRes$observed, mtcRes$predictions)

# ROC 그래프
plot(mtcRoc, main = "ROC Curve", xlab = "FPR", ylab = "TPR", xlim = c(1, 0), ylim = c(0, 1))

# 대각선 기준선 추가
abline(a = 0, b = 1, lty = 2)

# AUC 계산
legend("bottomright", paste("AUC =", round(auc(mtcRoc), 2)))

　좌측상단으로 갈수록 성능이 우수한 모델임을 나타내는데, 해당 그래프를 보았을 때 ROC 곡선이 좌측 상단에 위치해 있으며, AUC 또한 0.83으로 적은 데이터 대비 높은 성능을 보여주고 있습니다.

4. 해석

　모델의 기술 통계량 분석했을 때 각 독립변수의 p-value 값이 유의수준보다 높아 높은 성능을 기대하기 어려웠지만 해당 독립변수들은 분석 목적에 꼭 필요한 것이었고, 모델 자체(전체)에 대한 p-value 값은 낮은 것 등 다른 요인을 고려하여 그대로 진행하였습니다.

　변수 간 관계 확인 및 모델 평가를 통해 얻은 사실은 모델 자체의 성능은 좋은 편이나, 독립변수 am(변속기 종류)는 종속변수 vs(엔진)에 유의미한 영향이 미친다고 할 수 없다는 것입니다. 이는 예측값이 mpg(연비)의 영향으로 나왔다고 할 수도 있습니다.

　하지만 본 과정에서 사용한 데이터의 크기 자체가 굉장히 작았기 때문에 이 결과를 일반화하기에는 무리가 있습니다. 따라서, 데이터의 양이 작을 때에는 결과 보단 과정에 집중하는 것이 추후 빅데이터를 다룰 때 신중하고 옳은 판단을 할 수 있습니다.