우노

위상 정렬 알고리즘이란? 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미합니다. 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (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

문제 어떤 나라에는 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차원 리스트에 ‘최단 거리' 정보를 저장한다는 특징이 있습니다. 모든 노드가 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문입..

문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N,M이 주어진다(1

문제 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어, 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다. 입력 조건 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000) 출력 조건 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. 입력 예시 3 출력 예시 5 풀이 왼쪽부터 i-1 까지의 길이가 이미 덮개로 채워져 있으면, i 번째를 채우는 방법은 2 x 1 의 덮개를 채우는 하나의 경우밖에 없습니다. 왼쪽부터 i-2 까지의 길이가 이미 덮개..

문제 개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 ..