IT 기획의 길

알고리즘 설계 1. A배열을 오름차순해서 정렬하고 2. B배열을 내림차순으로 정렬해서 3. A배열의 가장 큰값과 B배열의 가장 작은값을 곱하고 A배열의 그 다음 큰값과 B배열의 그 다음 작은값을 곱하는식으로 계산을하면 S는 최솟값이 된다 import java.util.*; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int N=scan.nextInt(); int sum=0; ArrayList A=new ArrayList(); ArrayList B=new ArrayList(); for(int i=0;i

알고리즘 설계 1.x좌표 y좌표니까 이차원 배열로 접근한다 2. 정렬 기준이 (1) x좌표로 오름차순 정렬 (2) x좌표가 같으면 y좌표 오름차순 정렬 2개이므로 comparator를 활용한다 import java.util.Scanner; import java.util.*; import java.util.Arrays; public class 좌표정렬하기 { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int num=scan.nextInt(); int [][] pos=new int[num][2]; for(int i=0;i

알고리즘 설계: 1. 같은 단어가 여러 번 입력된 경우 한번만 출력되게 하려면 중복을 허용하지않는 set을 사용한다 2. 출력을 할때 길이 순으로 오름차순 정렬을 한다 3. 만약 길이가 같은 문자라면 사전 순으로 출력한다 import java.util.*; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); HashSet str1=new HashSet(); for(int i=0;is2.length()) //문자 길이로 정렬 return 1; else if(s1.length()

알고리즘 설계: 1. 먼저 사람의 수를 입력받는다. 2. 각 사람의 인출 시간과 각 사람의 앞사람의 인출시간까지 고려한 인출시간을 구하는 배열을 정의한다 3. 적게 걸리는 사람부터 줄 서는게 각 사람의 앞사람의 인출시간까지 고려한 인출시간을 최소로 만든다 4. 각 사람의 인출시간을 입력으로 받고 그 값을 배열에 담아 오름차순으로 정렬한뒤 그 값에 따라 각 사람의 앞사람의 인출시간까지 고려한 총 인출시간을 구한다 import java.util.*; public class ATM { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int time[]=new int[n]; //각 ..

퀵정렬: 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬하는 방법 -> 특정한 값 피벗(Pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다 EX) (3) 7 8 1 5 9 6 10 2 4 3을 피벗으로 지정 3보다 큰 숫자를 왼쪽에서 찾고 3보다 작은 숫자를 오른쪽부터 찾는다. 3보다 큰 수: 7 3보다 작은 수: 2 이때 큰값과 작은 값의 위치를 바꿔준다 (3) 2 8 1 5 9 6 10 7 4 3보다 큰 수: 8 3보다 작은 수: 1 (3) 2 1 8 5 9 6 10 7 4 3보다 큰 수: 8 3보다 작은 수: 1 이때 큰값의 인덱스와 작은값의 인덱스가 엇갈린다 이럴때는 피벗값(3)과 작은값(1)을 바꿔준다 1 2 (3) 8 5 9 6 10 7 4 ..

삽입정렬: 필요할때만 적절한 위치에 삽입하는 정렬 (앞의 요소들은 정렬이 되어있다고 가정한다) Java code import java.util.*; public class InsertionSort { public static void main(String[] args) { int i,j,temp; int []arr= {1,10,5,8,7,6,4,3,2,9}; for(i=0;iarr[i+1]) { //앞의 원소가 뒤의 원소보다 작을때 까지 while문 실행 temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; i--; } } for(int k=0;k

버블정렬: 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 정렬 Java code import java.util.*; public class BubbleSort { public static void main(String[] args) { int i,j,temp; int []arr= {1,10,5,8,7,6,4,3,2,9}; for(i=0;i 이때 9개의 데이터를 탐색한다 .... 이런식으로 실행하면 버블정렬은 10+9+8+ ...+2+1=N(N*1)/2=O(N^2)의 시간복잡도를 갖는다 선택정렬같은 경우는 탐색을 다 마친후에 최솟값만 맨앞으로 가져오면 되지만 버블정렬은 배열의 현재 요소와 뒤의 요소를 비교할때마다 뒤의 요소가 더 작으면 현재 요소와 교체해야 된다(매우 비효율적) ->시간복잡도는 선택..

import java.util.Scanner; import java.util.HashSet; public class 수찾기해쉬 { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); //첫번째 case 입력 HashSet set=new HashSet(); for(int i=0;i

알고리즘: 문자열