2024-03-11 AI 코딩 TIL

오늘도 알고리즘의 한 주가 시작 되었습니다!

 

튜터님의 강의

스택 2

 

탐색 알고리즘에 유망한지 아닌지를 따녀야 한다.

기본적인 예시!

의사결정 공간 트리, 상태 공간 트리

백트레킹에 개념중에 중요한 부분

이거 아주 중요합니다..

이 순서를 잘 몰라서 자꾸 틀렸어,,,

 

 

DFS, BFS
깊이 우선 탐색, 넓이 우선 탐색

드라마 한 방에 몰아보기 : DFS
드라마 하나 씩 나올 때 마다 보기 : BFS

 

DFS(Depth First Search)

깊이우선탐색

 

 

 

 

DFS는 스택을 이용하기 때문에 stack을 이용해서 만든다.!!!

 

 

BFS 이 친구는 큐를 이용해서 풀이!

 

---

햄버거 다이어트 처럼 재료를 골라야 할 때 재료는 모두 고르는 것이 좋은 것이 아니라
재료의 조합에 따라 값이 다른 경우를 비교 할 때!!

 이걸 더 짧게 만들어 보자!

 

Memoization! 메모이제이션!

 

타뷸레이션!

지금 당장 필요하지 않아도 내가 원하는 값을 알아내기 위해서 순서대로 찾아가는거!

---

스택 만들기

 

아 주말동안 퀸 푼다고 과제가 있는걸 깜빡 해버렸다....
뒤늦게라도 만들었습니다 ㅠㅠ

class MyStack:
    def __init__(self):
        self.max_limit = -1
        self.size = 0  # 아무것도 안설정하면 크기는 0
        self.items = []  # 내용도 비어있음
        self.able = -1  # -1이 되면 꽉찬거임

    def limit(self, limit):
        self.max_limit = limit  # 최대치 설정

    def is_empty(self):
        if self.size == 0:  # 사이즈가 0이면 비어있는 상태 Ture
            return True
        else:
            return False  # 아니라면 False 출력

    def is_full(self):
        if self.max_limit == -1:
            print("제한 설정이 없습니다.")
        if self.size >= self.max_limit:  # size의 값이 limit 랑 같으면 꽉 참
            return True
        else:
            return False

    def push(self, item):
        if self.max_limit == -1:
            self.size += 1
            self.items.append(item)
        if self.size < self.max_limit:  # 제한 값 보다 작으면 넣음
            self.size += 1
            self.items.append(item)
        else:  # 제한 값 보다 크면 못 넣음
            print("스택이 가득 찼습니다.")

    def pop(self):
        if not self.is_empty():
            self.temp = self.items[-1]  # 마지막 열에 있는 값 따로 저장
            del self.items[-1]  # 마지막 열 제거
            self.size -= 1
            return self.temp  # 따로 넣어 둔 값 리턴
        else:
            print("리스트가 비어 있습니다.")

    def popleft(self):
        if not self.is_empty():
            self.temp = self.items[0]  # 가장 왼쪽 열에 있는 값 따로 저장
            del self.items[0]  # 가장 왼쪽 열 제거
            self.size -= 1
            return self.temp  # 따로 넣어 둔 값 리턴
        else:
            print("리스트가 비어 있습니다.")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 마지막 열에 있는 값 보여주기
        else:
            print("리스트가 비어 있습니다.")

    def clear(self):
        self.items = []
        self.size = 0

    def is_contain(self, item):
        return item in self.items # item 이 안에 있으면 참 없으면 거짓!

    def list(self):
        return self.items


stack = MyStack()
print(stack.is_empty())
stack.limit(2)
print(stack.is_full())
stack.push(1)
print(stack.is_full())
stack.push(2)
print(stack.is_full())
stack.push(2)
print(stack.is_full())
print(stack.list())
a = stack.pop()
print(a)
print(stack.list())
a = stack.popleft()
print(a)
stack.push(2)
stack.clear()
print(stack.list())
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())
stack.push(1)
print(stack.is_contain(1))
print(stack.is_contain(0))

 

그리고 오늘 문제 너무 어려워서 결국은 다 못 풀었어요 ㅠㅠ
dfs 개념이해 너무 어렵습니다....ㅠㅠㅠ
내일 예비군 전에 복습을 ...