개발노동자

문제 가중치 없는 방향 그래프 G가 주어졌을 떄, 모든 정점 (i,j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오 3 0 1 0 0 0 1 1 0 0 풀이 - 인접행렬로 받아 인접행렬로 출력하고, 바로 플로이드 와샬이 떠오르긴 했는데 바로 적용하기가 어려웠다.. 0,0 부분만 0이 출력되는 결과가 나와버려서 해결 못해서 답을 찾아봤다. 결국 arr[2번쨰 for][1번째 for]==1 && arr[1번째 for][3번쨰 for] 가 통과하면 arr[2번쨰 for][3번쨰 for] 로 갈 수 있다는 뜻이므로 arr[2번쨰 for][3번쨰 for]에 1을 넣어주면 정답이다. import java.io.BufferedReader; import java.io.IOExcepti..

문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들도 익을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 ..

문제 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다. 통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2,,4,5,6,9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 2,9,7,4,5의 난이도는 7이다. 우리는 더 나은 배열 2,5,9,7,4 를 만들 수 있으며 이 배열의 난이도는 4이다 이 배열보다 난이도가 낮은 배열은 만들..

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오 풀이 예시 입력을 봤을 때 결국 4개에 중간 값 중 하나일 경우 면 된다. 근데 계속 해보니 중간에 틀리는 결과가 나와 당황 했는데 간단히 생각해보니 주어진 수가 홀수 개이면 가운대 값이 되어야 정답이었다 예를 들어 1,5,6,7,8 이면 답이 6이어야 한다. (4+1+2+4)와 (5+1+1+3)..

문제 석환이는 아기다. 아기 석환이는 자연수가 쓰여져 있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이다! 아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다. 1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. 2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어쓴다. 이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목..

문제 숭실골 높은 언덕 깊은 골짜기에 출제로고통 받는 욱제가 살고 있다! 욱제는 또 출제를 해야해서 단단히 화가났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어버렸다. 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문 Q개가 주어진다. 욱제의 질문에 답하고 함께 엠티를 떠나자! 5 6 2 5 1 4 3 1 5 2 4 3 3 1 3 2 5 4 5 풀이 입력만 보고 바로 손으로 계산해보니 해당 구간에 대한 합을 구하는 것이길래 그대로 코드로 짰더니 12퍼에서 시간초과나서 틀렸다. 일단 시간초과코드 import java.io.BufferedReader; import java.io.IOException; import java...

문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 짖머을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 알 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로 만 이동하여 목표 지점까지 가고자 한다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개술르 구하는 프로그램을 작성하시오, 풀이 DFS를 이용해야하는데 여기서 DP배열을 통해 값을 미리 구한 ..

문제 트리는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트라의 지름은 45가 된다. 풀이 해당 문제를 조금 다르게 보면 9번 노드에서 12번 노드로 향하는 가중치..

문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌 나와 아버지 형제들과 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오 입력 사람들은 1,2,3,. 의 연속된 번호로 각각 표시 된다. 입력파일의 첫째 줄에는 전체 사람의 수 N이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋..

문제 총 N개의 문자열로 이루어진 집합 S가 주어지낟. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오 입력 첫째 줄에 문자열의 개수 N과 M이 주어진다. 다음 N개의 주렝는 집합 S에 포함되어 있는 문자열ㄷ르이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 풀이 HashSet에 N만큼을 담고 M만큼을 순회하며 contains가 true이면 count에 1씩 추가했다. import java.io.BufferedReader; import java.io.IOException; ..