BFS 개념 Breadth First Search 노드를 방문하고 너비 우선으로 인접한 노드를 방문한다. 인접한 노드 중 방문하지 않은 모든 노드들을 저장 후 가장 처음에 넣은 노드를 꺼내서 탐색 가장 처음에 넣은 노드 -> 큐(Queue) 이용하는 것이 적합 1. 루트 노드를 큐에 저장 2. 현재 큐의 노드를 빼서 visited 에 추가 (방문처리) 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가 4. 2부터 반복. 5. 큐가 비면 탐색 종료 BFS 구현 조금 더 확실히 하기 위해 각 노드에 붙은 숫자를 섞어보았다. 위와 같이 DFS인 척 하는 그래프가 있다고 해보자. 우리는 이 그래프를 BFS로 탐색하려고 한다. 그러면 탐색 순서는 이러한 형태가 되어야 할 것이다. 이를 딕셔..
DFS & BFS? 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. 왜 DFS & BFS 를 배울까요? 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에, 모든 경우의 수를 전부 탐색해야 하는 경우도 있습니다. DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있습니다. DFS 는 끝까지 파고드는 것이고, BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것이 차이점입니다. DFS 끝까지 파고드는..
그래프란? 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 자료를 저장하고 꺼내는 것에 초점 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 표현에 초점 그래프 : 연결 관계에 초점 노드(Node): 연결 관계를 가진 각 데이터, 정점(Vertex) 간선(Edge): 노드 간의 관계를 표시한 선 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 유방향 그래프 (Directed Graph) 방향이 있는 간선 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능 무방향 그래프 (Undirected Graph) 방향이 없는 간선 그래프의 표현 방법 인접 행렬(Adjacency Matrix): 2차원 배열로 그래..
최대 힙 - 삽입 힙이란? 힙? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Tree)(Complete Binary Tree) 최대/최소의 값들이 필요한 연산에 사용 Max 힙 : 최댓값이 맨 위 Min 힙 : 최솟값이 맨 위 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아님 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 4 2 1 Level 2 # 모든 부모 노드의 값이 자식 노드보다 크므로 힙O 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 4 2 5 Level 2 # 모든 부모 노드의 값이자식 노드보다 크지 않으므로 힙이 아님..
트리란? 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점 트리 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node(Terminal Node): Child Node가 하나도 없는 노드 (제일 끝) Sibling: 동일한 Parent Node를 가진 노드 Depth:..
해시테이블이란? 해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조 구현 충돌 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다. 예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다. 👉 입력값이 달라도 똑같은 결과가 나오면 충돌 이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다. 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식 체이닝은 충돌 발생 시 ‘연결’해가는 것 오픈 어드레싱 O(1) 체이닝 O(n) 오픈 어드레싱은 값이 뭉치는 클러스터링 이 발생할 수 있고, 체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점 C++, Java, Go는 체이닝을 택하고 Python, ..
스택(Stack)스택(Stack)이란?후입선출의 원칙을 따르는 자료구조로 차곡차곡 쌓아올리는(Stack) 것삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간 복잡도사용 예브라우저의 뒤로가기실행 취소 (Ctrl + z)재귀 함수역순 문자열 (문자열 거꾸로 뒤집기)구현# structures.py'''연결리스트를 응용해서, 대신 제일 앞이 아니라 제일 위여야 하므로 가장 처음 걸 top으로 한다.O↓O↓O↓O↓O형태가 된다.'''class Node: def __init__(self, val = 0, next = None): self.val = val #상자 self.next = nextclass Stack: def __init__(self): self.top ..
배열(Array) 배열이란? 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조 데이터 조회에서 O(1)의 [[시간 복잡도]]를 가진다. 장점 연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다. 단점 크기가 고정되어 추가/삭제에 제약이 있다. 연결리스트 (Linked List) 연결리스트란? 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태 즉, 노드들이 서로 연결되어 있는 구조 데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도 데이터 추가와 삭제에는 O(1)의 시간 복잡도 Array vs Linked List 배열 (Array): 파이썬의 리스트. 접근 쉬움..
12. Django에서 테이블을 설계하고 DB에 반영하는 방법에 대해서 설명하시오. 1. models.py에서 models.Model을 상속한 클래스 생성 : 이 클래스가 데이터 테이블이 된다. 2. 필드 생성 3. 마이그레이션 파일 생성 : 모델이 새로 생성되거나 변경사항이 생길 때 사용 4. 마이그레이션 파일을 적용하는 migrate 명령어로 db에 반영 13. 회원가입을 할 때 비밀번호 저장을 암호화하는 이유는 무엇입니까? 비밀번호는 절대 유출되어서는 안 되는 정보이기 때문에 해킹, 정보유출 등의 위험을 방지하기 위해 복호화 할 수 없는 해시값으로 암호화해 저장함 14. JWT는 무엇입니까? JSON Web Token의 줄임말 - 유저를 인증하고 식별하기 위한 Token기반의 인증 JSON데이터를 ..
5. Django의 프로세스는 어떤 순서로 동작합니까? 1. 클라이언트 요청 수신: 클라이언트로부터 HTTP Request 요청을 받습니다. 2. URL 매핑 : urls.py에 정의된 url 패턴들과 요청된 url을 비교하여 일치하는 url 패턴과 연결된 뷰 함수 또는 클래스를 찾습니다. 해당 view가 호출됩니다. 3. 뷰 처리: 뷰 함수는 클라이언트의 요청을 처리하고 모델과 상호작용하여 데이터베이스의 데이터를 읽거나 수정합니다. 4. 템플릿 렌더링: 뷰 함수에서 처리된 데이터는 템플릿(Template)을 이용하여 html 페이지로 렌더링됩니다. 이 때 처리된 데이터를 html에 삽입하여 동적인 컨텐츠를 생성하며, 이는 사용자에게 보여지는 부분이 됩니다. 5. HTTP 응답 반환: 뷰에서 리턴된 ht..
Django가 무엇인지 설명하시오 Django는 파이썬 기반의 웹 프레임워크로, 기본적이고 반복적인 기능들이 미리 구현되어있어 웹 애플리케이션 개발을 쉽고 빠르게 만들어줍니다. MVC 아키텍처 패턴을 사용하며, 다양한 기능을 제공하여 데이터베이스 관리, URL 라우팅, 템플릿 엔진, 보안 등을 처리할 수 있습니다. Django를 백엔드 스택으로 선정한 이유는 무엇입니까? 사람의 언어와 굉장히 비슷하고, 그 때문에 직관적이라는 장점을 가진 Python 언어의 장점과, 편리하면서 완성도가 높은 Django 의 장점이 가장 잘 어울리며 굉장히 좋은 시너지를 낸다고 생각합니다. Django에는 어떤 장점이 있습니까? Django는 개발자의 생산성을 높이고 빠르고 효율적인 웹 애플리케이션 개발을 지원합니다. 미리..
오늘 한 일 - 파이썬 문법 심화 1주차 15~19 - 코딩테스트 연습 Level 2 소수찾기 배운 거 itertools 데카르트곱 구하기 from itertools import product sample1 = ["A", "B", "C", "D", "E"] sample2 = [1, 2, 3, 4] a = product(sample1, sample2) # 행 / 열을 구분하여 프린트 하기 위해 enumerate 사용 for i, v in enumerate(product(sample1, sample2), 1): print(v, end=" ") if i % len(sample2) == 0: print("") 결과 ('A', 1) ('A', 2) ('A', 3) ('A', 4) ('B', 1) ('B', 2) ..
오늘의 강의 파이썬 문법 심화 1주차 9~14 기억할 것 예외처리 try / except 사용 ValueError : 숫자로 바꿀 수 없는 것을 숫자로 바꾸려고 함 ZeroDivisionError : 0으로 나눈 경우 Exception as 변수 : 정의하지 않은(예상치 못한) 에러가 발생했을 때. 변수 - 에러 내용 (권장하지 않음) 패킹과 언패킹 함수를 만드는데 매개변수의 갯수를 지정하고 싶지 않다면? list 에서 def add(*args): * 👉add 함수에 들어가는 모든 인자를 args안에 넣을 거다! 요런 함수가 있을 때 리스트를 numbers = [1, 2, 3, 4] 라고 한다면, print(add(*numbers)) # list name : number ## 아래와 같다. pirnt(a..
오늘의 강의 파이썬 문법 심화 1주차 1~8강 오늘의 난관 에러가 나타났다! 최신 버전이 쓰고 싶어서 python을 새로 깔았는데 원래 쓰던 버전 : 3.8.6 새로 설치한 버전 : 3.11.2 가상환경을 설치하면 C:\Users\SCY\Desktop\DEV\python\lec2>python -m venv venv Error: Command '['C:\\Users\\SCY\\Desktop\\DEV\\python\\lec2\\venv\\Scripts\\python.exe', '-m', 'ensurepip', '--upgrade ', '--default-pip']' returned non-zero exit status 1. 이런 에러가 뜬다. 근데 또 가상환경이 만들어지기는 한다. 대신 venv\Script..
1. 프로젝트 주제 팀원 소개하기 작업 Python Flask, HTML, JavaScript, CSS (Bootstrap) 사용해서 CRUD 구현 (방명록 생성, 읽기, 수정, 삭제 기능 구현) 핵심 기능 : 방명록 작성, 읽기 추가작업 : 수정, 삭제 - 비밀번호 구현을 중점적으로 작업 Keep 👉 이번 프로젝트에서 진행한 과정 중 다음 프로젝트에서도 유지했으면 하는 부분. - 서로 응원해주고 축하해주는 부분은 계속 이어지면 좋겠다. - 지금처럼 모르는 부분을 바로 해결해주기보다 서로도움을 줌으로써 본인이 해결할 수 있도록 하는 것 - 협업능력을 키운다는점에서 자주팀이 바뀌는 부분. 적응하는데 어렵지만 도움 되는 것 같다. - 해 보지 않은 것에 도전해 구현하려고 한 것. - 잘 모르는 부분도 적극적..
