aeightchill

🗂️ 문제 17270. 연예인은 힘들어📌 PointDijkstra그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용한다. 특징음(-)의 간선이 없을 때 정상적으로 동작‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신 작동 방식출발 노드를 설정한다.최단 거리 테이블을 초기화한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.위 과정에서 3번과 4번을 반복한다. 📄 코드import heapq # 우선순위 ..

OSI 7계층네트워크 통신이 이뤄지는 과정을 7단계로 나눈 네트워크 표준 모델  7계층으로 나누는 이유특정한 곳에 이상이 생기면 이상이 생긴 단계만 수정할 수 있기 때문이다.    1. 물리 계층 (Physical layer)리피터, 케이블, 허브 등단지 데이터를 전기적인 신호로 변환해서 주고받는 기능을 진행하는 공간데이터를 비트(bit) 단위의 0과 1로 변환한 후 장비를 사용해 전송하거나 전기 신호를 데이터로 복원한다.  2. 데이터 링크 계층 (Data Link layer)브릿지, 스위치, 이더넷 등물리 계층으로 송수신되는 정보를 관리하여 안전하게 전달되도록 도와주는 역할데이터 흐름을 관리하며 데이터의 오류 검출 및 복구 등을 수행한다.MAC 주소를 통해 통신한다.  3. 네트워크 계층 (Netwo..

🗂️   문제 17609. 회문📌   PointTwo Pointer 문자열이 회문인지 확인하기 위해서는 문자열이 대칭인지를 확인해야 한다.대칭인지를 확인하기 위해 첫 번째 문자와 마지막 문자에 각각 포인터를 두고 중간 문자까지 각 포인터가 가리키는 문자가 같은지 확인한다. https://youngone-kang.tistory.com/30 [Algorithm] Two Pointers (투 포인터)Two Pointers리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. (응용문제) _ 특정한 합을 가youngone-kang.tistory.com     📄   코드def main(): T = int(i..

이진 탐색검색 간격을 반으로 반복적으로 나누어 정렬된 배열로 사용하는 알고리즘대상 요소와 검색 공간의 중간 값을 비교하여 검색 간격을 절반으로 줄임.  ✍🏻  동작 예시index0123456789 -5-2012456710Low   Middle    High-5-2012456710     Low Middle High-5-2012456710        LowMiddleHigh   이진 검색 알고리즘 적용 조건데이터 구조를 정렬데이터 구조의 모든 요소에 액세스하려면 일정 시간 소요   작동 방식배열의 중간 요소를 Key와 비교한다. (Key는 찾고자 하는 요소)키를 찾으면 프로세스 종료키를 찾지 못한 경우 다음 공간으로 탐색할 배열의 절반을 선택한다.키가 중간 요소보다 작으면  →   중간을 기준으로 왼쪽..

깊이 우선 탐색 (Depth-First Search, DFS)루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 방법 (스택 or 재귀함수를 통해 구현) 가능한 한 깊이 내려가면서 탐색을 진행한다.특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다. def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)visited = [False] * ndfs(graph, 1, visited)      너비 우선 탐색 (Breadth-First Search, BFS)루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 ..

계수 정렬 (Counting Sort)계수 정렬은 비교하지 않는 정렬 알고리즘으로 데이터의 개수를 세서 정렬하는 방식. 정렬하려는 데이터의 범위를 인덱스로 갖는 빈 배열을 생성한다.데이터 범위가 0 ~ 99까지라면 크기가 100인 빈 배열을 생성한다.정렬하려는 배열을 순회하면서 데이터에 해당하는 인덱스의 값을 1씩 증가한다. 제약 조건데이터의 범위가 0 또는 양의 정수여야 한다. 예시배열 [8, 3, 9, 2, 3, 4, 0, 5]를 계수 정렬하는 과정. 정렬하려는 배열 : 83923405계수 배열 :1012110011인덱스 ↑0123456789최종 배열 : 02334589 시간 복잡도  :  O(n + k)   * 데이터의 개수 : n , 데이터의 최댓값 : k  (데이터의 최댓값이 무한대에 수렴하면 ..

기수 정렬 (Radix Sort)기수 정렬은 비교하지 않는 정렬 알고리즘으로 낮은 자릿수부터 정렬을 수행. 숫자별로 버킷(bucket)이라는 queue를 생성정렬하려는 숫자들의 각 자릿수에 해당하는 숫자를 각각의 버킷에 넣어 정렬이를 자릿수만큼 반복한다.   단점버킷을 구성하기 위한 추가 메모리가 필요정렬할 수 있는 데이터 타입이 한정적 예시숫자 배열 [73, 21, 56, 13, 16, 35, 41, 69]를 기수 정렬을 이용해 오름차순으로 정렬하는 과정7321561316354169버킷          0123456789 버킷 4121 1373 351656  690123456789  2141731335561669버킷 1613213541566973  0123456789  1316213541566973 시..

병합 정렬 (Merge Sort)병합 정렬은 재귀를 이용하는 분할 정복 알고리즘. 분할  →   배열을 쪼개는 것.정복  →   분할한 배열을 정렬하면서 하나로 합병하는 것.   작동 방식정렬하려는 배열을 크기가 0 또는 1이 될 때까지 절반씩 분할.분할된 배열은 다시 하나의 배열로 합쳐지면서 정렬.예시배열 [8, 3, 2, 1, 7, 6, 4, 5]가 있을 때 다음과 같은 과정으로 정렬한다. (오름차순)분할8 3 2 1 7 6 4 58 3 2 1  |  7 6 4 58 3  |  2 1  |  7 6  |  4 58  |  3  |  2  |  1  |  7  |  6  |  4  |  5정렬6 7  |  4 5  |  _ _ _ _6 7  |  _ 5  |  4 _ _ _6 7  |  _ _  |  ..

퀵 정렬 (Quick Sort)퀵 정렬은 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 알고리즘.   작동 방식변수 : low low배열의 첫 번째 요소에서 시작피봇보다 작으면 오른쪽으로 한 칸 이동피봇보다 크면 이동 Xhigh배열의 마지막 요소에서 시작피봇보다 크면 왼쪽으로 한 칸 이동피봇보다 작으면 이동 Xlow와 high 둘 다 이동하지 않을 때 두 변수가 가리키는 값을 교환예시배열 [4, 3, 2, 6, 7, 1, 5]가 있을 때 다음과 같은 과정으로 분할한다.분할은 배열의 크기가 1이하가 될 때까지 반복해서 수행한다.1.4326715 pivotlow    high2.4326715 pivotlow    high3.4326715 pivot low  high(이..

삽입 정렬 (Insertion Sort)삽입 정렬은 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식으로 정렬하는 알고리즘.   작동 방식인덱스 i에 있는 a를 정렬할 차례일 때, 인덱스 0부터 i-1까지는 이미 정렬된 상태배열의 정렬된 부분에서 a보다 작거나 같은 수와 a보다 큰 수 사이에 a를 삽입한다.예시배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.5 3 8 1 23 5 8 1 23 5 8 1 21 3 5 8 21 2 3 5 8시간 복잡도 : O(n^2)    * 1 + 2 + ... + (n-2) + (n-1) = n(n-1) / 2   def insertion_sort(arr): n = len(arr) for i in range..