멋쟁이 사자처럼 AI 스쿨 - Snippet

김영민·2022년 12월 9일
AI스쿨snippet데이터분석가딥러닝머신러닝멋쟁이사자처럼
0

코테 전 준비사항

  • 플랫폼에 익숙
    • 사용 가능 라이브러리 미리 확인 등
    • 대부분 numpy나 pandas 같은 라이브러리 사용 금지이지만 간혹가다 제한이 없는 곳도 있습니다. numpy는 python보다 대부분의 경우 속도가 빠릅니다. 크기에 따라 다르지만 100000개 이상의 배열의 연산의 경우 50배 이상의 성능을 보입니다.
  • 언어 선택(속도 : C++, 풀이 : Python)
  • 코드 스니펫(트리, 검색, 최단경로(예를 들어 다익스트라), 직접 제작한 함수 등), Cheatsheet, A4 용지 준비
    • 코드 스니펫을 만들어둔 레파지토리 fork - 제주코딩베이스캠프
    • 시험 전 스니펫을 만들지 말고 하루 한 문제씩
    1. 유용한 라이브러리 정리! (collections, itertools(순열, 조합), functools, itertools, re, bisect, math 등) - 제주코딩베이스캠프 유튜브 채널 확인
  • 예외처리
  • 속도개선
    1. class로 구현
    2. 메서드 대신 슬라이싱 구현(슬라이싱은 C로 구현되어 있어 메서드보다 통상 8배정도 빠르다.) 다만 공간복잡도가 상승할 수 있다. (리스트.reverse(), reversed(리스트), 리스트[::-1])
    3. for문 대신 list comprehension을 사용. 더 빠르다.
    4. 재귀는 느리다. 최후의 수단

Map & Zip & lambda

  • map에 들어가는 것은 함수와 이터러블

  • 문자열을 숫자형의 합으로

    l = ['1','11','125']

[int(i) for i in l]
sum([int(i) for i in l])
    sum(map(int,l))
  • lambda 예시
    def 함수(x):
    return x ** 2

def 함수2(x):
    return x*2
list(map(함수,[1,2,3,4]))
list(map(함수,range(5)))
list(map(함수2,'abc'))

>>>> 

list(map(lambda x:x**2,[1,2,3,4]))
list(map(lambda x:x**3,range(5)))
list(map(lambda x:x*2,'abc'))
  • map과 zip의 활용
    list(map(lambda x: [x[2]-x[0],x[1]],
   zip(range(10), 
       'hello world', 
       [30,50,60,100,30,4,10,2,30]
      )
   )
)
    출력
    [[30, 'h'],
 [49, 'e'],
 [58, 'l'],
 [97, 'l'],
 [26, 'o'],
 [-1, ' '],
 [4, 'w'],
 [-5, 'o'],
 [22, 'r']]
  • 문제 1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오. (단 점들의 배열은 모두 정렬되어있다고 가정한다.) 예를들어 S = [1, 3, 4, 8, 13, 17, 20] 이 주어졌다면, 결과값은 (3, 4)가 될 것이다.
    # 만약에 빌트인 펑션을 사용해야 한다면
# .sort => 데이터 분석을 할 때에는 권고사항 X
# sorted => 데이터 분석을 할 때 권장, 알고리즘 테스트에서 자주 사용

def 함수(value):
    return [value[1]-value[0],(value[0],value[1])]

s = [1, 3, 4, 8, 13, 17, 20]
list(map(함수,zip(s,s[1:])))
sorted(list(map(함수,zip(s,s[1:]))),key=lambda x:x[0],reverse=True)[0][1]
sorted(list(map(함수,zip(s,s[1:]))),key=lambda x:x[0],reverse=True)

# reverse =True 를 하게 되면 역정렬
    최솟값 구하는 방법
    s  = [1, 3, 4, 8, 13, 17, 20]
최솟값 = float('inf')
인덱스 = 0

for i in range(len(s)-1):
    if (s[i+1] - s[i]) < 최솟값:
        최솟값 = s[i+1] - s[i]
        인덱스 = i

print(s[인덱스], s[인덱스+1])

스택과 큐

스택

  • 스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조
  • 스택은 LIFO(Last-In-First-Out, 후입선출)
  • ADT(Abstract Data Type)
    • S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
    • S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
    • S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
    • S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.

