프로그래머스 인공지능 데브코스

박준희·2023년 8월 22일

프로그래머스

목록 보기

1/28

이미지 출처: https://school.programmers.co.kr/learn/courses/17597/17597-6%EA%B8%B0-k-digital-training-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9D%B8%EA%B3%B5%EC%A7%80%EB%8A%A5-%EB%8D%B0%EB%B8%8C%EC%BD%94%EC%8A%A4

본론으로 들어가기 전에 좋은 기회로 프로그래머스에서 진행하는 인공지능 데브코스 6기에 합격하게 되었어요.😃
그런데 개인 블로그가 필요하다고 해서 교육 받는 것도 정리할 겸 개발 블로그를 시작하게 되었어요. 부족하지만 점차 발전해가는 모습 지켜봐주세요👊👊

📕Week1 day1

첫째날은 OT만 진행했고 두번째 날부터 온라인 강의를 시작했어요!
많은 양을 한 번에 정리하기 위해 간단하게 작성할게요.

1.자료구조&알고리즘

자료구조란?

자료구조는 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

알고리즘이란?

프로그래밍에서의 알고리즘으로 정의한다면 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택이라고 할 수 있다.

2.선형배열(Linear Array)

자료 구조의 한 형태인 선형 배열에 관해 배웠다.

📒배열 : 원소들을 순서대로 늘어놓은것
📒선형 배열: 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말합니다.

선형배열구조 중에서 파이썬의 데이터형인 list를 다루어 보았습니다.

list 연산

리스트의 길이와 결과 처리 시간이 관계 없는 연산
- append() : 리스트의 맨 뒷부분에 데이터를 덧붙인다.
- pop() : 리스트의 맨 뒷부분의 데이터를 꺼내고 삭제한다.
리스트의 길이와 비례해서 시간이 걸리는 연산
- insert() : 원하는 위치에 데이터를 삽입한다.
- del() : 리스트 안의 데이터를 삭제한다.

*추가 다른연산
index() : 원하는 원소를 탐색하여 리스트 위치를 반환

3. 정렬(Sort), 탐색(Search)

정렬(Sort)이란?

📒여러개의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업입니다.

정렬 알고리즘에는 여러가지가 있는데 리스트를 사용하면 이미 내장된 정렬 기능이 존재하기 때문에 정렬알고리즘을 구현할 필요가 없습니다.

아래의 두 방법이 대표적입니다.

sorted() 파이썬 내장함수
.sort() 리스트에 쓸 수 있는 메서드

탐색(Search)이란?

📒여러개의 의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업입니다.

탐색 알고리즘에도 여러가지가 있는데 대표적인 두 가지만 설명합니다.

선형 탐색 (linear search), 또는 순차 탐색 (sequential search): 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냅니다. 배열의 길이에 비례하는 시간이 걸립니다.
이진 탐색 (binary search): 탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용할 수 있습니다. 배열의 가운데 원소와 찾으려 하는 값을 비교하면, 왼쪽에 있을지 오른쪽에 있을지를 알 수 있습니다.

4,5. 재귀 알고리즘(recursive algorithms)

📒재귀 알고리즘이란 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘입니다.주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용해서, 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법입니다.

*많은 경우, 재귀적으로 표현된 알고리즘은 사람이 이해하기 좋지만, 컴퓨터가 실행했을 때 그 성능은 좋지 않은 경우가 많습니다.

예시. 피보나치 수열

피보나치 수는 첫 번째와 두 번째 값이 1이고 다음부터는 그 전의 수와 그 전전의 수를 더하는 방식입니다.

첫 번째 값이 0으로 시작하는 경우도 있으며 다음과 같은 형태의 수열입니다.
0, 1, 1, 2, 3, 5, 8, 13,...

피보나치 수열을 재귀함수로 구현해보았습니다.

def fibo(n):
    if n<=1:
        return n
    return fibo(n-1)+fibo(n-2)

이렇게 문제의 종류에 따라서는 재귀 알고리즘을 적용함으로써 알고리즘을 간단하고 이해하기 쉽게 서술할 수 있다는 장점이 있습니다.
하지만 시간적인 측면에선 그리 효율이 좋지 않은 것이 많습니다.

하나의 재귀 알고리즘이 주어질 때, 이것을 재귀적이지 않은 (non-recursive) 방법으로 동일하게 풀어내는 알고리즘이 존재한다는 것을 수학적으로 증명할 수 있습니다. 보통은 순환문 (loop) 을 이용해서 정해진 연산을 반복함으로써 문제의 답을 구하는데, 따라서 반복적 (iterative) 알고리즘이라고 부르기도 합니다. 일반적으로, 주어진 문제에 대해서 반복적인 알고리즘이 재귀적인 알고리즘보다 문제 풀이의 (시간적) 효율이 높습니다.

