우노

문제 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. '팀 합치기' 연산은 두 팀을 합치는 연산이다. ‘같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1

위상 정렬 알고리즘이란? 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미합니다. 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (o) 자료구조 → 고급 알고리즘 → 알고리즘 (x) 진입차수와 진출 차수 진입 차수(Indegree) 특정한 노드로 들어오는 간선의 개수 진출 차수(Outdegree) 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 세부 동작 과정 진입차수가 0인 모든 노드를 큐에 넣습니다. 큐가 빌 때까지 다음 과정을 반복합니다. 큐에서 원소를 꺼내, 해당 노드에서 나가는 모든 간선을 그래프에서 제거합니다. 새롭게 진입차수가 0이 된 노드를 큐에 넣습니다. 결..

신장 트리란? 신장 트리는 그래프 알고리즘 문제로 자주 출제되는 문제 유형입니다. 신장 트리란, 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 합니다. 따라서, 이러한 그래프를 신장 트리라고 부릅니다. 크루스칼 알고리즘이란? 예를 들어, N개의 도시가 존재하는 상황에서, 각각의 도시 사이에 도로를 놓아, 전체 도시가 서로 연결될 수 있도록 도로를 설치할 때, 최소한의 비용으로 모든 도시를 연결하기 위해선 어떤 알고리즘이 사용되어야할까요? 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 ‘최소 신장 트리 알고리즘' 이라고 하며, 대표적인 ..

주요 개념 서로소 집합은 크루스칼 알고리즘에 핵심 개념으로 사용됩니다. 서로소 집합은 공통 원소가 없는 두 집합을 의미합니다. 예를 들어, 집합 {1, 2} 와 {3, 4} 는 서로소 관계입니다. 서로소 집합은 2가지 연산(union, find)으로 조작할 수 있습니다. union 연산은 2개의 부분 집합을 하나의 집합으로 합치는 연산입니다. find 연산은 특정한 원소가 어떤 집합에 속해있는지 알려주는 연산입니다. 따라서, 전체 요소들이 주어졌을 때, 전체 요소들이 어떤 형태의 부분 집합으로 나누어지는지 확인하고 싶을 때 사용하는 개념입니다. 서로소 집합 자료구조의 동작 과정 여러 개의 Union(A, B) 연산이 주어집니다. 순서대로 Union(A, B) 연산을 진행합니다. find 를 사용해, A와..

트리와 그래프의 구조 트리 방향성 : 방향 그래프 순환성 : 비순환 루트 노드 존재 여부 : 존재함 노드간 관계성 : 부모와 자식 관계 있음 모델의 종류 : 계층 모델 그래프 방향성 : 방향 그래프 혹은 무방향 그래프 순환성 : 순환 및 비순환 루트 노드 존재 여부 : 존재하지 않음 노드간 관계성 : 부모와 자식 관계 없음 모델의 종류 : 네트워크 모델 참고 이것이 취업을 위한 코딩테스트다. with Python https://kangworld.tistory.com/37

들어가기 앞서, 해당 포스팅에선, edge tpu 내부 컨테이너에서, 이미지 추론을 진행하기 위해 설치해야했던 라이브러리들의 설치 코드를 정리합니다. libedgetpu1-std (v15.0) python3-edgetpu(v15.0) tflite-runtime (v2.1.0) 설치 이후, 반드시 컨테이너를 재부팅해야 라이브러리들이 정상적으로 적용됩니다. 그럼에도 불구하고 적용이 안된다면, Coral USB를 다시 연결하거나, 호스트(해당 실험에선 라즈베리파이)를 재부팅해야합니다. 라이브러리 설치 코드 # Install Edge TPU Libraries echo "deb https://packages.cloud.google.com/apt coral-edgetpu-stable main" | tee /etc/..

문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌..

문제 방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 ..

플로이드 워셜(Floyd-Warshall) 알고리즘이란? 플로이드 워셜 알고리즘은 ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘입니다. 해당 알고리즘은 매 단계마다 ‘현재 노드를 거쳐 가는 노드'를 기준으로 알고리즘을 수행합니다. 노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 통해 현재 노드를 선택하며, 단계마다 O(N^2)의 연산을 통해 ‘현재 노드를 거쳐 가는' 모든 경로를 고려합니다. 따라서, 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)입니다. 해당 알고리즘은 2차원 리스트에 ‘최단 거리' 정보를 저장한다는 특징이 있습니다. 모든 노드가 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문입..

들어가기 앞서 heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공합니다. 통상적으로 heapq 가 PriorityQueue 보다 더 빠릅니다. 해당 포스팅에선, heap 사용법에 대해서만 간단히 다뤄보겠습니다. heapq 에 튜플이 삽입될 경우엔, 튜플의 첫 번째 요소가 정렬의 기준이 됩니다. 예제 코드 import heapq # 기본 배열 생성 q = [] # 우선순위 큐에 요소 삽입 heapq.heappush(q, (4, 10)) heapq.heappush(q, (1, 10)) heapq.heappush(q, (3, 10)) heapq.heappush(q, (2, 10)) print(q) # [(1, 10), (2, 10), (3, 10), (4, 1..