출처 : https://cocoon1787.tistory.com/691

큐

  • 스택과 반대되는 개념, 먼저 들어간 데이터가 먼저 나오는 자료 구조이다.
  • FIFO(First in First Out, 선입선출)
  • 기존에 데이터 삽입 시 offer(). 추출시 poll()을 사용한다.


출처 : https://cocoon1787.tistory.com/691

  • 스택과 큐 알고리즘 및 예시 문제 알고리즘
    # 스택
s= [10,20,30,40,50]
s.append(100) # push
s.pop() # pop

# 큐
s = [10,20,30,40,50]
s.append(100) #push
s.pop(0) #pop
    class Stack:
    def __init__(self): # 최초에 인스턴스가 생성 될 때
        self.배열 = []
        
    def push(self,data):
        self.배열.append(data)
        
    def pop(self):
        self.배열.pop()
        
    def bottom(self):
        self.배열[0]
    
    def top(self):
        self.배열[-1]
    
    def empty(self):
        self.배열 = []
    s = Stack()
s.push(10)
s.push(20)
s.push(30)
s.push(40)
s.push(50)
s.push(60)
s.push(70)
s.pop()
s.배열

>> 결과
[10, 20, 30, 40, 50, 60]

연결리스트

순서가 매겨진 항목들을 모아놓은 구조 중 하나로 각 데이터를 연결하는 포인터까지 있는 구조.

  • 알고리즘
    class Node:
    def __init__(self,data):
        print(f"{data}이 입력되었습니다.")
        self.data = data
        self.next = None
              
              
class LinkedList:
    def __init__(self):
        init = Node('init')
        self.head = init
        self.tail = init
        self.counter = 0
        
    def __len__(self):
        return self.counter
        
    def __iter__(self):
        currentNode = self.head
        currentNode = currentNode.next
        while currentNode:
            yield 1
    
    
        
    def __str__(self):
        currentNode = self.head
        currentNode = currentNode.next
        result = ''
        for i in range(self.counter):
            result += f'{currentNode.data}, '
            currentNode = currentNode.next
        return f'[{result[:-2]}]'
    
    def append(self,data):
        newNode = Node(data)
        self.tail.next = newNode
        self.tail = newNode
        self.counter += 1
        
    def insert(self, inputIndex, inputData):
        currentNode = self.head

        for i in range(inputIndex):
            currentNode = currentNode.next

        newNode = Node(inputData)
        newNode.next = currentNode.next
        currentNode.next = newNode

        self.counter += 1
    
    
    def pop(self):
        lastNodeData = self.tail.data
        currentNode = self.head
        for i in range(self.counter):
            if currentNode.next == self.tail:
                self.tail = currentNode
                break
            currentNode = currentNode.next
        self.counter -= 1
        return lastNodeData
    
    def find(self,data):
        index = -1
        currentNode = self.head
        for i in range(self.counter+1):
            if currentNode.data == data:
                return index
            index += 1
            currentNode = currentNode.next
        return -1
    l = LinkedList() # init 노드만 생성
l.append(10)
l.append(20)
l.append(30)
l.append(40)
l.append(50)
print(l)
len(l)
# l.find(50)
print(l)

>> 결과

init이 입력되었습니다.
10이 입력되었습니다.
20이 입력되었습니다.
30이 입력되었습니다.
40이 입력되었습니다.
50이 입력되었습니다.
[10, 20, 30, 40, 50]
[10, 20, 30, 40, 50]
  • 문제
    연결리스트 = {
    'head' : {
        'value': 22,
        'next': {
            'value' : 2,
            'next' : {
                'value' : 90,
                'next' : {
                    'value' : 77,
                    'next' : None
                }
            }
        }
    }
}
    연결리스트['head']["next"]["next"]["next"]["value"]

>> 결과

35
    class Node:
    def __init__(self,data):
        print(f'{data}가 입력')
        self.data = data
        self.next = None

node1 = Node(90)
node2 = Node(2)
node3 = Node(37)
node4 = Node(35)
node5 = Node(21)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

node1.next.next.next.data

>>결과
90가 입력
2가 입력
37가 입력
35가 입력
21가 입력

