알고리즘 복습 #1

hyeon·2022년 3월 4일

알고리즘 복습

목록 보기

1/3

외워야할 것들

<Math 클래스의 메소드들>

1. abs - 절댓값 (int float double long타입 가능)
2. ceil(double a) -천정함수 (실수값보다 크거나 같은 정수 중 가장 작은 정수 반환)
3. floor(double a) -바닥함수 (실수값보다 작거나 같은 정수중 가장 큰 정수 반환)
4. max (a,b)- 큰값 반환 (float, long, itn dobule 가능)
5. min(a,b)- 작은값 반환 (이하동문)
6. pow(double a,double b) - a의 b승
7. random()
8. round(a)- 반올림 double float 가능 double은 long 값, float은 int 값으로 반환됨 (첫째자리에서 반올림됨)
9. sqrt(double a)- 제곱근(16->4)

<원하는 자리 수에서 반올림하기>

round 함수는 double을 넣었을때 가장가까운 long값, float을 넣었을때 가장 가까운 int 값을 리턴 한다. 그리고 첫째자리에서 반올림 하기때문에 정수값이 나온다. 그래서 원하는 자리에서 반올림을 해주기 위해서는 구하려는 값에 반올림을 원하는 자리 만큼 곱하기를 해주고 나온 결과가 정수 타입으로 리턴 되기 때문에 소수점인 실수로 반환해주기 위해서 10.0 이런식으로 실수를 명시적으로 표시해준다.

Math.round(num*10)/10.0

<테스트케이스의 갯수가 정해지지 않았을 때>

while(scanner.hasNext())를 사용한다

<유클리드 호제법>

gcd를 최대 공약수를 구하는 함수라고 하고 r을 a/b의 나머지라고 할 때 gcd(a,b)=gcd(b,r)과 같다고 한다. (0<=r<b) (a>=b)

그래서 gcd를 for문이나 재귀문을 써서 반복하다보면 r이 0이된다. 그러면 b가 최대 공약수가 된다.
최소 공배수는 a*b/최대공약수 이다.

<배열 정렬시키기>

Arrays.sort();

< List 정렬시키기>

Collections.sort(list);
Collections.sort(list,Collections.reverseOrder());

<Hash 정렬시키기>

key 기준으로

    List<String> keySet = new ArrayList<>(map.keySet());

    // 키 값으로 오름차순 정렬
    Collections.sort(keySet);
    
    //순서대로 hash map에서 꺼내쓰면 됨

value 기준으로

    List<String> keySet = new ArrayList<>(map.keySet());
	//람다식으로
    keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
    keySet.sort((o1,o2) -> map.get(o2)-map.get(o1));
	//comparator
    keySet.sort(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return map.get(o1).compareTo(map.get(o2));
        }
    });

<자바 int 범위>

약 -21억~+21억

<#6 수학관련알고리즘 다시 한번씩 보기>

< char형 int형으로 바꾸기>

str.charAt(i)-'0';

<ArrayList 사용법(인접리스트)>

ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<n;i++){
		list.add(new ArrayList);
} 	//한 행마다 가로 list 생성 해주기 
for(int i=0;i<m;i++){
			int a=scan.nextInt();
			int b=scan.nextInt();
			list.get(a).add(b);
			list.get(b).add(a);
}
//get으로 a의 인접리스트에 add b

<comparator 재정의하기>

양수면 자리를 변경 음수면 그대로

static Comparator<String> cmpt=new Comparator<String>(){
	@Override
    public int compare(String o1,String o2){
    	if(o1.compareTo(o2)<0){
        return -1;
        }
        else return 1;
    }
};