다음은 그 예시입니다. time 모듈을 사용하여 걸리는 시간을 측정해 보았습니다.(코드 생략)

from re import T
#재귀알고리즘 효율 ex) 피보나치 수열 함수
import time
def rec(n):
    if n<=1:
        return n
    else:
        return rec(n-1)-rec(n-2)

def iter(n):
    if n<=1:
        return n
    else:
        i=2
        t0=0
        t1=1
        while i <= n:
            t0, t1 = t1, t0+t1
            i+=1
        return t1
이하 생략
>>>Enter a number1
iterative version: 1 (0.000)
recursive version: 1 (0.000)
Enter a number10
iterative version: 55 (0.000)
recursive version: 55 (0.000)
Enter a number30
iterative version: 832040 (0.000)
recursive version: 832040 (0.337)

이와 같이 재귀적인 방법이 시간적인 측면에서 효율이 떨어지는 것을 확인할 수 있습니다.

그럼에도 불구하고, 재귀 알고리즘이 가지는 특성 때문에 트리 (tree) 와 같은 자료 구조를 이용하는 알고리즘에는 매우 직관적으로 적용할 수 있는 경우가 많습니다.

연습문제 - 재귀적 이진탐색

def binsearch(L,x,lower,upper):
    if x<L[lower] or x>L[upper]:
        return -1
    mid = (lower+upper)//2
    if x == L[mid]:
        return mid
    elif x<L[mid]:
        return binsearch(L[:mid],x, lower, mid)
    else:
        return binsearch(L[mid+1:],x,mid+1, upper)

6. 알고리즘의 복잡도

알고리즘의 "복잡도" (complexity) 라고 부르는 것은 이 알고리즘이 실행함에 있어, 문제의 크기 (일반적으로 데이터 원소의 개수를 뜻합니다) 가 커짐에 따라서 얼마나 큰 시간을 (또는 공간을) 요구하느냐를 뜻합니다.

시간복잡도(time complexity)

📒문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계

-평균시간복잡도 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 -최악시간 복잡도 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

공간복잡도(space complexity)

📒문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

Big-O Notation 점근표기법의 하나 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현

다음은 각 알고리즘의 시간복잡도를 나타낸 것이다.

선형시간 알고리즘 - O(n)
예) 선형탐색 알고리즘
로그시간 알고리즘 - O(n)
예) 이진탐색 알고리즘
이차시간 알고리즘 - O(n^2)
예) 삽입정렬 worst case의 경우 O(n^2) 정렬이 역순으로 되어있는 경우
병합정렬 - O(nlogn)

7-9. 연결리스트(Linked List)

📒연결리스트(Linked List)는 추상적 자료구조(Abstract Data Structures)의 한가지 종류로 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.

💡추상적 자료구조(Abstract Data Structures)란 자료(Data)에 대한 일련의 연산(A set of operations)이 정의되며, 각각의 연산에 대한 연산 복잡도가 정의된 가상의 자료 저장 공간이다.
Data 예) 정수, 문자열, 레코드
A set of operations 예) 삽입, 삭제, 순회, 정렬, 탐색

기본적 연결리스트

Node

Node구성
-Data
-Link(next)
Node내의 데이터는 다른 구조로 이루어질 수 있습니다.

예) 문자열, 레코드, 또 다른 연결 리스트 등

리스트의 맨 앞 원소 head 맨 끝 원소 tail 연결 리스트 안에 노드가 몇개 있는지 알면 좋습니다.

자료구조 정의

다음은 파이썬으로 구현한 연결리스트 자료구조입니다.

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None
class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None
#비어있는 연결 리스트

연산정의

다음은 위에서 정의한 자료구조에 사용할 수 있는 연산입니다.

특정 원소 참조(k번째)
리스트 순회
길이 얻어내기
원소 삽입
원소 삭제
두 리스트 합치기

특정 원소 참조

# 1. 특정 원소 참조
def getAt(self, pos):
    if pos <=0 or pos>self.nodeCount:
        return None
    i = 1
    curr = self.head
    while i<pos:
        curr = curr.next
        i+=1
    return curr

리스트 순회

def traverse(self):
    result = []
    temp = self.head
    while temp != None:#self.next 가 None이면 끝에 도달한 것
        result.append(temp.data)
        temp = temp.next

    return result

길이 얻어내기
self.nodeCount를 사용하면 된다.
원소 삽입
pos-1번째 노드를 찾는다 - prev 라고 합니다.
prev 노드가 newnode를 가리키게 하고 newnode가 원래의 prev.next를 가리키게 합니다. 마지막으로 노드카운트를 1증가시킵니다.

여기서 주의할 점은
1) 삽입하려는 위치가 맨 앞일 때

