배열문제
배열의 최대값 최소값 찾기
int[]arr = {1,2,3,4,5};
int max=Arrays.stream(arr).max().getAsInt();
int min=Arrays.stream(arr).min().getAsInt();
System.out.println(max);
System.out.println(min);
반복문 활용
int[] arr = {1, 2, 3, 4, 5};
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
if (min > arr[i]) {
min = arr[i];
}
}
중복된 값 찾기
int[] arr = { 1, 2, 3, 3, 4, 4, 5 };
for(int i=0; i<arr.length; i++) {
for(int j=i+1; j<arr.length; j++) {
if(arr[i]==arr[j]) {
System.out.println("중복된갓값:"+arr[i]);
}
배열뒤집기
int[] arr = {1, 2, 3, 4, 5};
int left=0;
int right= arr.length-1;
while(left<right) {
int tmp = arr[left];
arr[left]=arr[right];
arr[right]=tmp;
left++;
right--;
}
System.out.println(Arrays.toString(arr));
}
문자열
문자열 뒤집기
String str = "hello";
StringBuilder sb = new StringBuilder(str);
sb.reverse().toString();
System.out.println(sb);
}
중복된 문자열 제거
String[] arr = { "p", "e", "o", "p", "l" ,"e" };
arr= Arrays.stream(arr).distinct().toArray(String[]::new);
System.out.println(Arrays.toString(arr));
}
팰린드롬 확인
문자열 뒤집은것
뒤집은 문자열과 원래 뒤문자열이 같으면 출력 .
로또 번호 뽑기
Math.random() 함수
랜덤함수는 기본형이 Double형이기에 (int) 로 정수화시켜줘야함
0~1(1은 미포함) 구간에서 부동소수점의 난수를 생성
1부터의 값을 뽑고 싶다면 랜덤함수는 0부터 나오기때문에 +1을 꼭 시켜주는것이다
package hj;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
//랜덤 1부터 값 뽑기
int[] arr = new int[6];//로또 뽑을 배열 6개로 생성함
for(int i=0; i<arr.length; i++) {
//로또번호 랜덤으로 뽑기 -->랜덤함수는 double 형 int로 정수화 시켜줘야함
int lotto = (int)(Math.random()*45)+1; //1부터 뽑을려고 +1 해줌
arr[i]=lotto;
}
System.out.println("로또당첨번호 한번에 보기");
System.out.println(Arrays.toString(arr));
System.out.println("로또번호 하나씩 번호 보기");
for(int i=0; i<arr.length; i++) {
System.out.println(i+"번째"+arr[i]);
}
}
}
구구단 출력 (가로)
일의 자리와 십의 자리 수를 깔끔하게 정리하기 위해서 String.format 을 이용했다.
package hj;
public class Main {
public static void main(String[] args) {
//2단부터 9단까지 구구단 출력
for(int i=2; i<=9; i++) {
for(int j=1; j<=9; j++) {
System.out.print(i+"*"+j+"="String.format("%2d", i*j) );
System.out.print(" ");
}
System.out.println();
}
}
}
구구단 출력(세로)
🎈for문 사용
i와 j 만 바꿔주면 완료
package hj;
public class Main {
public static void main(String[] args) {
//2단부터 9단까지 구구단 출력
for(int i=1; i<=9; i++) {
for(int j=2; j<=9; j++) {
System.out.print(j+"*"+i+"="+String.format("%2d", i*j) );
System.out.print(" ");
}
System.out.println();
}
}
}🎈while 문 사용
package hj;
public class Main {
public static void main(String[] args) {
//2단부터 9단까지 구구단 출력
int j=0;
while(j++<9) {
int i=1;
while(i++<9) {
System.out.print(i+"*"+j+"="+String.format("%2d", i*j));
System.out.print(" ");
}
System.out.println();
}
}
}
🎈do while 문 사용
package hj;
public class Main {
public static void main(String[] args) {
//2단부터 9단까지 구구단 출력
int j=1;
do {
int i=2;
do {
System.out.print(i+"*"+j+"="+String.format("%2d",i*j));
System.out.print(" ");
}while(i++<9);
System.out.println();
}while(j++<9);
}
}
구구단 3단에서 3의 배수 빼고 출력
package hj;
public class Main {
public static void main(String[] args) {
//3단만 출력
for(int i=2; i<=9; i++) {
for(int j=1; j<=9; j++) {
if(i==3) {
if(j%3!=0)
System.out.println(i+"*"+j+"="+String.format("%2d", i*j));
}
}
}
}
}
구구단 3의 배수단만 출력
package hj;
public class Main {
public static void main(String[] args) {
//3의 배수단 만 출력
for(int i=2; i<=9; i++) {
for(int j=1; j<=9; j++) {
if(i%3==0) {
System.out.print(i+"*"+j+"="+String.format("%2d", i*j));
System.out.print(" ");
}
}
System.out.println();
}
}
}
재귀 피보나치 수열
private int fibo(int n) {
if (n < 2)
return n;
return fibo(n - 1) + fibo(n - 2);
}
메모이제이션 이용한 피보나치 수열
private int solution(int n) {
int[] memo = new int[n + 1];
return fibo(n, memo);
}
private int fibo(int n, int[] memo) {
if (memo[n] != 0)
return memo[n];
if (n < 2)
return n;
return memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo);
}
반복분(동적계획법) 이용한 피보나치 수열
private int solution(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
재귀 팩토리얼
int fact(int n) {
if(n==1)
return 1;
return n * fact(n-1);
}
최대 공약수, 최소 공배수
//최대공약수
private int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
------------------------------------------------
// 두 수의 곱을 최대 공약수로 나누면 최소 공배수
private int lcm(int a, int b) {
return a * b / gcd(a, b);
}
소수구하기
소수 : 1과 자기 자신으로만 나누어지는 수
- 1은 소수에서 제외
package hj;
public class Main {
public static void main(String[] args) {
int count=0;
for(int i=2; i<=100; i++) {
for(int j=2;j<=i; j++) {
if(i%j==0) {
count++;
}
}
if(count ==1) {
System.out.print(i+" ");
}
count=0;
}
}
}
팩토리얼 수중에 0인것
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올떄까지 0의 개수를 구하라
🙊🙊우리가 뒷자리가 0이 나오는 경우는 언제인가? 2와 5가 곱해져 있을 때다. 이 말은 거꾸로 말하자면 소인수분해를 해서 2와 5가 존재할 경우 뒷자리는 0으로 끝난다는 것
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int cnt=0;
while(num>=5) {
cnt+=num/5;
num/=5;
}
System.out.println(cnt);
}
숫자중에 7의 개수
package hj;
public class Main {
public static void main(String[] args) {
int answer=0;
int[]array= {7,77,17};
for(int i=0; i<array.length; i++) {
String num= Integer.toString(array[i]);
String[] arr =num.split("");
for(int j=0; j<arr.length; j++) {
if(arr[j].equals("7")) {
answer++;
}
}
}
System.out.println(answer);
}
}
1~100 사이수를 크기10 배열 arr에 담음 -->그리고 각각 정렬하기
int []arr = new int[10];
for(int i=0; i<arr.length; i++) {
arr[i]=(int)(Math.random()*100)+1;
}선택정렬
최소값 구해서 앞으로 보내는 방식
package hj;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int []arr = new int[10];
for(int i=0; i<arr.length; i++) {
arr[i]=(int)(Math.random()*100)+1;
}
System.out.println(Arrays.toString(arr));
//선택정렬 -->최소값 구해서 앞으로 보내는 방식
for(int i=0; i<arr.length; i++) {
int min=i; //가장 작은 원소의 인덱스
for(int j=i+1; j<arr.length; j++) {
if(arr[min]>arr[j]) {
min=j;
}
}
int tmp = arr[i]; //원래값은 0번째 배열
arr[i]=arr[min]; //0번째 배열에 제일 작은 값
arr[min]=tmp; //2번째 배열이 최소값 됨
}
System.out.println(Arrays.toString(arr));
}
}
버블정렬
바로뒤 숫자와 비교해서 큰수를 뒤로 보내는 방식
package hj;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 5, 6, 2, 3, 7, 8, 4, 9, 10};
// 버블 정렬 -- 인접한 두 원소를 검사하여 정렬
for (int i = 0; i < arr.length-1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
삽입정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
tip * 제일처음숫자는 그 자체로 정렬되어있어서 그다음 숫자부터 앞으로갈지 뒤로갈지 결정
for(int i=1; i<arr.length; i++) {
for(int j=i; j>0; j--) {
if(arr[j-1]>arr[j]) {
//스와프
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
else break;
}
}
System.out.println(Arrays.toString(arr));
퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은데이터의 위치를 바꾸는 방법
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다
package hj;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int n=10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, n-1);
}
private static void quickSort(int[] arr, int start, int end) {
//원소가 1개인 경우 종료
if(start >=end) return;
//첫번쨰원소
int pivot =start;
int left =start+1;
int right =end;
while(left <= right) {
//피벗보다 큰 데이터를 찾을 때까지 반복
while(left <=end && arr[left] <= arr[pivot]) left++;
//피벗도바 작은 데이터 찾을 떄까지 반복
while(right >start && arr[right] >= arr[pivot]) right--;
//엇갈렷으면 작은 데이터와 피벗을 교체
if(left>right) {
//스와프
int tmp=arr[pivot];
arr[pivot]=arr[right];
arr[right]=tmp;
}
//엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else {
//스와프
int tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
}
}
//분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(arr, start, right-1);
quickSort(arr, right+1, end);
System.out.println(Arrays.toString(arr));
}
}
석차구하기
정수를 비교해 작은 점수의 등수를 증가 시키는 방식
10명의 학생의 점수를 임의로 설정하여 각 학생별로 등수를 매기시오
int[] score = new int[10];
1. for(int i = 0; i < score.length;i++){
score[i] = (int)(Math.random() * 100) + 1;
}
2. int[] rank = new int[score.length];
3. for(int i = 0; i < rank.length; i++){
rank[i] = 1;
}
4. for(int i = 0; i < score.length; i++){
for(int j = 0; j < score.length; j++){
5. if(score[i] < score[j]){
6. rank[i]++;
}
}
}
7. for(int i = 0; i < arr.length; i++){
System.out.println(arr[i] + " : " + rank[i] + "등");
}
스택 자료구조
- 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다
- 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다
스택구현 예제
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
while(!s.empty()) { //비어있지 않으면
System.out.println(s.peek());//스택의 맨앞에있는거 출력
s.pop(); //하고 삭제
}
}
큐 자료구조
- 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다
큐 구현 예제
package hj;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(5); //삽입
q.offer(2);
q.offer(3);
q.offer(2);
q.poll(); //삭제
//먼저 들어온 원소부터 추출
while(!q.isEmpty()) {
System.out.println(q.poll());
}
}
}
스택두개주고 큐만들기
선입선출 FIFO 가장먼저 들어온 데이터 가장먼저 나감
-
enqueue
큐에 데이터를 삽입합니다. -
dequeue
큐의 맨 앞에 있는 데이터를 꺼내옵니다.
꺼내온 뒤에는 큐에서 제거합니다. -
peek
큐의 맨 앞에 있는 데이터가 뭔지 확인합니다. -
isEmpty
큐가 비어있는지 확인합니다.
public class Queue{
//스택 두개 생성
private Stack inBox = new Stack();
private Stack outBox = new Stack();
public Object deQueue(){
//두번째 박스가 비어있으면
if(outbox.isEmpty()){
//첫번째 박스가 비어있지을떄
while(!inBox.isEmpty()){
//두번쨰 박스에 넣어라 첫번쨰 박스에서 가져뺌
outBox.push(inBox.pop());
}
}
}
return outBox.pop();//두번째박스에서 뺴서 출력
}
public static void main(String[] args){
Queue queue= new Queue();
queue.enQueue("A");
queue.enQueue("B");
queue.enQueue("C");
}그래프 탐색 알고리즘: DFS/BFS
탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다
대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다
- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다
소수문제, 길찾기 문제, 숫자중에 0이나, 7의 개수, 팩토리얼 수중에 0인것, 피보나치, 완전탐색 기초적인것(DFS, BFS), 달팽이문제, 배열돌리기, 해쉬맵으로 카운트해서 정렬하기 , 이진검색트리, 타켓숫자을 주고 배열중 두수로 타켓숫자 만들기
.