TEAM EDA

정원이는 같은 반 친구들에게 소문내는 것을 좋아합니다. 자기가 하고 싶은 이야기를 주변 친구들에게 퍼뜨리는 것을 즐겨하는데, 소문은 친구의 친구를 통해서 빠르게 퍼져서 결국 연결된 친구들은 이를 모두 알게 됩니다. 예를 들어 정원이네 반 학생 7명의 친구관계가 과 같다고 해봅시다. 이 그림에서 친구끼리는 연결선으로 연결되어 있고, 친구가 아니면 연결되어 있지 않습니다. 이 네트워크 상에서 정원이가 1번이라면, 소문은 2번과 5번 친구를 거쳐 결과적으로 2, 3, 5, 6번 학생이 소문을 듣게 됩니다. 하지만, 4번과 7번 학생은 이들과 친구가 아니기 때문에 소문을 들을 수 없습니다. 정원이가 1번이라고 가정할 때, 같은 반 학생(노드) 수와 친구관계(간선) 정보가 주어질 때, 정원이에 의해서 이야기를 듣..

유치원 소풍 상훈이는 엘리스 유치원 선생님입니다. 엘리스 유치원 학생들은 다 같이 어은동산으로 소풍을 갔습니다. 그런데 엘리스 유치원 학생들은 서로 파벌이 나뉘어 있어서 절대로 다른 조직과는 점심을 같이 먹지 않습니다. 상훈 선생님은 점심을 먹는 애들을 보면서 어느 조직에 몇명이 있는 지를 알려고 합니다. 여러분은 점심을 먹는 학생들의 지도를 바탕으로 어느 조직에 몇 명이 있는지 알아내면 됩니다. 학생들은 다음과 같이 앉아 있습니다. 다음과 같이 파벌이 나뉩니다. 여러분이 출력해야 할 것은 파벌이 몇 개 있는지, 그리고 각 파벌에는 몇 명이 있는 지를 오름차순으로 정리한 결과입니다. 입력 첫째 줄에는 지도의 크기가 주어집니다. 지도는 항상 정사각형입니다. 두 번째 줄부터 지도의 정보가 주어집니다. 1은 ..

팰린드롬 만들기 팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “aba”, “abdba”, “abffba” 는 모두 팰린드롬이다. 임의의 문자열이 주어질 때, 몇 개의 문자를 적당히 삭제하면 이를 팰린드롬으로 만들 수 있다. 예를 들어, "abca"가 주어질 경우, 알파벳 'b’를 삭제하면 "aca"가 되므로, 팰린드롬으로 만들 수 있다. 임의의 문자를 제거함으로써 주어진 문자열을 팰린드롬으로 만들고 싶다고 할 때, 제거해야 하는 문자의 최소 개수를 출력하는 프로그램을 작성하세요. 입력 첫 번째 줄에 문자열이 주어진다. 문자열의 길이는 3000을 넘지 않는다. 출력 팰린드롬을 만들기 위해 제거해야 하는 문자의 개수의 최솟값을 출력한다. 입력 예시 1 abcfba 출력 예시..

두 문자열 사이의 거리 두 문자열 s1, s2가 주어진다. 이제 s1에서 문자 하나를 추가하거나 제거할 수 있으며, 이를 반복함으로써 s2를 얻고싶다고 하자. 예를 들어, s1 = “abc”, s2 = “bdcf” 라고 하면, s1에서 a를 제거하고 d를 추가, 그리고 f를 추가하면 s2를 얻을 수 있다. 즉, 다음과 같은 경로로 s1에서 s2를 얻을 수 있다. $“abc” -> “bc” -> “bdc” -> “bdcf”$ 두 문자열 s1, s2 사이의 거리란, s1에서 s2를 만들기 위해 필요한 문자 삽입, 삭제 횟수의 최소값으로 정의된다. 예를 들어, s1 = “abc”, s2 = "bdcf"라면, 두 문자열의 거리는 3이다. 왜냐하면, s1에서 문자의 추가 및 삭제를 3번 하면 s2를 얻을 수 있기..

최대 공통 부분 수열 두 개의 문자열 s1, s2 가 주어질 때, 공통 부분 수열이란, s1과 s2가 공통으로 갖는 부분 수열을 일컫는다. 예를 들어, s1 = “Television”, s2 = "Telephone"이라고 하면, s1과 s2의 공통 부분 수열이 될 수 있는 문자열은 “T”, “To”, “Teln” 등이 있다. 최대 공통 부분 수열이란, 공통 부분 수열 중에서 그 길이가 최대인 것을 일컫는다. 예를 들어, s1 = “Television”, s2 = "Telephone"이라고 하면, 그 최대 공통 부분 수열은 "Teleon"으로써, 그 길이는 6이다. 두 개의 문자열이 주어질 때, 최대 공통 부분 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 문자열 s1, 두 번째 줄에 문..

N-Queen n x n 의 체스 판에 n개의 Queen을 놓으려 합니다. 이 때, 다음의 규칙을 반드시 따라야 합니다. 같은 행에 2개 이상의 Queen이 존재해서는 안됩니다. 같은 열에 2개 이상의 Queen이 존재해서는 안됩니다. 하나의 대각선에 2개 이상의 Queen이 존재해서는 안됩니다. 이는 ‘’ 방향의 대각선과 ‘/’ 방향의 대각선 모두에 대하여 해당되는 조건입니다. 예를 들어 n = 4 일 경우, 아래와 같이 Queen을 배치하는 것은 가능하지 않다. 왜냐하면 다음과 같이 조건 1, 그리고 조건 3에 반하기 때문이다. n = 4 일 경우에는 다음과 같이 Queen 을 배치할 수 있는 경우가 2가지 존재한다. n이 주어질 때, nn개의 Queen을 배치할 수 있는 경우의 수를 출력하는 프로그..

가로수 직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져 있습니다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있습니다. KOI 시에서는 예산 문제로 가능한 한 가장 적은 수의 나무를 심고 싶습니다. 편의상 가로수의 위치는 기준점으로부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수입니다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 됩니다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 합니다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새..