prev 없음
Head조정 필요

2)삽입하려는 위치가 맨 끝일 때

tail 조정 필요

def insertAt(self,pos, newNode):
    if pos < 1 or pos >self.nodeCount +1:
        return False

    if pos == 1:
        newNode.next = self.head
        self.head = newNode

    else:
        if pos ==self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos-1)
        newNode.next = prev.next
        prev.next = newNode

    if pos == self.nodeCount + 1:
        self.tail = newNode

    self.nodeCount += 1
    return True

원소의 삭제
pos-1번째 노드 prev로, pos번째 노드 curr로 정의합니다.
prev.next가 curr.next를 가리키게 조정하고
마지막으로 nodeCount -1

여기서 주의할 점은
1) 삭제하려는 node가 맨 앞의 것일 때

prev 없음
head 조정 필요

2)리스트의 맨 끝의 node를 삭제할 때

tail 조정 필요

*노드가 한 개만 존재하는 리스트에서 유일한 노드를 삭제할 때 주의해야한다.

def popAt(self, pos):
        data = 0
        if pos < 1 or pos >self.nodeCount:
            raise IndexError

        if self.nodeCount == 1:
            data = self.head.data
            self.head = None
            self.tail = None
        elif pos == 1:
            data = self.head.data
            self.head = self.head.next

        elif pos == self.nodeCount:
            prev = self.getAt(pos -1)
            data = prev.next.data
            prev.next = None
            self.tail = prev
        else:
            prev = self.getAt(pos -1)
            data = prev.next.data
            prev.next = prev.next.next

        self.nodeCount -= 1
        return data

두 리스트의 연결

두 리스트의 연결은 간결하다.

def concat(self, L):
    self.tail.next = L.head
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

이번에는 연결 리스트의 맨 앞에다가 데이터 원소를 담고 있지 않은, 그냥 자리만 차지하는 노드인 더미 노드(dummy node)를 가지는 연결 리스트를 대상으로, 지금까지 우리가 정의한 아래와 같은 연산들을 구현해봅니다.
#추가설명 필요 수정하기

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos <1 or pos > self.nodeCount:
            return None
        i = 0
        curr = self.head
        while i<pos:
            curr = curr.next
            i+=1
        return curr

    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos != 1 and pos == self.nodeCount+1:
            prev = self. tail
        else:
            prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)

    def popAfter(self, prev):
        curr = prev.next

        if prev.next == None:
            return None

        if curr.next == None:
            prev.next = None
            self.tail = prev

        else:
            prev.next = curr.next

        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        if pos<0 or pos>self.nodeCount:
            raise IndexError

        prev = self.getAt(pos-1)
        return self.popAfter(prev)

    def concat(self, L):
        self.tail.next = L.head.next
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

10. 양뱡향 연결 리스트(Doubly Linked Lists)

지금까지 구현한 연결 리스트는 단방향으로 연결되어 있었습니다.
이번에는 양방향으로 연결된 양방향 연결 리스트(Doubly Linked Lists)를 구현해 보려합니다.

양방향 연결 리스트는 링크를 나타내기 위한 메모리 사용량이 늘어나고, 원소를 삽입/삭제하는 연산에 있어서 앞/뒤의 링크를 모두 조정해 주어야 하는 단점이 있지만, 데이터 원소들을 차례로 방문할 때, 앞에서부터 뒤로도 할 수 있지만 뒤에서부터 앞으로도 할 수 있다는 장점이 있습니다.

컴퓨터 시스템의 주요 구성 요소의 하나인 운영체제 (operating system) 등에서는 리스트를 대상으로 앞/뒤로 왔다 갔다 하면서 작업을 행하는 일들이 빈번히 요구되고, 따라서 양방향 연결 리스트가 많이 이용되고 있습니다.

다음은 양방향 연결 리스트를 파이썬으로 구현한 것입니다.

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None
    
class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos <1 or pos > self.nodeCount:
            return None

        if pos>self.nodeCount//2:
            i = 0
            curr = self.tail
            while i<self.nodeCount-pos+1:
                curr = curr.prev
                i+=1
        else:
            i = 0
            curr = self.head
            while i<pos:
                curr = curr.next
                i+=1

        return curr

    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)

    def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount -= 1
        return curr.data

    def popBefore(self, next):
        curr = next.prev
        next.prev = curr.prev
        curr.prev.next = next
        self.nodeCount-=1
        return curr.data

    def popAt(self, pos):
        if pos<0 or pos>self.nodeCount:
            raise IndexError

        prev = self.getAt(pos-1)
        return self.popAfter(prev)

    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount

마무리 나중에 입력 파이썬 코드에 주석도 달아야됨

박준희

게을렀던 프로그래밍 공부

프로그래머스 인공지능 데브코스