TEAM EDA

팰린드롬 만들기 팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “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)에 가로수를 더 심어야 합니다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새..

최대공약수 구하기 두 자연수 x, y의 최대공약수를 출력하는 프로그램을 작성하세요. 이 문제에서는 유클리드 호제법을 이용하여 두 자연수의 최대공약수를 구합니다. 유클리드 호제법을 간단하게 이야기하면 다음과 같습니다. gcd(x, y) 를 x와 y의 최대공약수라고 정의합니다. 그러면 다음의 식이 성립합니다. gcd(x, y) = gcd(y, x%y) 예를 들어, 1071과 1029의 최대공약수는 따라서 다음과 같이 구할 수 있습니다. gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = 21 참고로 gcd(42, 21) = 21 인 이유는, 42가 21로 나누어 떨어지기 때문에 42와 21의 최대공약수는 21이 됩니다. 자세한 설명은 다음의 링크를 참고해주세요. 위의 예제 ..

Quick sort 정의 : 재귀 호출을 이용한 대표적인 정렬 배열 중에 값 하나를 pivot으로 설정한다. pivot과 같거나 작은 값은 왼쪽 배열(left)에 그렇지 않은 값은 오른쪽 배열(right)에 저장한다. 이후, 왼쪽 배열과 오른쪽 배열을 각각 Quicksort를 진행해주면 위와 같이 정렬이 완료된다. 과정을 좀 더 자세히 보기 위해서 왼쪽의 배열 [4, 2, 2, 4, 3, 1]의 Quick Sort 과정을 살펴보자. 먼저, 값 하나를 pivot으로 설정해준다. 설정한 pivot을 기준으로 왼쪽에는 pivot보다 작거나 같은 값을 오른쪽에는 pivot보다 큰 값을 넣어준다. pivot을 설정해준다. pivot을 기준으로 pivot 보다 작거나 같은 값을 왼쪽에, 그렇지 않은 값을 오른쪽에 ..

점토 놀이 엘리스씨는 가장 적은 힘을 사용하여 주어진 모든 점토를 합치고 싶어졌습니다. 엘리스씨를 도와 n개의 점토를 하나의 덩이로 합치기 위해 필요한 힘의 크기의 합의 최솟값을 구하는 프로그램을 작성하세요. 만약 무게가 a인 점토와 무게가 b인 점토를 한 덩이가 되도록 합치기 위해서는 a+b의 힘을 들여야 합니다. [입력값] 〔1〕 점토의 개수 n (1≤n≤100,000) 〔2〕 n개의 숫자(각 점토의 무게) [결과값] 모든 점토를 한 덩이로 합치기 위해 필요한 힘의 크기의 합의 최솟값을 출력합니다. [제한 시간] 5초 이내에 결과가 출력되어야 합니다. [입력 예시] 4 1 5 7 3 [출력 예시] 29 [예시 설명] 4개의 점토가 있고 각각 1, 5, 7, 3의 무게를 가진다면 다음의 순서대로 합치는..

우선순위 큐 정의 : 원소를 제거할 시, 가장 우선순위가 높은 원소를 제거 배열로 구현 삽입 : O(1) 삭제 : O(n) 힙으로 구현 (부모의 값이 항상 자식보다 작은 완전 이진 트리) 삽입 : O(logn) 삽입 : 가장 마지막 노드에 값을 삽입하고 우선순위를 맞게 정렬 - 정렬에 드는 시간 복잡도 O(logn) heap.insert(4)를 통해서 4라는 값을 삽입하려고 함 빈 노드의 위치에 삽입 정렬을 통해 우선순위를 맞춤 삭제 : O(logn) 삭제 : 부모를 삭제하고 남은 노드를 우선순위에 맞게 정렬 - 정렬에 드는 시간 복잡도 O(logn) heap.pop()을 통해서 2를 제거하려고 함 먼저, 2를 제거 가장 마지막 노드에 있는 값을 맨 위의 노드에 삽입 이후, 정렬을 통해서 우선순위를 맞춤..

합계 0인 정수 쌍 구하기 0을 제외한 n개의 정수가 주어졌을 때, 합이 0에 가장 가까운 숫자쌍을 구하는 sum_0(data)을 작성하세요. [입력값] 첫 번째 줄에 n개의 정수들이 오름차순으로 주어집니다. n의 값은 따로 주어지지 않습니다.(1≤n≤100,000,000) [결과값] 합이 0에 가장 가까운 숫자쌍을 빈 칸으로 구분하여 출력합니다. 숫자쌍은 오름차순으로 정렬하여 출력하며, 정답이 여러개일 경우 그 중 하나만 출력하면 됩니다. [입력 예시] -193 30 94 100 194 [출력 예시] -193 194 풀이 "투포인터" 알고리즘 : 1차원 배열이 있고 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 얻는 형태 성립하는 이유 : 배열이 정렬되어 있는 상황이..