> 35

더블 연결리스트

  • 기본형태
    # 더블 링크드 리스트의 기본 형태
init = {
    'head' : None
}

node1={'data':12,'prev':None,'next':None}
node2={'data':99,'prev':None,'next':None}
node3={'data':37,'prev':None,'next':None}
node4={'data':2,'prev':None,'next':None}

init['head'] = node1

node1['prev'] = init
node1['next'] = node2

node2['prev'] = node1
node2['next'] = node3

node3['prev'] = node2
node3['next'] = node4

node4['prev'] = node3
node4['next'] = None

init['head']['data']
init['head']['next']['data']
init['head']['next']['next']['data']
init['head']['next']['next']['prev']['prev']['data']
  • 알고리즘
    class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        self.prev = None
              
              
class LinkedList:
    def __init__(self):
        init = Node('init')
        self.head = init
        self.tail = init
    
    def append(self,data):
        newNode = Node(data)
        self.tail.next = newNode
        newNode.pre = self.tail # 이 코드 추가
        self.tail = newNode

정규표현식 및 찾기문제

re 모듈

  • 특정 문자열에서 원하는 문자를 찾거나 문자 구조를 찾는 것을 도와주는 파이썬 모듈

정규표현식

\d : 숫자
\D : 숫자가 아닌 문자 [^0-9]
\s : 공백 문자
\S : 공백 문자가 아닌 문자
\w : 알파벳대소문자 & 숫자
\W : [^0-9a-zA-Z]와 동일
\ : 캐릭터 자체를 표현 \
. : 캐릭터 자체를 표현 .

  • 예시 r'[a-z]\d’
    • 여기서 정규표현식은 r'[a-z]\d' 이러한 형태를 띄고 있습니다.
    • [a - z ] : a ~ z 까지의 문자열 중 하나를 말합니다.
    • \d : 숫자를 의미합니다.
    • 0-9 : 0 ~ 9까지의 숫자를 의미합니다.
    • ^ 모양은 제일 앞에 존재할 때 Except를 의미합니다.

정규표현식을 이용한 문제

  • re.sub 이용
    import re

re.sub('[a-zA-Z]', '', 'aAb1B2cC34oOp')
list(re.sub('[a-zA-Z]', '', 'aAb1B2cC34oOp'))
list(map(int, list(re.sub('[a-zA-Z]', '', 'aAb1B2cC34oOp'))))
# list(map(lambda x:int(x), list(re.sub('[a-zA-Z]', '', 'aAb1B2cC34oOp'))))
map(int, list(re.sub('[a-zA-Z]', '', 'aAb1B2cC34oOp')))
sum(map(int, list(re.sub('[a-zA-Z]', '', 'aAb1B2cC34oOp'))))

>> 결과

10
  • findall
    import re

re.findall('[0-9]', 'aAb1B2cC34oOp')
sum(map(int, re.findall('[0-9]', 'aAb1B2cC34oOp')))

>> 결과

10
  • 문자열에서 숫자만 출력
    def solution(my_string):
    result = 0
    for i in my_string:
        if i.isdigit():
            result += int(i)
    return result
  • a에 있는 값을 b에서 찾는데 index만 찾기
    def solution(emergency):
    # 원본은 a라는 이름으로 가지고 있습니다.
    # emergency를 정렬한 값을 b라고 합니다.
    # a에 있는 값을 b에서 찾는데 index만 찾아서
    # 새로운 리스트로 만듭니다.
    a = emergency
    b = sorted(a, reverse=True)
    result = []
    for i in a:
        result.append(b.index(i) + 1)

    return result
    # 간단하게 컴프리헨션으로 표현
def solution(emergency):
    s_emergency = sorted(emergency, reverse=True)
    return [s_emergency.index(i) + 1 for i in emergency]

트리와 그래프

  • 트리의 기본형태

    • value

    • child - left

    • child - right

      {
    'value': 5,
    'left': {},
    'right': {}
}

QnA. object나 array(기존 자료형)로 tree나 linked list를 구현할 수 있는데 왜 class로 구현할까요?

  1. 더 lite한 모델을 만들기 위해
  2. 확장성
  3. OOP(Object-Oriented Programming, 객체 지향 프로그래밍)에 철학에 맞기 때문에
  • 문제

