본문 바로가기
728x90

분류 전체보기

 (245)
[백준] 1865번 웜홀 [Python] - 벨만 포드 테스트 케이스의 개수만큼 아래 주어진 정보로 답을 구해야 한다. N개의 지점에 M개의 도로$($무방향$)$와 W개의 웜홀$($단방향$)$이 있다. 도로와 웜홀은 시작 위치, 도착 위치, 소요 시간으로 주어진다. 소요 시간은 0 이상, 10,000 이하인데, 웜홀은 도로와 다르게 소요 시간만큼 시간이 줄어든다. - 음수처럼 생각하면 쉽다. 각 테스트 케이스에서 처음 위치로 되돌아 올 때, 시간이 과거로 갈 수 있다면 YES, 불가능하면 NO를 출력하는 문제 TC N, M, W 도로 정보 M개 웜홀 정보 W개 x TC 수만큼 반복 더보기 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. $(단 도로는 방향이 없으..
[백준] 1238번 파티 [Python] - 데이크스트라 N개의 마을마다 한 명의 학생이 있고, 어느 날 X번 마을에 모여서 파티를 한다. M개의 단방향 도로가 있고, 시작 도시 A, 도착 도시 B, 소요시간 T가 정보로 주어진다. 각 학생이 자신의 마을에서 X 마을에 모여 파티를 참석하고 자신의 마을로 다시 돌아오는 데 드는 최단 이동 소요시간 중 최대 값을 구하는 문제 더보기 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X $(1 ≤ X ≤ N)$번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 $T_{i}$$(1 ≤ Ti ≤ 100)$의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만..
[백준] 11657번 타임머신 [Python] - 벨만 포드 n개의 도시가 있고, 1번 도시에서 나머지 도시로 가는 최소 시간을 구하는 문제 m개의 버스 노선이 시작도시, 도착도시, 시간 정보로 주어진다. 시간은 양수, 0$($순간 이동$)$, 음수$($타임머신$)$일 수 있다. 소요 시간을 음의 무한대로 향하게 할 수 있다면 -1을 출력한다. 그게 아니라면 순서대로 소요시간을 출력하고, 해당 도시로 가는 경로가 없는 경우는 시간 대신 -1을 출력한다. 더보기 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C ..
[백준] 11404번 플로이드 [Python] - 플로이드 워셜 n개의 도시가 있고, a 도시에서 b도시로 가는 최소 비용을 구하는 문제 m 개의 버스 노선이 출발 도시, 도착 도시, 비용으로 주어진다. $($똑같은 노선은 존재하지 않는다.$)$ nxn 행렬로 답을 구하면 된다. $($i, j$)$ 값은 i 도시에서 j 도시로 가는 비용을 의미한다. 더보기 문제 n$(2 ≤ n ≤ 100)$개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m$(1 ≤ m ≤ 100,000)$개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 $($A, B$)$에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. ..
[백준] 1967번 트리의 지름 [Python] 트리$($tree$)$는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 더보기 문제 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다. 트리의 노드는 1부터 n까지 번호가 매겨져 있다...
[프로그래머스] Lv.3 등산코스 정하기 [Python] N 개의 지점은 출입구, 쉼터, 산봉우리로 이루어져 있습니다. 이 문제에서 출입구에서 산봉우리를 하나만 거처 다시 출입구로 돌아가는 경로를 등산코스라고 정의합니다. 한 등산코스 내 각 지점 사이의 최대 소요시간을 해당 등산코스의 intensity라고 합니다. 가능한 등산코스 중 최소 intensity와 그 값을 갖는 산봉우리를 구하는 문제 더보기 문제 설명 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현..
[프로그래머스] Lv.2 두 큐 합 같게 만들기 [Python] 두 개의 큐가 주어지면 다음 작업을 통해 각 큐의 합이 서로 같게 만드는 최소 횟수를 구하는 문제 작업: 한 큐의 첫 원소를 다른 큐의 마지막 원소로 옮기는 작업을 한 횟수로 취급 더보기 문제 설명 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출$($pop$)$하고, 추출된 원소를 다른 큐에 집어넣는$($insert$)$ 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다. 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면..
[백준] 1753번 최단경로 [Python] - 데이크스트라 방향 그래프의 정점 V개에 대해서 간선 E개의 정보가 시작점, 도착점, 가중치 순서로 주어질 때, 시작 정점 K에서 출발해서 첫번재 노드 부터 V 번째 노드까지의 최단 경로의 가중치를 구하는 문제 자기 자신은 0, 경로가 존재하지 않는 경우에는 INF 출력 더보기 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. $(1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)$ 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각..
[백준] 15686번 치킨 배달 [Python] - 백트래킹 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리 도시의 치킨 거리: 모든 집의 치킨 거리의 합 치킨 거리는 맨해튼 거리(Manhattan distance) 또는 택시 거리로 구한다. 초록색: 유클리드 거리 / 나머지: 맨허튼 거리 N과 M이 주어지고 N개의 숫자가 N줄로 주어질 때, 아래 조건에 따라 도시의 치킨 거리의 최솟값을 구하는 문제 숫자는 NxN 크기의 마을에 대한 정보로 0은 빈 칸, 1은 집, 2는 치킨집을 의미함 치킨 집을 최대 M만 고르고 나머지는 폐업해야한다. 더보기 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 $(r, c)$와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸..
[백준] 13549번 숨바꼭질 3 [Python] - 데이크스트라 N을 아래 연산을 통해서 K로 바꾸는 데 걸리는 시간을 구하는 문제 연산 : 소요 시간 +1 또는 -1 : 1초 x2$($2배$)$ : 0초 더보기 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N$(0 ≤ N ≤ 100,000)$에 있고, 동생은 점 K$(0 ≤ K ≤ 100,000)$에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 ..
운동 구분, 자세 평가 및 카운팅 with Yolov8-pose, LSTM 집에서 운동할 때, 올바른 자세를 확인하고, 잘못된 자세를 피해서 부상을 줄일 수 없을까 생각하고, 이 프로젝트를 하게되었습니다. Yolo로 키포인트를 잡고, LSTM으로 운동을 분류하고, Python으로 함수를 짜서 아래 기능을 구현했습니다. 향후 운동은 사용자 선택, 웹 또는 앱에서 사용할 수 있는 형태로 다른 기능을 추가해서 개발하려고 하고 있습니다. AI Hub 데이터로 학습했고, 아래 영상은 직접 촬영한 영상입니다.
[백준] 12865번 이진 검색 트리 [Python] 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제 이진 검색 트리 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 후위 순회: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 더보기 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 $($루트-왼쪽-오른..

티스토리툴바