최장 공통부분 수열은(LCS, Longest Common Subsequence) 여러 개의 수열이 주어졌을 때 두 수열의 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 방법이다. 구하는 방법은 하나의 수열을 순서대로 다른 수열의 모든 문자와 비교하여 같은지 비교하는데, 동적 계획법(DP)을 활용하여 문제를 푼다. 1. 만약 같다면 현재 비교하고 있는 [n][n] 번 위치의 문자 이전에 매치됐던 [n-1][n-1] 번 위치에 있는 문자에 더한다. 2. 만약 다르다면 비교하기 이전에 나왔던 가장 긴 길이를 갖도록 하기 위해서 [n][n-1] 위치의 값과 [n-1][n] 위치의 값을 비교하여 큰 값을 가진다. 3. 배열의 최종 위치의 숫자는 가장 긴 수열의 길이를 갖게 된다. 예시: ABCD, BZDCD =..
데이터를 입력받은 후 데이터에서 가야하는 거리를 구한다. 가야하는 거리를 이동하는 최소값은 규칙이 있다. 이 규칙은 1부터 하나씩 최소값을 찾아보면 규칙이 보이고 규칙은 다음과 같다. 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 ... 와 같은 증가 형식을 띄게 된다. 이를 구현한 코드는 아래와 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..
총 데이터의 개수가 주어졌을 때 10 대의 컴퓨터에 차례로 총 데이터를 분산시켰을 때 마지막 데이터의 위치를 구하는 문제이다. 입력 데이터는 테스트 횟수와 테스트 데이터가 순서대로 입력된다. 테스트 데이터는 "A B"와 같은 형식으로 입력된다. 데이터의 총 수는 A에 B승한 것과 같다. (EX: "3 7"은 "3 * 3 * 3 * 3 * 3 * 3 * 3" 와 같고 계산했을 때 "2187"이 나오게 된다.) 데이터의 총 갯수가 몇이던지 10개의 컴퓨터에 분산하여 배분하기 때문에 10으로 나누었을 때 나머지값이 정답이다. 다만 데이터의 총 개수를 먼저 구하게되면 데이터의 수가 많아질 경우 실패하게 된다. 따라서 데이터의 총 개수를 먼저 구하는 것이 아니라 A * A 의 위치를 구한 후 해당 위치의 다음 컴..
퀵 소트(quick sort) ( * 오름차순 기준 * )기준을 잡은 후 기준을 피벗이라고 하자 피벗을 제외한 숫자들을 가지고 정렬하는데 피벗 보다 작다면 왼쪽을 크다면 오른쪽으로 나눈 후 왼쪽과 오른쪽에서 다시 피벗을 잡아 다시 정렬하며 모든 정렬이 끝날 때까지 이를 반복한다. 0. 피벗을 재외한 후 두개의 비교할 값을 정한다.(편의상 l(left)와 r(right)로 칭하겠다.)1. l이 피벗보다 작고 r이 피벗보다 크다면 둘다 새로운 값을 정한다.(l과 r의 값이 같아도 동일하다.)2. l이 피벗보다 크고 r이 피벗보다 작다면 서로 값을 바꾼 후 새로운 값을 정한다.3. l이 피벗보다 작고 r이 피벗보다 작다면 l의 값만 새로 정한다.4. l이 피벗보다 크고 r이 피벗보다 크다면 r..
플로이드 워셜(Floyd Warshall) 알고리즘은 동적 계획법으로 모든 최단 경로를 구하는 알고리즘이다. 먼저 초기화를 해줘야 하는데 최단경로가 있으면 최단경로를 없으면 최댓값을 넣어주어야 한다.그래야 최단경로를 구할 수 있다. 3중 for 문으로 동작하는데 첫 for 문부터 각각 거쳐 가는 점, 출발하는 점, 도착하는 점을 나타낸다.아래 코드는 초기화를 했다는 가정하에 작성했다. class Floyd{ int len = 10; int[][] arr = new int[len][len]; void floyd(){ for(int i = 0; i < len; i++){ // 거쳐가는 점 for(int j = 0; j < len; j++){ // 출발하는 점 if(i == j){ continue; } for..
- 거품 정렬(Bubble sort) ( * 오름차순기준 * ) 인접한 두 원소를 비교하여 정렬하는 방법이다. 원소의 이동이 거품이 수면으로 올라오는 모습을 보이기 때문에 지어졌다고 한다. - ex) 테이블 비교값 5, 3, 2, 1, 4 5, 3 3, 5, 2, 1, 4 5, 2 3, 2, 5, 1, 4 5, 1 3, 2, 1, 5, 4 5, 4 3, 2, 1, 4, 5 3, 2 2, 3, 1, 4, 5 3, 1 2, 1, 3, 4, 5 2, 1 1, 2, 3, 4, 5 -끝- 시간 복잡도 : O(n 제곱)
- 선택 정렬(selection sort) ( * 오름차순 기준 * ) 가장 작은 값을 찾아서 첫번째 위치에 있는 값과 교환하고, 두번째로 작은 값을 찾아 두번째 위치에 있는 값과 교환하는 방법으로 이러한 방법을 반복한다. 즉 최소값을 찾아 왼쪽으로 이동시키는데 배열의 크기만큼 반복하여 정렬하는 방법이다. - ex)테이블 최소값[9,1,6,8,4,3,2,0] 0[0,1,6,8,4,3,2,9] 1[0,1,6,8,4,3,2,9] 2[0,1,2,8,4,3,6,9] 3[0,1,2,3,4,8,6,9] 4[0,1,2,3,4,8,6,9] 6[0,1,2,3,4,6,8,9] 8 시간복잡도 : O(n 제곱)