딩동댕 코딩유치원

문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 입력 예제 7 1 6 6 3 3 5 4 1 2 4 4 7 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 출력 예제 4 6 1 3 1 4 1 1 2 3 3 4 4 5 5 6 6 문제 풀이 루트노드가 1부터 시작하므로, 노드1에서 탐색을 시작한..

문제 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나..

연결요소 (Connected Component)란? 정점사이에 겹치는 정점이 있는 연결되어 있는 그래프로 왼쪽의 연결요소 개수는 2개, 오른쪽의 연결요소 개수는 3개이다. 연결요소가 성립될 수 있는 조건은 두 가지가 있다. 하나의 연결요소에 속한 모든 정점을 연결하는 경로가 있어야 한다. 다른 연결요소와 같은 정점을 경유하면 안된다. 연결요소는 DFS나 BFS탐색을 통해 구할 수 있다. 문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 입력 첫째..

문제 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 입력 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는..

문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 입력 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다. 출력 첫째 줄에 장마철에 물에 잠기지 않는 안전한 영..

문제 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 입력 첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다. 둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다. 출력 첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다. 입력 예제 6 8 4 5 3 2 4 0 4 1 4 2 1 1 5 6 1 3 6 2 3 2 6 3 4 4 출력 예제 5 문제 풀이 전형적인 다익스트라 알고리즘 문제 최소 여물이 있는 경로로 갱신해가며 이동한 후, 각 값을 갱신 해 놓은 distance 리스트에서..

문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 입력 첫째 줄에 방의 크기 N과 M이 입력된다. 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0인 경우 북쪽, 1인 경우 동쪽,2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다. 셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i,j)의 상태를 나타..

문제 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 입력 정수 a,b,c,d,e,f 가 공백으로 구분되어 차례대로 주어진다. (−999 ≤ a,b,c,d,e,f ≤ 999$-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 (x , y)가 유일하게 존재하고, 이 때 x와 y가 각각 −999이상 999이하의 정수인 경우만 입력으로 주어짐이 보장된다. 출력 문제의 답인..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문자열을 압축하는 최대 길이는 len(s) // 2 이므로 하나부터 len(s) // 2 의 길이만큼 차례대로 잘라 가면서 앞 뒤 문자열이 같은지 하나씩 확인한다. 앞 뒤 문자열이 같다면 반복되는 문자열 횟수와 문자열을 붙인다. 앞 뒤 문자열이 같지 않다면 숫자 없이 문자열을 붙인다. 남은 마지막 문자열에 대한 처리 또한 위와 같이 한 후, 문자열을 압축할 때 마다의 길이를 하나씩 확인하여 최소 길이를 출력 코드 s = 'abcabcdede' def solution(s): result_len ..

문제 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 입력 첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤5000,1≤m≤100,000) 다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다. (1≤a,b≤n,1≤c≤100,a≠b) 다음 줄에는 두 정점 s,t가 주어진다. (1≤s,t≤n,s≠t) 모든 간선을 연결하면 그래프는 연결 그래프가 됨이 보장된다. 출력 s와 t가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오, 입력 예제 8 9 1..