BFS(너비 우선 탐색) 너비 우선 탐색은 루트 노드 (혹은 임의의 노드)에서 시작해서 인접한 노드들을 우선으로 방문하여 탐색하는 알고리즘이다.  가능한 한 넓게 탐색을 진행하는 방식이다. BFS의 동작 방식시작 노드 선택탐색할 노드를 선택하고 해당 노드를 큐에 추가방문 및 큐 연산큐에서 노드를 꺼내고 방문 처리현재 방문중인 노드의 인접 노드들을 확인하여 방문되지 않았다면 큐에 추가반복큐가 비어 있지 않는 동안 위 과정을 반복수행큐가 비었다면 탐색이 완료됨을 의미탐색 종료모든 노드를 방문하거나, 특정 조건을 만족하는 노드를 찾으면 탐색이 종료됨. BFS는 Queue 자료구조를 사용하여 구현한다. BFS 구현 예시인접 리스트로 표현된 그래프가 있다고 하자graph = { 'A': ['B', 'C'],..

DFS ( 깊이 우선 탐색 ) 깊이 우선 탐색은 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기에 대한 탐색을 완전히 끝내고 다음 분기로 넘어가는 방식의 탐색을 의미한다. 가능한 한 방향으로 깊게 내려가며 노드를 탐색한다. DFS의 동작 방식시작 노드 선택탐색을 시작할 노드를 선택방문 및 기록현재 노드를 방문하고, 방문을 기록( 중복 방문 방지)자식 노드 탐색현재 노드에 연결된 인접 노드 중 아직 방문하지 않은 노드가 있다면 그 노드로 이동하여 탐색 진행백트랙킹더 이상 탐색을 진행할 수 없는 경우(현재 노드의 인접 노드를 모두 방문) 이전 단계의 노드로 되돌아감이 과정을 반복하며 탐색을 진행탐색 종료모든 노드를 탐색했거나, 특정 조건을 만족하는 노드를 찾은 경우 탐색을 종..

백트랙킹(Backtracking) 이란?백트래킹은 한정 조건에 대해 해를 찾는 탐색 및 최적화 문제의 해결 전략이다. 백트래킹은 모든 경우에 대해 탐색을 수행하는 과정에서 불필요한 경로는 배제하여 효율성을 높이는 방식으로 동작한다. 한정조건에 대해서 경우의 수를 시도하기 때문에 단순 다중 for문을 사용하는 것보다 효율적으로 동작한다.  Backtracking의 문제 해결 전략문제를 풀기 위한 모든 가능한 해의 조합을 정의함각 단계에서 현재 상태가 문제의 한정 조건을 만족하는 지 검사하고, 해가 될 수 없는 경로라면 가지치기를 통해 정답 경로에서 배제함정답이 될 수 있는 경로를 따라 재귀적으로 진행을 한다. 특정 경로가 조건을 만족하지 못하면 이전 단계로 돌아가 경로를 탐색함 탐색하다가 문제를 해결하면 ..

다익스트라 알고리즘 (Dijkstra Algorithm)다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘이다. 다익스트라 알고리즘 탐색 과정[step 1] 출발 노드와 도착 노드를 설정[step 2] 출발 노드를 기준으로 각 노드의 최소 비용을 저장 ( 갈 수 없다면 INF로 설정)[step 3] 방문하지 않은 노드 중에서 비용이 가장 적은 노드를 선택[step 4] 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려하여 최소 비용 갱신[step 5] 3,4 과정을 반복 다익스트라 알고리즘 탐색 예시이차원 배열 형태로 그래프를 처리출발/도착12345610251INFINF2INF032INFINF3INF30INFINF54INFINF301INF5INFINF1INF026INFIN..

플로이드 워셜 알고리즘 (Floyd - Warshall Algorithm)Floyd - Warshall Algorithm은 그래프에서 가능한 모든 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘 양의 간선들에 대해서 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘2024.08.18 - [🤔알고리즘] - [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)다익스트라 알고리즘 (Dijkstra Algorithm)다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘이다. 다익스트라 알고리즘 탐색 과정[step 1] 출발 노드와 도착yobi-devlog.tist..

힙큐(heapq)는 파이썬 표준라이브러리가 제공하는 모듈로 Heap 자료구조를 지원한다. 완전 이진트리 형태를 하고 있으며, 최솟값과 최댓값을 빠르게 찾을 수 있다 . 파이썬은 기본적으로 최소힙(min-heap)을 제공한다. (부모 노드의 값은 자식 노드의 값보다 작거나 같다.)주요 메소드heapq.heappush(heap, item)힙의 조건을 유지하면서 item을 heap에 push 해준다. ( O(logn) )import heapqheap = []for i in range(10): heapq.heappush(heap, i)print(heap)## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]heapq.heappop(heap)힙에서 가장 작은 요소를 제거하고 반환함.  ( O(logn)..

itertools 라이브러리를 사용하면 효율적으로 순열과 조합을 구현할 수 있다. permutations( ) - 순열순열은 서로 다른 n개의 다른 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관 있게 r개의 원소를 선택하거나 나열하는 것을 의미한다. import itertoolsarr = ['A', 'B', 'C', 'D']nPr = itertools.permutations(arr, 2)print(list(nPr))"""[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]"""combination..

알고리즘 문제를 풀다보면 시간 제한이라는 벽을 마주하게 된다. Python은 입력을 받기 위해 input()과 sys.stdin.readline()을 사용하는데 sys.stdin.readline()을 사용하면 더 빠르게 입력을 처리할 수 있다.  Input( ) vs sys.stdin.readline( )input( )input( ) 은 자동으로 개행 문자를 제거한다. (입력받은 문자열에 개행 문자만을 제거하여 줄 바꿈 없이 출력함)상대적으로 느리다. 더 이상 입력이 없는 경우에 실행되면 EOF 에러를 출력한다. sys.stdin.readline( )sys.stdin.readline( )은 개행 문자를 포함하여 반환한다.상대적으로 빠르다.EOF를 만나도 에러를 반환하지 않고 빈 문자열을 반환한다. sys..

배열(Array)배열의 장단점은? 장점 인덱스를 이용한 빠른 접근(O(1)) 연속된 공간을 사용해서 메모리 효율성이 좋다. 단점 데이터가 순차적으로 존재해서 중간에 요소가 삽입되거나 삭제되는 경우 뒤에 있는 모든 요소들을 한칸씩 움직여줘야 한다. O(n) 배열과 연결리스트의 차이점배열은 고정된 크기의 연속된 메모리 블록을 사용하지만, 연결 리스트는 동적으로 크기가 변할 수 있는 노드들의 연결로 이루어져 있다. 배열은 인덱스를 통해 O(1) 의 시간 복잡도로 요소에 접근할 수 있지만, 연결 리스트는 특정 요소에 접근하기 위해 O(n)의 시간 복잡도가 필요하다. 삽입과 삭제에 배열은 각 원소들을 옮겨주어야 해O(n)의 시간 복잡도가 필요하지만, 연결 리스트는 O(1)의 시간 복잡도가 필요하다. 연결리스트(L..

운영체제의 주요 기능은? 운영체제는 컴퓨터 하드웨어 소프트웨어 자원을 관리하며 컴퓨터와 사용자 사이의 인터페이스를 제공한다. 주요 기능 프로세스 관리 : 프로세스의 생성, 스케줄링 등을 담당 메모리 관리 : 메모리 할당, 해제, 스왑핑 등을 관리. 가상 메모리, 페이징, 세그멘테이션 기법등을 사용 파일 시스템 관리 : 파일 및 디렉터리 구조를 제공. 파일 저장, 검색, 삭제등의 작업을 수행 입출력 시스템 관리 : 다양한 입출력 장치와 상호작용을 관리 메모리의 구조메모리는 크게 Code, Data, Heap, Stack영역으로 이루어져 있습니다. 프로세스와 스레드의 차이프로세스는 실행중인 프로그램의 인스턴스로 별도의 메모리 공간을 가진다. 각 프로세스는 자체 주소 공간을 가지고 있어 다른 프로세스와 독립적..