본문 바로가기

전체 글

 (118)
너비 우선 탐색 (BFS, Breadth-First Search) 너비 우선 탐색 (BFS, Breadth-First Search) 개요너비 우선 탐색(BFS)은 그래프나 트리를 탐색하는 대표적인 알고리즘 중 하나로, 탐색의 너비(Breadth)를 우선으로 진행하는 방식이다. BFS는 시작 노드에서 출발해 인접한 노드들을 먼저 탐색한 후, 그 다음으로 인접한 노드들의 이웃들을 탐색하는 방식으로 진행된다. 즉, 같은 레벨에 있는 노드들을 먼저 방문하고, 한 레벨의 모든 노드를 방문한 후 다음 레벨로 넘어가는 방식이다.BFS는 큐(Queue) 자료구조를 사용해 구현되며, 최단 경로를 찾는 문제나, 그래프의 각 노드를 너비 우선으로 방문할 때 매우 유용하다. BFS의 동작 원리시작 노드에서 탐색을 시작한다.해당 노드를 방문 처리하고, 그 노드를 큐에 넣는다.큐에서 노드를 꺼..
비동기(Asynchronous)와 동기(Synchronous) 동기(Synchronous)와 비동기(Asynchronous)에 대한 이해 동기와 비동기는 프로그램의 작업 처리 방식을 설명하는 개념으로, 특히 입출력(I/O)이나 멀티태스킹에서 많이 언급됩니다. 이 두 개념은 작업을 어떻게 처리하고, 작업 완료를 기다리는 방식에서 큰 차이를 보인다. 1. 동기(Synchronous)동작 원리:동기 방식에서는 하나의 작업이 완료될 때까지 기다린 후 다음 작업을 진행한다. 즉, 작업을 순차적으로 실행하며, 이전 작업이 끝나기 전에는 다음 작업으로 넘어가지 않는다.비유:예를 들어, 식당에서 음식을 주문한 후 그 음식이 나올 때까지 아무것도 하지 않고 기다리는 상황이다. 이 경우에는 음식이 준비되기 전까지는 다른 일을 할 수 없다.실생활 예:은행에서 업무 처리를 생각해보면, ..
깊이 우선 탐색 (DFS, Depth-First Search) 깊이 우선 탐색 (DFS, Depth-First Search) 개요깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 그래프의 모든 노드를 깊이(depth)를 우선으로 탐색하는 방법이다. DFS는 재귀(Recursion)나 스택(Stack)을 사용하여 구현할 수 있으며, 그래프 또는 트리에서 특정 경로를 찾거나, 모든 노드를 방문하는 데 유용하게 사용된다.DFS는 다음과 같은 방식으로 동작한다:시작 노드에서 출발하여 한 노드를 선택하고, 그 노드에서 갈 수 있는 경로 중 하나를 선택해 탐색을 계속 진행한다.더 이상 갈 수 있는 노드가 없을 때, 다시 이전 경로로 돌아와 다른 경로를 탐색한다.방문한 노드를 다시 방문하지 않도록 하기 위해 방문 여부를 기록한다.DFS는 깊이 우선이기 때문에 가능한 ..
그래프(Graphs)- 인접 리스트(Adjacency List) 인접 리스트는 그래프를 표현하는 또 다른 방법으로, 각 노드에 연결된 이웃 노드들을 리스트나 다른 자료구조로 저장하는 방식이다. 이 방법은 간선의 수가 적은 희소 그래프(Sparse Graph)를 표현할 때 공간 효율적이다. 인접 리스트의 구조각 노드는 자신과 연결된 노드들의 리스트를 갖고 있다. 이를 위해 파이썬에서는 딕셔너리나 리스트를 활용할 수 있다.키(Key): 노드를 나타낸다.값(Value): 해당 노드와 연결된 노드들의 리스트이다. 리스트의 각 항목은 이웃 노드를 나타낸다.인접 리스트 예시다음은 4개의 노드를 가진 무방향 그래프의 예시이다. 0 -- 1 \\ / \\ 2 -- 3이 그래프의 인접 리스트 표현은 다음과 같다:{ 0: [1, 2], 1: [0, 2..
세션(Session), 쿠키(Cookie), 캐시(Cache) 1. 세션(Session)세션은 서버와 클라이언트 간의 상태를 유지하는 방법 중 하나이다. 웹은 기본적으로 무상태(stateless) 프로토콜인 HTTP를 사용하기 때문에, 서버는 클라이언트의 이전 요청이나 상태를 기억하지 못한다. 따라서, 세션은 서버 측에서 사용자와의 상호작용 상태를 유지하기 위한 중요한 기법이다.세션의 동작 방식:사용자가 웹사이트에 처음 접속하면, 서버는 그 사용자에게 고유한 세션 ID를 생성한다.이 세션 ID는 일반적으로 쿠키를 통해 클라이언트에 저장된다.사용자가 동일한 서버에 다시 요청을 보내면, 쿠키에 저장된 세션 ID를 서버에 전송하여 서버는 해당 사용자의 상태를 유지할 수 있게 된다.세션은 주로 서버의 메모리나 데이터베이스에 저장되며, 로그인 정보나 장바구니 정보와 같은 상..
그래프(Graphs) - 인접행렬(Adjacency Matrix) 그래프(Graphs) 개요그래프는 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 이루어진 자료구조이다. 그래프는 여러 문제를 모델링하는 데 유용하며, 특히 네트워크, 지도, 소셜 네트워크 등의 문제를 해결할 때 자주 사용된다.그래프는 방향성(Directed)이 있을 수도 있고 없을 수도 있으며, 가중치(Weighted)가 있을 수도 있고 없을 수도 있다. 이 특징에 따라 그래프의 형태가 달라진다.그래프를 표현하는 두 가지 주요 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)입니다. 이 중에서 인접 행렬에 대해 자세히 살펴보겠다. 인접 행렬 (Adjacency Matrix)인접 행렬은 그래프를 표현하는 방법 중 하나로, 2차원 배열을 사용하여 노드 ..
REST API REST API(Representational State Transfer Application Programming Interface)는 네트워크 상에서 서로 다른 컴퓨터 시스템 간의 통신을 가능하게 하는 규칙 세트로, 주로 HTTP를 통해 작동한다. REST API는 웹 애플리케이션에서 서버와 클라이언트 간의 상호작용을 쉽게 하기 위한 방법으로 사용된다. REST는 특히 확장성과 단순함을 제공하여 현대의 웹 애플리케이션에서 매우 중요한 역할을 한다. 1. REST의 개념과 원리REST는 Representational State Transfer의 약자로, 자원(Resource)을 HTTP URI로 식별하고, 해당 자원에 대한 상태 정보를 HTTP 메서드로 처리하는 구조이다. REST는 주로 웹 애플리케이..
해시 테이블(Hash Tables) 해시 테이블(Hash Tables) 개요해시 테이블은 키(key)-값(value) 쌍을 저장하는 자료구조이다. 키를 해시 함수(hash function)를 통해 특정한 인덱스로 변환하여, 배열과 같은 자료구조에 값을 저장한다. 해시 테이블의 주요 장점은 빠른 데이터 검색, 삽입, 삭제이다. 평균적으로 O(1) 시간 복잡도를 가지기 때문에 효율적이다.하지만 해시 테이블에서 중요한 문제는 충돌(collision)이다. 충돌은 두 개 이상의 서로 다른 키가 동일한 해시 값을 갖게 되어 동일한 인덱스에 저장하려고 할 때 발생한다. 이 문제를 해결하기 위해 여러 가지 기법이 사용된다. 충돌 처리 기법충돌을 처리하기 위한 대표적인 방법으로 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)이 있..
728x90

티스토리툴바