여러가지 자료를 참고하여 적은 문서입니다. 기본은 ezsw님의 유튜브 강의를 들으며 모르겠는 부분을 기록한것입니다. 세부 출처는 각각 적어놓도록하겠습니다!
사전 공부 1 : shift 연산자
shift 연산자가 비트를 이동시키는 연산자 인거는 알았는데 대체 뭐하는데 쓰는걸까??
shift 연산자
x<<y x를 y만큼 왼쪽으로 이동 . 왼쪽으로 하나 이동할 때마다 곱하기 2가 된다.
x>>y x를 y만큼 오른쪽으로 이동. 하나 이동할때마다 나누기 2가 된다.
shift 연산자와 부분집합
출처: ezsw님 유튜브- java 비트와 부분 집합
원소가 n개인 집합에서 부분집합의 총 개수 => 1<<n
집합의 원소개수는 Integer.bitCount(int i) 메소드를 사용한다. (정수를 넣었을 때 이진수로 바꾸어 1의 개수를 반환함)
- i번째 원소가 있는지 확인하는 방법은 (비트로 표현된 집합)&(1<<i) 결과가 0이 아니면 존재한다. 0이면 존재하지 않음
ex) 0101&(1<<2)= 0101&0100=0100 - i번째 원소를 추가하는 방법은 (비트로 표현된 집합) |(1<<i) 해주면 된다.
- i번째 원소를 삭제하는 방법은 (비트로 표현된 집합) &~(1<<i) 해주면 된다.
비트를 이용한 부분집합 예제
문제) 두 수의 합이 7인 경우의 수 구하기
입력) 입력 개수 , 숫자들
package codeup100;
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
public static int solve(int n,int data[]) {
int ret=0;
//모든 부분집합을 나열하기 위해서 i=0부터 1<<n까지 반복 {},{data[0]}{data[1],data[2]}....등 모든 부분 집합들 n이 4면 0000~1111까지 존재할 수 있음
for(int i=0;i<(1<<n);i++) { //1<<n는 원소가 n인 집합에서의 부분집합의 개수이다.
if(Integer.bitCount(i)!=2) { //부분집합의 원소가 두개가 아닌 경우에는 스킵
continue;
}
int sum=0;
for(int j=0;j<n;j++) { //i가 n자리 수 2진수이므로 n번 돌려서 1이 있는 곳을 확인한다.
if((i&1<<j)!=0) { //i에 j번째 원소가 존재하면 (= 부분집합이 data[j]를 포함하고 있으면) example : i가 0101이고 j가 2라서 0100이라면 &연산 해서 1이므로 ok 그리고 j가0일때도 ok
sum+=data[j]; //sum에 j번째 원소를 더한다
}
}
if(sum==7) { //합이 7이면 count를 1씩올려줌다.
ret++;
}
}
return ret;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int n =scanner.nextInt();
int[] data=new int[n];
for(int i=0;i<n;i++) {
data[i]=scanner.nextInt();
}
System.out.print(solve(n,data));
}
}완전헷갈림!! 주석 완전히 이해하고 다시 풀어보기
사전공부 2 : 재귀(Recursion)
아미치겠다 재귀도 완전 헷갈리기 시작해서 다시 정리
Base case= 간단히 결과를 반환하는 부분
Recursive case = 자기 자신을 호출하는 부분
함수 호출 했을 때 Stack Memory에 정보들 저장됨
flood fill 알고리즘 예제
재귀호출을 사용한 flood fill 알고리즘 구현 (페인트통 붓기)
입력) nn 배열의 크기 , nn배열 (색칠되지않은곳은 0 벽은1), 시작할 좌표 (x,y)
package codeup100;
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int[][]board=new int[100][100];
static void fill(int r, int c) {
if(r<0||r>n-1||c<0||c>n-1)return;//벽에 막혔거나 배열을 뚫고 나가려고할때 return
if(board[r][c]!=0) return; //가야할 곳이 이미 1로 채워져 있을 때
board[r][c]=1;
fill(r-1,c);
fill(r+1,c);
fill(r,c-1);
fill(r,c+1);
//상하좌우 1로 채우러 가기
}
public static void main(String[] args) {
// TODO Auto-generated method stub
n= scanner.nextInt();
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
board[i][j]=scanner.nextInt();
}
}
int sRow,sCol;
sRow=scanner.nextInt();
sCol=scanner.nextInt();
fill(sRow,sCol);
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
System.out.print(board[i][j]+" ");
}
System.out.print("\n");
}
}
}백준 10872번 : 팩토리얼
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
public static int factorial(int n) {
int answer=0;
if(n<=1) {
return 1;
}
answer=n*factorial(n-1);
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int n= scanner.nextInt();
System.out.print(factorial(n));
}
}0!은 1이므로 첫번째 if문을 n<=1라고 해줘야한다. 처음에 n==1라고 해서 틀림 ㅠㅅㅠ
백준 10870 피보나치 수5
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
public static int pivo(int n) {
int answer=0;
if(n==0)return 0;
if(n==1)return 1;
answer=pivo(n-1)+pivo(n-2);
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int n= scanner.nextInt();
System.out.print(pivo(n));
}
}StringBuilder과 StringBuffer
Stirng 객체끼리 연산을 하면 메모리할당과 메모리 해제를 발생시켜 성능적으로 좋지않음(String의 객체는 Heap메모리영역(가비지 컬렉션이 동작하는 영역)에 생성하고 한번 생성된 객체의 내부 내용 변화 불가능 =>immutable)
=> StringBuiler와 buffer는 새로운 객체를 생성하는게 아니라 기존의 데이터에서 더하는 방식을 사용하기때문에 성능좋음
스트링 빌더와 버퍼의 차이점은 동기화(synchronization)여부이다. Builder는 동기화가 적용되지않지만 StringBuffer는 각 메서드별로 Synchronized Keyword가 존재한다.
결론 : 멀티 스레드 환경에서는 StringBuffer, 단일 스레드이거나 동기화를 고려하지 않아도 되는 환경에서는 StringBuilder를 사용한다.
출처: https://hardlearner.tistory.com/288 그리고 https://dejavuhyo.github.io/posts/string-stringbuffer-stringbuilder/
스레드에 대해서
StringBuilder 메소드
append(a) : 문자열을 시퀀스에 추가해줌
insert(n,a) : 해당 인덱스에 문자열 삽입
delete(n,m) : n부터m 에 해당하는 인덱스의 문자를 제거
length() :길이
StringBuilder sb =new StringBuilder();