```python
tree = {
    'root':{
        'value':55,
        'left':{
            'value':30,
            'left':{
                'value':25,
                'left':{
                    'value':21,
                    'left':None,
                    'right':None
                },
                'right':None
            },
            'right':{
                'value':37,
                'left':None,
                'right':None
            }
        },
        'right':{
            'value':70,
            'left':None,
            'right':{
                'value':77,
                'left':None,
                'right':{
                    'value':80,
                    'left':None,
                    'right':None
                }
            }
        }
    }
}
```

```python
# 아래와 같은 형태로 Node를 만들어 진행하게 됩니다.
root = {
    'value': 55,
    'left': None,
    'right': None
}

node1 = {'value':99, 'left':None, 'right':None}
node2 = {'value':53, 'left':None, 'right':None}
node3 = {'value':37, 'left':None, 'right':None}
node4 = {'value':54,  'left':None, 'right':None}
root['right'] = node1
root['left'] = node2
node2['left'] = node3
node2['right'] = node4

root['value']
root['right']['value']
root['left']['left']['value']
```

```python
class Node:
    def __init__(self, data):
        self.data = data
        # self.child = [] # 2진 트리가 아닌 경우에도 풀이가 가능합니다.
        self.left = None
        self.right = None

node1 = Node(55)
node2 = Node(53)
node3 = Node(99)
node4 = Node(37)
node5 = Node(54)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5

node1.data
node1.right.data
node1.left.data
node1.left.left.data
node1.left.right.data
```
  • 알고리즘
    class Node:
    def __init__(self, data):
        self.data = data
        # self.child = [] # 2진 트리가 아닌 경우에도 풀이가 가능합니다.
        self.left = None
        self.right = None

class Tree:
    def __init__(self, data):
        init = Node(data)
        self.root = init
        self.counter = 0
    
    def __len__(self):
        return self.counter
    
    def insert(self, data):
        newNode = Node(data)
        currentNode = self.root
        while(currentNode):
            if (data == currentNode.data):
                return
            if (data < currentNode.data):
                # 왼쪽으로 데이터 삽입해야 합니다.
                # 해당 데이터 부분이 비어있으면 데이터를 넣고, 아니면 현재 노드를 이동시킵니다.
                if (not currentNode.left):
                    currentNode.left = newNode
                    self.counter += 1
                    return
                currentNode = currentNode.left
            if (data > currentNode.data):
                # 오른쪽으로 데이터 삽입해야 합니다.
                # 해당 데이터 부분이 비어있으면 데이터를 넣고, 아니면 현재 노드를 이동시킵니다.
                if (not currentNode.right):
                    currentNode.right = newNode
                    self.counter += 1
                    return
                currentNode = currentNode.right

    # 깊스너큐(깊이우선 탐색은 스택, 너비우선 탐색은 큐)
    def DFS(self):
        # 깊이우선탐색, DFS(Depth First Search)
        # Stack 이용!
        result = []
        stack = [self.root]
        
        while(len(stack) != 0):
            current = stack.pop()
            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)
            result.append(current.data)
        return result
        
        
    def BFS(self):
        # 너비우선탐색, BFS(Breadth First Search)
        # Queue 이용!
        result = []
        queue = [self.root]
        
        while(len(queue) != 0):
            current = queue.pop(0)
            if current.right:
                queue.append(current.right)
            if current.left:
                queue.append(current.left)
            result.append(current.data)
        return result
        
t = Tree(5)
t.insert(3)
t.insert(8)
t.insert(1)
t.insert(4)
t.insert(6)
t.insert(9)
t.DFS()
t.BFS()

>> 결과

[5, 8, 3, 9, 6, 4, 1]

--------------------------

t.root.data
t.root.left.data
t.root.right.data

>> 결과

8

출처

XENAS Blog : 네이버 블로그

just my way : 네이버 블로그

  • 멋쟁이사자처럼 AI스쿨 이호준강사님
profile
김영민
배운걸 다 흡수하는 제로민
이전 포스트

멋쟁이 사자처럼 AI 스쿨 TIL-47-1

다음 포스트

멋쟁이 사자처럼 AI 스쿨 TIL-48

0개의 댓글