static class Info implements Comparable<Info>{
		int idx, distance;	//인덱스와 가중치를 저장한다.
		Info(int idx,int distance){	
			this.idx=idx;
			this.distance=distance;
		}
		public int compareTo(Info other) {	//가중치를 기준으로 comparable을 선언하여 우선순위 큐의 판단 기준을 제공한다.
			if(this.distance<other.distance) {//비교할 값보다 지금이 최소값일 때 -> 교환안함
				return -1;		//음수 일경우 : 교환안함
			}
			return 1;
		}
		
	}
    ```

## <문자열 자르기>
split을 사용하면 배열로 return 됨
substring을 이용하면 string으로 return 됨

substring은 index적어줘야함
=> indexOf(',)로 index 찾아줘야함


## < INT to STRING >

Integer.toString();


## < length 함수>
배열의 길이구할때는 ()없이 ???
string은 ()있게 ?

arr[numbers.length]
for(int i=0;i<numbers.length;i++)

## < 형변환 >
double to int
(int) round(double숫자)
int to string
Integer.toString(int 숫자)

String to int
Integer.parseInt(문자열)

## <큐와 스택>
Stack s=new Stack();

Queue q=new LinkedList();

```java
	public static void DFS(int v) {
		Stack<Integer> stack =new Stack<>();

		stack.push(v);
		
		while(!stack.empty()) {
			int curr=stack.pop();	//노드를 pop
			
			if(visited[curr]==1)continue;		//방문한 노드이면 skip
			//그렇지 않으면
			visited[curr]=1;
			sb.append(curr+" ");
			for(int i=n;i>0;i--) {
				if(visited[i]==0&&arr[curr][i]==1) {//방문하지 않은 노드이고 간선이 존재하는 경우
					stack.push(i);
				}
			}
		}
		}
	public static void BFS(int v) {
		Queue<Integer> q=new LinkedList<>();
		
		visited2[v]=1;
		q.offer(v);
		
		while(q.isEmpty()==false) {
			int curr=q.poll();
			sb2.append(curr+" ");	//실제 방문
			
			for(int i=1;i<n+1;i++) {
				if(visited2[i]==0&&arr[curr][i]==1) {//방문하지 않은 노드이고 간선이 존재하는 경우
					visited2[i]=1;
					q.offer(i);
				}
			}
		}
	
	}

클래스를 따로 선언할때

class xy{
	int x;
	int y;
	public xy(int x, int y){
		this.x=x;
		this.y=y;
	}
->
//queue에서 사용할 때
Queue<xy> q=new LinkedList<>(); //큐를 xy형으로 선언해야하고 

q.offer(new xy(nextx,nexty)); //넣을 때도 new xy로
xy xy=q.poll(); // 뺄때도 xy형으로

문자열 메소드

indexOf("찾는문자") : 찾는 문자의 첫번째 index를 return 해준다. 찾지못하면 -1 return
substring(index1,index2) :해당하는 인덱스 사이에 있는 문자를 string으로 return 해준다.(0,2)이면 ab까지
split(";") : 지정한 문자로 나눠서 배열로 return 해준다.
String[] ans= str.split(";") 이면
ans[0], ans[1]… 이런식으로
contains(str2) : 해당 문자열이 포함되어있는지 boolean으로 return해준다.

문자열 reverse

StringBuilder 이용

        // reverse
        StringBuffer sb = new StringBuffer(str);
        String reversedStr = sb.reverse().toString();

int <-> Long

int to Long

Long n = new Long (intVal);

int x=4;
Long xLong=Long.valueOf(x);

Long to Int

Long x = 11L;
int xInt = x.intValue();

주의할점

조건을 쓸 때 같거나 작은거 포함인지 같은조건도 포함인지 확인 잘하기
Math로 반올림 내림 버림시 double로 바꿔서 계산

배열을 List로

Arrays.asList()
new ArrayList<>(Arrays.asList())
Collectors.toList()

ArrayList를 배열로

toArray() - java.util.List
// ArrayList를 배열로 변환 int arrListSize = arrList.size();
String arr[] = arrList.toArray(new String[arrListSize]);

hyeon

남기고 싶은 개발자입니다 :>

다음 포스트

알고리즘 복습 #1