• 알고리즘
  • backtracking
    • Shortest Paths의 조건과 경우들
• 자료구조
  • DP
  • BFS(Breadth First Search)
  • pdf 305 마이쮸 문제
  • SWEA_1225
  • 큐
  • 리스트
  • wsalgo07
  • 병합정렬
  • 트리
  • SWEA_1233
• 그래프
  • 인접 행렬
  • 인접 리스트
  • 상호배타 집합
  • Union Find 자료구조
    • Find
    • Union
  • 비트 연산자
• Backtracking
  • N queen
  • 이진탐색트리
  • 힙
• 알고리즘
  • Prim 알고리즘
  • Brute Force(브루트 포스)
    • 재귀함수를 이용한 브루트포스
  • 다익스트라 알고리즘
  • 문자열
    • 해쉬함수
    • KMP
    • 접미사 배열(SA)
  • DP
    • PDF 439
    • PDF 456
    • PDF 472
    • PDF 478
• PS 팁
  • 순열과 조합
  • BufferedReader vs Scanner
  • 시간복잡도 계산
  • 팁
• 학교에서 배운 알고리즘들

알고리즘

backtracking

backtracking으로 가장 유명한 문제는 N-Queen 문제

[[##]] Shortest Path(최단경로 알고리즘)

Shortest Paths의 조건과 경우들

• 조건
  • 간선 가중치가 있는 유향 그래프
  • 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다
  • 즉, 무향 간선 (u,v)는 유향 간선 (u,v)와 (v,u)를 의미한다고 가정하면 된다
• 두 정점 사이의 최단경로
  • 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로
  • 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않는다
  • 모든 쌍 최단경로
    • 모든 정점 쌍 사이의 최단경로를 모두 구한다 -> 플로이드-워샬 알고리즘
  • 단일 시작점 최단경로
  • 단일 시작점으로부터 각 정점에 이르는 최단경로이면서 음의 가중치를 허용하지 않는 최단경로 -> 다익스트라 알고리즘
  • 음의 가중치를 허용하면서 싸이클이 없는 그래프의 최단경로 -> 벨만-포드 알고리즘

하노이탑

if) n=3

1. from - tmp - to

2. 1. from에 있는 1, 2를 tmp로 옮김

   2. 들어가보면 from - to - tmp가 됨. a의 tmp로 가야되니까.

   3. 1. 1이 tmp로 가고
      2. 2가 to로 갓다가
      3. 다시 tmp 1이 2의 to로 옴.
   4. 그러면 tmp - from(1,2) - to(3)가 됨

결론 위에 있는 모든 덩어리를 tmp에 놓고 맨 밑 원판을 to에 옮기고, tmp에 있던 덩어리를 다시 to로 올린다.

비트마스킹

● & - 각 자리의 모든 비트를 and 연산하는 것.

○ 11에서 둘째자리 1이 1인지 0인지 알고싶을 때 알고싶은 자리를 1로하고 나머지를 0으로 했을 때 &을 해서 1이 나오면 1이니까 알 수 있다. 0이면 아무리해도 0이니까.

상대 비트가 1인지 0인지 알아낼 때 쓴다.

켜져있는지는 and로 판단, 사용중이지 않아서 쓰기로 결정해서 내가 원하는 곳을 켜주고 or 연산.

1«0 1을 0만큼 shift. 0001

1«1 이면 0010

1«2 이면 0100

쉬프트 연산자 즉, 비트마스킹으로 해서 할 수도 있다. 그런데 int보다 클 수도 있어서 BigInteger를 사용해야 한다.

BigInteger는 객체라서 +나 -를 못하고 다 메소드로 이루어져 있다.

BigInteger는 매개변수가 스트링이다.

and 연산을 했을 때 각 자리의 비트가 켜져있는지 확인해서 0이 나오면 꺼져있는 것.

1208번 문제

● 카운팅 배열로 풀어보기

● 0인덱스 안 쓰고 1인덱스부터 차례대로 만들기.

● 예시에 나온 5 8 3 1 5 6 9 9 2 2 4 를 카운팅 배열로 정리하면

● 1 2 1 1 2 1 0 1 2 가 나온다.

● min = 1, max = 9;

● 9짜리 박스를 줄이면 8로 되서 8짜리가 1개 더 늘어난다.

● 1 2 1 1 2 1 0 2(8) 1(9)

● 1이 없어지고 2가 늘어남.

● 0(1) 3(2) 1 1 2 1 0 2(8) 1(9)

● 원래있던 min이 0이 되거나 max가 0이되거나 하면 바꿔야된다.

● min = 2, max = 9;

● 높이가 중요하지 순서는 중요하지 않음.

● 또 진행하면 0(1) 3(2) 1 1 2 1 0 3(8) 0(9)

● min = 2, max = 8;

● 받았으니까 0(1) 2(2) 2(3) 1 2 1 0 3(8) 0(9)

● 덤프 횟수만큼 min, max. 하면 됨.

PDF 23 - babygin 풀이 방법

1. 진짜 완전탐색

2. 1. 6중 포문을 써서 모든 경우의 수를 판단한다.

3. 인덱스순열

4. 1. 인덱스 순열을 미리 만들어놔서 거기다 대입하는 방법

테케 수 만큼 돌리면 테케 하나에 720번째에 걸림.

012 인덱스가 있다면 012, 021, 102 … 6가지가 있다.

ex) 135라면 135, 153, …513… 등.

인덱스 순열을 먼저 만들어놓고, 각 숫자가 입력으로 들어오면 그 개수만큼 시도.

a[0] +1 == a[1] && a[0]+2 == a[2] run++

a[0] == a[1] && a[1] = a[2] triplet++

a[3]+1 = a[4] && a[3] + 2 == a[5] run++;

a[3] == a[4] && a[3] == a[5] triplet++

if(run+triplet == 2)

6개로 구분되어있으면 반복문으로 굳이 안 해도 됨.

1. +1 된 것이 다음 거일 때 한번씩 확인하는 방식.
2. 카운팅 배열로도 풀 수 있음. 가장 효과적. 근데 막상 떠오르진 않을듯.

pdf 34

● n개중 r개. 처음에 n개*n-1가지… n - (r-1)

순열, 부분집합은 기본적으로 마스터하고 있어야할 내용들.

그리디는 쉽지 않은 알고리즘. 왜냐면 증명이 되어야 함. 문제가 비중이 높지 않음.

지그재그 순회 - 홀수일 때는, 짝수일 때는 ~ 이런 식으로 하는 게 가장 편함. 가독성도 좋고.

숙제 로봇 이동거리 했던 거 그거 델타 배열 딱 하나만 써서 해결해보라.

정점의 수 만큼 2차원 배열을 만듦. ABCD, ABCD A가 A로 갈 수 있냐의 방식.

방향성이 있는 그래프가 있고 없는 그래프도 있음.

내가 갈수있는 부분이 행우선탐색. –»쪽으로.

연습문제 델타 모르겠다면 풀기

부분집합

● 1 2 3개 중 선택하거나 선택하지 않는 경우 222

● for 선택 비선택 <- 첫 번째 원소, 또 다시 for로 선택과 비선택 <- 두 번째 원소. 세 번째도 마찬가지.

이분탐색

● 정렬되어야 있어야한다.(전제조건)

● 데이터가 많으면 많을 수록 좋다

● 검색한다기보다 이진탐색을 이용해서 처리 범위를 줄여가는 용도로 많이 쓰인다.

●

부분집합의 합 부분은 제대로 알고 가기

항상 어떻게 하면 처리 범위를 줄일 수 있을까 생각해야됨.

hashcode는 객체의 유일한 해쉬를 만들 수 있으니 재정의를 해주면 좋다.

정렬되어있으면 중간에 끝낼 수 있어서 좋다. 탐색의 알고리즘이 더 간편해진다.

인덱스또한 무식하게 찾지 않는다. 트리구조로 되어있다.

문자열

각 지역별로 달라서 표준이 필요함.

이렇게 쓰면 됩니다~ -> 인터페이스

자바는 2바이트로 구성, 16비트 16진수 4개로 표현.

주소번지는 오른쪽으로 갈수록 높아짐. 리틀엔디언.

문자열이 상수의 성질을 가지고 있어서 새 문자열 객체가 무수히 만들어짐. 이걸 보완하기 위해서 스트링버퍼가 만들어짐.

+는 매번 새 문자열 객체를 리턴.

나란히 실행하는 개념 스레딩. 공유되는 자원을 동기화시켜서 써야함. 공유자원에 대해서 시간적인 공유는 안 되도록. 공간적인 공유는 됨. 스트링버퍼는 동기화가 되어있다. 스트링빌더는 그냥 벌컥벌컥 물어보지않고 방에 들어간다. 그래서 멀티스레딩환경에서 스트링빌더는 안된다. 싱글스레딩환경에서만 스트링 빌더를 써야한다.

문자열을 계속 조작해야 된다면 스트링 빌더를 써서 중간 과정에 새로운 스트링을 만들면 안 된다.

직접 맞물리는 스트림 : 노드스트림.

JVM에 올라갔을 때 기본적으로 추가되는 스트림 System.in, System.out, System.err

Buffered가 Scanner보다 속도가 훨씬 빠르다.

StringTokenizer 생성자가 string을 받아들이니까. 특별히 구분자를 주지 않으면 공백을 기준으로 함.

concat될 때마다 새로운 문자열로 계속 기억하고 있는 중

원본 문자열에 영향을 안 줌.

그래서 얘를 쓰면 힙을 계속 쓰는 중…

많이 쓴다 - 처리속도 개선. Scanner를 쓰는데 너무 느리다면.

st = new StringTokenizer(in.readLine()); // x y ==> 3 4

​ int x = Integer.parseInt(st.nextToken());

​ int y = Integer.parseInt(st.nextToken());

​ System.out.println(x + “,” + y);

스트링 조작은 빌더를 쓰자.

스택

● 후입선출

● 불필요한 객체는 null로 해도 된다.

한 소스파일에 public이 붙는 클래스는 하나만.

swea_1218

// 스택으로 풀어야 좋은 문제. 가장 마지막에 들어간 녀석을 가장 처음 확인해야 하니까. empty인지도 체크해야된다. 뒤에 여는 괄호가 더 있어도 0이 나와야 한다. 그걸 size로 체크한다.

swea_5432

// 스택으로 풀거나 아니면 그냥 for문.

​ // (가 나오면 무조건 push. ()가 나올 때는 stack.size를 더해주면 됨. )가 나올때는 sum에 +1해주면서 pop.

​ // char[] str = br.readLine().CharArray()를 쓰면 다 차례로 들어온다. 캐릭터 배열로 할 수 있음. 또는 그냥 CharAt(i)로 할 수도 있다.

​ // 여는 괄호면 무조건 스택에 넣기.

​ // 레이저를 빼내면 파이프 수.

​ // 닫는괄호면 일단 pop

​ // === 샘

​ // (이면 쇠막대기 or 레이저

​ // (이면 무조건 push ((((, 닫는 괄호 만나면 무조건 pop,

자료구조

Stack

가장 직전의 작업을 타켓으로 했을 때 스택을 쓴다. 실행중인 메소드는 스택에 쌓임. 싱글스레딩 환경에서는 스택에 따라 다 없어지면(마지막 메인이 끝나면) 프로그램이 끝남.

멀티스레딩은 여러 개가 스택의 top 상태가 됨. 스케줄러가 분할해서 관리해줌.

피보나치 수열

f(n-2)+f(n-1)로 하게 되면 너무나 많은 중복 호출이 발생함.

언제 부르든 3항은 무조건 2. 다르지 않음. n값을 줬을 때 리턴되는 값이 항상 똑같음. 이미 구한 값들.

중복되는 호출이 있는지 보고 똑같은 호출이라면 상향식으로 생각하자.

기억해둔다 - 메모이제이션.

DP

중복되는 호출이 없으면 메모이제이션은 아무런 의미가 없다.

DP(동적 계획법)도 메모리와 시간싸움.

메모이제이션을 재귀적 구조에 사용하는 것보다 반복적 구조로 구현한 게 성능적으로 효율적이다. 재귀는 쌓아야하니까. 쌓다가 끝날 수도 있음.

정올의 1077문제 배낭채우기1같은 경우, 2, 5, 10, 3의 순서로 한 번에 해줘도 되고, 2를 다 한 후, 5 해주고, 10 하고 이런 식으로 해도 된다. 최대 가치니까 MAX값 구해서 찾아주면 된다.

BFS(Breadth First Search)

• 한 정점에서 시작해서 연결된 모든 정점을 1번씩 방문
• 간선의 가중치가 1일 때 최소 비용/최단 거리를 구할 수 있다
• 시작점이 있어야 하고, 같은 정점을 두 번 이상 방문하면 안 된다

void bfs(int start){

    Queuequeue<int> queue;
    queue.push(start);
    check[start] = true; // dist[start] = 0; // dist배열을 -1로 초기화해 체크배열로도 쓸 수 있다.
    while(!queue.isEmpty()){
        // queue에서 뺄 때 check을 해주면 안 된다. 왜냐면 큐에 중복된 게 다 들어가고 나서 뺄 때 체크를 해주는 거니까. 넣을 때 check를 해줘야 중복되지 않게 큐에 들어간다.
        int nx = queue.poll(); // queue.front(); queue.pop();
        for(가능한 모든 다음 정점 y){
            if(check[y] == false){ // dist[y] == -1
                queue.offer(y)
                check[y] = true; // 방문배열 검사는 꼭 넣을 때 해줘야 한다. // dist[y] = dist[x] + 1;
                dist[y] = dist[x] + 1;
            }
        }
        
    }
        

}

DFS와 BFS는 트리나 그래프 탐색에서 나온 것.

지금까지는 선형자료구조라 노드들이 다 1:1 구조였음

비선형 구조는 다름. 트리 형태라 한줄로 늘어세울 수 가 없음. 탐색할 수 있는 고민이 필요.

Root를 갖고 있으면 전체를 갖고 있는 거라 생각해도 좋다. 같은 depth끼리 탐색.

큐에 A를 넣고 자식들을 모두 넣음. A(depth0) B1 C1 D2 E2… 순서로 쭉쭉 기다림. depth 순.

같은 depth 끼리 탐색 BFS. 너비우선탐색. 자료구조 중 큐를 씀

DFS는 스택을 씀. 스택에 따라 왼쪽이든, 오른쪽이든… 깊이우선탐색. 정점을 만날 때마다 끝까지 접근. 더 이상 갈 수 없을 때.

끝까지 백트래킹 알고리즘.

중위를 후위표기법으로 바꾸고 연산. 둘 다 스택 이용.

괄호를 해서 페어로 만들어줌.

여는 괄호는 무시하고 연산자가 나오면 Stack1에 넣음. 숫자가 나오면 다른 스택2에 넣음. (2+(3*4))닫는 괄호가 나왔다면 스택1의 가장 마지막에 푸쉬한 얘. 걔를 꺼내서 스택2에 넣음. 다시 닫는 괄호가 나온다면 +를 뒤에 붙임.

234*+ -> 스택1에 2를 넣고 3, 4 그리고 연산자가 나오면 두 개를 팝해서 연산하고 다시 그 결과를 stack2(피 연산자 기억)에 넣음12. 또 연산자 나오면 해주고 마지막에는 결과값. 후위연산자는 괄호가 없어도 연산이 쉽다.

후위표기식을 만드는 건 스택.

만약 괄호가 없다면 더 빡세짐. 전제 조건 등등…

괄호는 연사자의 수 만큼 나와야함?

////

hwalgo05

Pair 라는 클래스를 따로 만들어서 스택에 x, y가 들어가도록 함.

브루트포스로 하면 O(n^2)이라 다른 방법을 모색하는 게 좋음.

스택을 이용하는 방법

비교 횟수를 줄이기 위해 중간에 n-1보다 작은 얘들은 어차피 안 보이니까 탐색 자체를 안 하도록.

class top{

int no; // 네이밍을 정확히 주는 게 좋음.

int height;

원하는 변수를 넣어주고 생성자까지만 추가하자. 바로 대입해주면 좋으니까.

}

s.pop().no로 호출.

스택을 써서 제일 먼저 받을 수 있는 가장 가까운 탑만 봄.

2 4 6 8 10이 있을 때 일단 배열에 넣음. 스택에 있는 얘랑 비교해야 하는데 대상이 없으니까 0을 넣음. result 배열에도 0을 넣음. 4가 올 때 2번을 보는데 안보이니까 0을 pop을 해주고 4를 다시 배열에 넣음. 스택에 1을 넣고 다음 거로 감. …

즉, 스택에는 인덱스가 들어가는데 유효한 1개만 생각하면 된다. result에는

각 위치에서 한 번씩만 비교.

큰 탑은 작은 얘를 가리는데 그런 얘들을 pop 시킨다.

단순하게 먼저 생각해보고 풀기

swea 1222, 1223, 1224

계산기 1번은 다 +니까 우선순위가 같음.

계산기 2번은 +와 *중 *가 우선순위가 더 높아서 먼저 처리하는 방식으로 해야됨

계산기 3번은 괄호가 추가되서 (과 *or/, +or-를 우선순위 고려하면 된다. )는 필요 없음.

1. stack에는 연산자가 들어감,피연산자는 후위 표기식에 들어간다.
2. +, -는 1, *, /는 2, (는 두 가지로 나뉘는데 스택 안에 있는 건 0, 스택 바깥에 있는 건 3으로 지정해준다. 사실 스택 바깥에 있는
3. getPriority(stack, boolean)
4. getPriority(chars[i], false) <= getPriority(stack.peek(), true)
5. 괄호가 열린다는 이야기는 우선순위가 최우선.
6. 연산자 처리하려면
7. stack의 상단에 있는 연산자와 비교해서
8. 우선순위가 같은 놈도 먼저 처리를 해야됨
9. 스택 안에 있는 괄호랑, 스택 바깥에 있는 괄호가 있다. 스택 안에는 최 하위 우선순위, 스택 바깥에 있는 건 최 상위 우선순위.
10. boolean inInstack?
11. chars[i],

pdf에 있는 연습문제는 후위표기식이 잘못됨.

백트래킹은 DFS의 방식에 속하는 것.

백트래킹 가지치기를 하면서 최적화

퀵 정렬

반씩 나눠서 피봇을 중심으로 왼쪽과 오른쪽을 정렬해서 놓음. 중간값이나 시작이나 끝값을 피봇으로 해야 오류가 안남.

1. 피봇 위치 확정 (퀵 정렬의 핵심)

2. 1. 피봇을 기준으로 왼쪽에는 피봇보다 작은 값
   2. 오른쪽에는 피봇보다 큰 값
   3. 첫째 값, 중간 값, 끝 값 등 피봇은 아무나 될 수 있음.
   4. 분류해서 자기 위치를 찾으면서 부분집합의 크기가 1이 될 때까지 찾음.

3. 피봇의 왼쪽 집합 정렬(begin, p-1) -> 다시 퀵 정렬로

4. 피봇의 오른쪽 집합 정렬(p+1, end) -> 다시 퀵 정렬로

5. if(begin < end) quicksort // 집합의 크기가 2 이상인 것을 보장함. 다시 퀵 정렬로.

시뮬레이션

1. begin = 0, end = 4
2. 69, 10, 2, 15, 30
3. pivot = begin
4. left = begin+1
5. right=end
6. 69(p), 10(L), 2, 15, 30(R)
7. 왼쪽에서 오른쪽으로 찾아가면서 오른쪽으로 가야될(피봇보다 큰) 값을 찾아서 보내야됨.
8. 10, 2, 15, 30 모두 69보다 작은얘들. L이 30까지 갔다. 즉, L이 R로 됐다. 만나있는 상황.
9. 검색이 완료된 상황이므로 스왑을 하게 된다. R과 피봇을 스왑해준다. 그러면 69와 30이 바뀌어서 69가 맨 끝에 있게 된다.
10. begin = 0 , end = 4일 때, qsort(0, 3), qsort(5,4)가 나오는데 5,4는 처음 조건부터 갈리게 된다.
11. qsort(0,3)을 해주면 L과 R이 만나면서 30과 15를 스왑해줌. R포인터와 피봇 위치를 바꿔줌

큐

● 선입선출

● front, rear, dequeue(삭제), enqueue(삽입)

● front 변수. 직전에 빼낸 놈의 위치. -1. 스택의 top 또한 -1로 했던 것처럼.

● front를 증가시켜서 dequeue를 해주는 것.

● front와 rear가 같을 때 공백상태.

● LinkedList는 너무나 종합선물.

● Queue queue2 = new LinkedList();

pdf 305 마이쮸 문제

no, count, total로 3가지 변수가 필요하다.

새로운 사람은 그냥 증가하기만 하면 됨.

1. 큐의 front에서 dequeue
2. dequeue된 사람이 가져갈 마이쮸 처리(조건 넣기)
3. 마이쮸를 가져가고 다시 enqueue
4. 새로운 다음 사람을 enqueue

큐에서 poll과 remove차이. poll은 return null, remove는 예외를 던짐

SWEA_1225

큐를 사용하면 쉬운 문제. 어차피 레퍼런스를 주기 때문에 반환을 안 해줘도 되는 걸 생각 못 했다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Swea_1225 {
	
	// 반환을 안 해줘도 된다. void로 하고 return만 줘도 된다. 왜냐면 어차피 레퍼런스만 주니까.
	public static Queue<Integer> generate8(Queue<Integer> queue) {
		
        // 5까지 증가하는 변수
		int j = 1;
		while (true) {
			int k = queue.poll() - j++;
			if (k <= 0) {
				queue.offer(0);
                // 마찬가지로 return;만 해서 빠져나오도록.
				return queue;
			}
			queue.offer(k);
			//여기에서 그냥 j%5+1로 줘서 큰 수로 나눠도 1, 2, 3, 4, 5로 나오도록 할 수 있다.
			if (j == 6) {
				j = 1;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        
		Queue<Integer> queue = new LinkedList<Integer>();
        
		for (int t = 0; t < 10; t++) {
               int tcase = sc.nextInt();
            for (int i = 0; i < 8; i++) {
                queue.offer(sc.nextInt());
            }

            System.out.print("#" + tcase + " ");
            // 여기서도 레퍼런스라 따로 넣어줄 필요 없음. generate8(queue); 만 써줘도 됨.
            queue = generate8(queue);

            for (int i = 0; i < 8; i++) {
                System.out.print(queue.poll() + " ");
            }
		System.out.println();
		}
	}
    
}

Bufferedreader a = new Bufferedreader()를 쓸 때 input받을 때, split(“ “)으로 띄어쓰기 구분

큐

• 배열을 이용한 선형 큐. 3번 인큐, 3번 디큐, 그리고 인큐를 하면 공백상태임에도 불구하고 포화상태라고 나온다.
• 이걸 고치려면 디큐할 때마다 하나씩 계속 땡겨야된다.
• 0, 1, 2, 0, 1, 2, … 안으로 계속 움직이게 하려면 (r+1)%size로 해주면 된다.
• 포화상태와 공백상태를 구분해야 함.
  • front 공간을 안 쓰고 front와 rear를 만났을 때 포화상태를 식별하면 된다.

제대로 된 큐

1. front = rear = 0;
2. front+1, rear+1을 %size해서 연산해야 된다.
3. 포화상태 판단조건 변경(0 인덱스 공간은 사용하지 않음)

우선순위 큐.

우선순위가 있는 큐.

리스트

링크드 리스트의 구현은 알아둬야 한다.

• 데이터 필드와 링크필드
• 링크 필드에 의해서 순서가 유지됨.
• head - 시작점, tail도 따로 둘 수 있음(유지?)
  • tail이 있으면 좋은 이유?
    • 마지막 노드를 쉽게 찾을 수 있음
• 단순 연결 리스트
  • 다음 노드의 링크가 null일 때까지
  • 삭제할 때 뒤에 있는 노드를 끊어주고 앞에 있는 건 끊지 않아 줄 수 있다. 하지만 끊지 않으면 앞에 노드가 물고있기 때문에 그 노드마저 삭제했을 때 물고있는 상태로 남아서 gc가 처리하지 못 한다.
  • 삭제할 때 그 삭제하려는 노드의 이전노드를 null로 하면 끊김.
  • 인접 리스트
    • A -> B, A -> C, A -> D, B -> E 와 같은 간선, 만들어보면 그래프로 들어올 때 인접 행렬로 해도 되지만 데이터가 너무 커진다. 예를 들어, 10000개라면 10000*10000으로 해야된다. 그리고 X표 된 건 쓰지도 않는데 하나하나 모두 찾아야 되고. 그래서 인접 리스트로 푸는 게 좋다.
    • A의 칸에 head에 있는 얘를 바꿔주면서 첫 번째 노드로 계속 추가하면 된다. 예를 들어, A -> B, A -> C, A -> D의 경우 A - D - C - B로 연결된다. 하지만 이게 C와 B가 연결되어있는 게 아니고 A가 각자 연결되어있다고 생각해야 된다. 그리고 탐색만 잘하면 된다. 첫 번째로만 집어넣어주면 된다. 순서를 생각하지 않아도 된다. A의 정점에서 갈 수 있는 인접리스트라고 얘기해야 된다.
• 이중 연결 리스트

++

wsalgo07

링크드 리스트로 스택을 만드려면?

• push : 첫 번째 노드에 계속 추가하는 방식
• pop : 삭제 또한 첫 번째 노드에서 삭제하는 방식.

링크드 리스트로 큐를 만드려면?

• enqueue : 마지막 노드 추가
• dequeue : 첫 노드 삭제

` return top == null;`처럼 바로 true와 false가 나오게 할 수 있다.

hwalgo07도 직접 구현해서 풀기. 1228

병합정렬

1. 집합을 둘로 나눈다. (분할)
2. 왼쪽집합을 정렬한다
3. 오른쪽집합을 정렬한다
4. 두 집합을 합침 (병합)

트리

• 비선형 자료구조
• 1:다 관계를 가지고 있음
  • 1이 root
• 리프 노드 : 마지막 노드
• 이진트리
  • 두 개로만 나눠짐
• 높이
  • ROOT가 0.
• 완전 이진 트리
  • 포화 이진 트리의 모습을 지키면서 순서대로 맞춤. (왼쪽부터 붙인다)
  • 왼쪽이 없으면 오른쪽도 없다? 완전 이진트리이기 때문에?
• 순회 방법 3가지 -> 모두 DFS.
  • 전위(VLR), 중위(LVR), 후위(LRV)
  • ROOT를 언제 탐색하느냐에 따라 달라짐. 왼쪽과 오른쪽의 순서는 크게 신경 안 써도 된다.
    • 우리가 생각하는 전위 순회는 바로 루트를 탐색
  • 재귀적으로 호출하면 된다.
  • 자식이 없으면 탐색을 안 해도 되니까.
• 2개로 나눠지는 규칙성을 이용해서 완전 이진 트리를 배열로 구현하면 인덱스를 관리하기 편하지만 편향 이진트리를 배열로 쓰게되면 1, 2, 4, 8로 진행되기 때문에 비효율적이게 된다.
• 자기 인덱스의 2를 나누면 부모 인덱스가 나옴.

수식트리

• 피 연산자가 두 개라서 이진트리로 이용할 수 있다.

이진탐색트리

• 트리를 모두 순회할 필요가 없고 범위가 점점 좁아진다. 임시 노드로 잡아서 temp를 계속 바꿔주면서 내려가면 된다.
• 삭제 : 자식이 없는 경우, 1개 있는 경우, 2개 있는 경우 다 따져야 된다. 조정하면서 다 땡겨야함…

중위순회 시간 남으면 문제 풀기 1231번문제.

++

SWEA_1233

노드

• 연산자
  • 자식이 연산자, 연산자인 경우
  • 자식이 연산자, 숫자인 경우
  • 자식이 숫자이면, 다른 쪽은 무조건 숫자. 왜냐면 완전 이진 트리니까.
  • 즉, 왼쪽 자식 노드가 숫자일 때 오른쪽 자식 노드 숫자인지 체크.
• 숫자 - 자식 노드의 유무.

그래프

정점(Vertex)과 간선(Edge)의 집합.

비선형 자료구조. (한 줄로 줄 세울 수 없다)

V개의 정점을 가지는 최대 간선 수 : V(V-1)/2 –> 양방향 간선이 아니기 때문에 /2를 해줌.

인접 행렬

두 정점을 연결하는 간선의 유무를 행렬로 표현

V*V 행렬로 만듦. 행렬에서 ROW를 진출로 봐라. col을 진입으로.

만약 가중치가 없다면 boolean 형으로 만드는 게 좋다. 왜냐면 메모리적 측면의 이유가 크다. int형을 부르면 3()

간선이 많을 때 쓰임.

간선이 적고 정점이 많을 때 쓰인다.

인접 리스트 : 해당 정점으로 나가는 간선의 정보를 저장.

간선들의 목록을 갖고 있는 게 중요하다.

행을 인접 리스트로 생각하자.

대칭이 되는 성질이 있다.

무향과 유향을 잘 생각해봐야 한다.

int형 배열이면 가중치가 들어간다고 생각.

유향 그래프는 대칭이 아님.

인접 리스트

간선들의 정보만 구성되어있어서 공간적인 낭비는 없지만 따로 정렬하지 않는 이상 순차탐색을 해야 한다.

각 정점에 대한 인접 정점들을 순차적으로 표현

하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

새로운 노드를 추가할 때 마지막에 노드를 추가하는 알고리즘을 쓰지 말고 앞으로 추가하는알고리즘을 쓰자. 마지막 노드를 추가하려면 맨 뒤로 가서 추가를 시켜줘야 한다.

• 인접 리스트는 순차탐색을 해서 모두 다 검색해야하지만 인접리스트를 연결리스트로 저장한다면 해당하는 정점에 대해서 간선이 있기때문에 더 빠르게 간선의 정보를 찾을 수 있다.
• 새로 생성할 때 head에 집어넣기

무향 그래프일 경우

• 인접 리스트에 양방향으로 같이 추가를 해줘야 한다.

인접행렬로 DFS, BFS는 기본…

친구관계문제

1. 카운트를 줘서 풀면 된다.
2. depth count에 관한 배열을 만들어서 수를 넣어주는데 같은 depth일 때 비교하면 된다.

같은 depth마다…

상호배타 집합

Union find -> 크루스칼 알고리즘으로 풂.

-1은 자기 자신이 유일하다는 소리. 자기 혼자 root.

트리처럼 관리하는 건 아니지만 부모로 가면 root를 찾을 수 있다?

a가 b의 부모라면 부모로 주고 싶은 얘들의 인덱스를 넣어주면 된다.

parent라는 배열에 [-1, 0, -1, -1] 각각 abcd(0123)

[-1, 0, -1, 2] -> [-1, 0, 1, 2]

이게 사이클을 판단하는 요인이 된다.

최소 신장 트리를 만들려면 사이클이 있으면 안됨.

합치기 전에 찾아서 판별. union find 알고리즘

Union(d, f)할 때 e의 루트를 c의 자식으로 삼음.

찾은 부모 f로 다시 올 때 자기의 부모로 바꾼다.

pdf 312 부모를 모두 root로 바꿈.

정형화된 코드로 짜면 된다.

-1로 초기화하는 이유는 애초에 0인덱스로 초기화되기 때문에.

자기 자신이 루트면 자기 인덱스를 가져옴.

간선(Edge)클래스를 만들어서 쓰자

어차피 최소 비용으로 sort하기 때문에 바로 끊어주면 된다.

1. 비용이 최소인 간선을 이용해서 연결해나간다.
2. 사이클 형성되면 안함.
3. 간선정보를 안주면 간선의 비용을 구해야됨…

Union Find 자료구조

Find

어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별

인덱스만 따라가면 된다.

Root가 같으면 같은 집합에 있다.

Union

서로 다른 두 개의 집합을 하나의 집합으로 합병(집합에 포함되면 합병하고 포함되지 않으면 안 하고)

링크드리스트로 원소를 넣어서 찾아볼 수 있지만 O(n)이라는 시간이 걸린다. 상향식 트리 구조로 구현하면 효율적이다.

같은 집합으로 바꿔주려면 그냥 그 root 노드를 다른 집합의 Root의 자식으로 두면 된다.

높이가 낮은 집합을 높이가 높은 집합의 자식으로 두는 게 좋다. 그러면 합칠 때 높이가 같아질 수 있으니까.

비트 연산자

두 번째 비트가 켜져있는지 궁금하면 0010을 & 연산하면 된다.

쉬프트 연산은 내가 원하는 자리에 1을 놓기위한 방법

쉬프트 두 개짜리는 부호비트로 채운다~

부동 소수점

123.625는 많은 방식으로 표현이 가능하다.

12.3625

1.23624*10^2으로 고정. 소수점의 위치를 왼쪽의 가장 유요한 숫자 다음으로 고정시키고 밑수의 지수승으로 표현한다. 첫 번째 숫자 뒤에 .이 있다고 생각한다.

소수 아래부분만 기억한다.

두 개를 기억하지 않게 되는데

1. 소수점의 위치
2. 1.을 버림.

소수점의 위치까지 기억을 해야한다.

IEEE 754 포맷에 해당 내용이 있다. 32비트를 쓴다고 하면 맨 앞에 sign비트, 지수부 8, 가수부 23비트이다.

64비트일경우, 1, 11, 52 이다.

가수부분에 1. 뒤에 부분을 기억한다. 이진화된 값으로 들어간다.

sign비트를 이용하지 않고도 지수를 기억하기 위한방법

1. 지수부를 8비트라고 생각하면 256이 가능하다.
2. 그러면 128을 기준으로 10^-3이면 125, 10^5이면 133으로 기억을 한다.
3. 즉, 중간 값을 기준으로 음수 지수와 양수 지수를 판단한다.

데이터 타입 자체를 실수 연산으로 하면 좋지 않다.

이래서 웬만하면 실수 연산은 하지 않는 게 좋다.

Backtracking

답을 찾았다면 Root로 return

가지치기(Prunning)하기 전에 완전탐색으로 잘 되나부터 확인. (등호같은 거 조심.)

• 대각선이 안 된다.
• 십자가가 안 된다.

메모이제이션 테이블을 어떻게 만들지 생각.

N queen

일차원 배열만 생각해도 됨. 4*4라면 4개의 배열. 열만 생각해도 된다.

대각선의 규칙성으로 찾겠다는 소리

행 차이와 열 차이로 생각해서 푼다. [1, 3, ?, ?] 이면이 규칙을 행 차이는 1이고 열 차이가 2므로 대각선에 포함안됨. 대각선에 걸리지 않는다. 이런 방식으로 계속 체크를 해보면 된다. 바꿀 때마다 열 체크, 대각선 체크를 해주면 된다. 행 체크는 배열의 인덱스로 다르니까 상관 없다.

다 했는데 안 되면 백해서 값을 바꾸고 체크한다.

[1, 4, 2, …] 다 안됨. 1열이 안 되는 거였음. 그럼 2열로 감

N-1번 비교하면 된다. 배열은 총 3개로 체크하면 된다. 열을 체크할 배열. 우상향 - 각 좌표의 합이 똑같다(2~8), 우 하향배열 - 각 좌표의 빼기가 같다.(-3~3)

이진탐색트리

리프 노드의 삭제는 쉽다.

리프 노드인 13을 삭제한다면 그냥 삭제가 가능하다. 그러나 차수가 1인 것, 2인 걸 없앨 때는 어렵다.

차수가 2일 때는 자식중에 하나가 위로 올라와야 함. 왼쪽 서브트리보다는 크면서 오른쪽 서브트리보다는 작은 노드를 선택해야 함.

힙

완전 이진 트리로 구성. 최대 힙이면 루트 노드가 가장 큰 값, 최소 힙이라면 가장 작음. 우선순위 큐에서 쓰인다. default는 최소 힙. 오름차순. 최대힙일 때, 리프 노드랑 바꾸면서 가장 큰 루트노드를 뽑아서 배열에 넣는다. 최대이게 바로 힙 정렬.

알고리즘

가중치가 없는 간선일 경우, BFS로 푸는 게 가장 빠르다.

Prim 알고리즘

1. 임의의 정점에서 시작한다.
2. 그 임의의 정점과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점을 선택한다.
   1. 전에 있던 정점들을 포함해서 최소 비용의 간선을 찾는 것이다.
   2. 당연히 이미 다 연결된 대상은 고려하지 않는다.
   3. 경로 형태의 정점을 선택하는 것이 아니다.
   4. 정점들이 연결되어 있기만 하면 된다.
3. 모든 정점이 선택될 때까지 1, 2번을 반복한다.

pdf.

0번 정점 기준으로는 min이 7인데 1번 정점 기준으로는 3이 최소.

1. 방문했던 정점을 기준으로 방문하지 않은 정점을

연결되지 않은 정점은 넣을 때 바로 살펴보기에 사이클링을 살펴볼 필요가 없다.

브루트포스와 좀 더 개선된 코드, 두 개의 코드로 표현할 수 있다.

Brute Force(브루트 포스)

• 모든 경우의 수를 다 시도해보는 알고리즘
• 시간복잡도는 O(전체 경우의 수 * 하나를 시도하는데 걸리는 시간)

재귀함수를 이용한 브루트포스

void go(int x){
     if(정답을 찾음){
        정답을 찾은 처리;
     }
     if(불가능한 경우) return;
     for(가능한 모든 다음 정점 y){
        if(check[y] == false){
            check[y] = true;
            go(y);
        }
     }
}
check[시작] = true;
go(시작);

선택된 정점의 간선들 가중치를 계속해서 더하면 그게 최소가 되는 것

다익스트라 알고리즘

단일 출발점에서 단일 도착점으로 갈 때.

가중치가 양수일 때(1 이상)만 가능하다. 음의 가중치가 있는 선이 있다면 간선을 거칠 수록 값이 작아질 수 있기때문에 안 된다.

최단 경로라서 Path이기 때문에 누적된 간선 비용이 된다.

중간 경유지를 모두 반영한다.

미지의 큰 값을 줘놓고 시작. 왜냐면 나중에 경로에 따라서 갈 수도 있으니까.

a출발점에서 각 정점들을 도착점 개념으로 본다.

a 출발점에서 각 정점에 오는 최소 비용. a에서 b, a에서 c, a에서 d…

방문 했다면 방문한 얘들을 제외한 얘들을 다시 보기.

유리한 쪽을 업데이트 해줌.

a - b - c, a - b - d, a - b - f

a - c - d, a - c - e, a - c - f

첫 출발만 경유지와 출발점이 같은 선상에 있으니까 그런거고

나머지 얘들은 모두 경유지 개념.

0 - 1 - 4로 가는 것과 0 - 4로 가는 걸 비교해서 더 작으면 갱신해줌.

문자열

매우 어렵다. 자기 것화 하기가 어렵다. 시험에 잘 안나오기 때문에 현 상황에서는 깊게 보지 않아도 된다. 집중적으로 보완할 생각보다 다른 문제를 먼저 풀어라. 다양하게 풀어보려 하지말고 아니다 싶으면 바로 바꾸기.

랜덤하게 한 문제씩… 난해한 거 말고… 월말은 IM 2문제… 2시간.

동적 생성정도는 할 수 있게… 프론트 form 처리. 박스에 입력된 값들. 영화 티켓같이

테케 데이터 inputbox. 브라우저 dom처리, 이벤트 처리.

해쉬함수

충돌나지 않게 좋은 해쉬함수가 좋다.

라빈카프 알고리즘이 해쉬의 원리를 이용한다. 문자를 하나씩 비교하는 게 아니라 내가 찾는 문자열의 해쉬코드를 미리 만들어놓고 해쉬코드상으로 비교한다. 그래서 하나씩 비교하는 일이 없어진다.

10을 곱하고 앞에 값을 제거하고, 뒤를 붙여서 해쉬값을 쉽게 구할 수 있다.

KMP

패턴이 반복되는 문자열이 있을 경우 이 알고리즘을 쓰기 좋다.

실패가 발생한 위치부터 반복적인 패턴을 넘기기 위해서.

탐색하는데 실패했을 경우, 원본 문자열의 어디서부터 검색할지?

접미사 배열(SA)

banana -> N개의 길이를 갖는 문자열은 N개 만큼 나온다. 브루트포스로 하나하나 다 비교하게 되면 N^logN으로 많이 느리다.

입력 데이터의 범위를 보고…

접미사들은 반복적인 부분을 보고…

번호를 가지고 문자열을 대신한다.

접두사로 바로 앞에 일치하는 얘가 있는지 없는지.

접미사 배열을 만들어서 소팅하는 것.

앞에 몇 개가 일치하는지 만족하는 최장 접두사. 부분문자열을 만들 수 있다…

LCP

SWEA_1257

food라는 문자열이 들어왔을 때 접미어를 추출하면

food, ood, od, d가 나온다. 여기서 배열을 정렬한 후, 다시 접두어를 추출하면, d, food, foo, fo, f, od, o, ood, oo, o가 나온다.

그냥 쓰고 카운트를 늘려주면 될듯. 1, 4, 2, 3개니까 만약에 찾는 개수가 8개라면 8개에서 줄여가면서 0이 될 때까지 줄인다. 그러다가 LCP가 숫자가 나올 때 한 번 더 추가해줘서 하면 될 것 같다.

DP

완전 검색을 하는데

PDF 439

1-1, 2-1, 3-2, 4-3, 5-5, 6-8. 즉, 1, 1, 2, 3, 5, 8 피보나치 수열이다.

메모이제이션이 필요한지 상태공간트리를 그려보면서 생각해보자.

피보나치 수열에서 메모이제이션을 생각한다면 memo[]라는 일차원 배열을 만들어놓고 모두 -1로 일단 채워 놓는다. 그리고 -1일 때는 그 값을 채워놓도록 알고리즘을 짜면 된다.

그 다음 문제에 적용해보기. 가장 작은 단위의 항부터 구한다.

재귀 탈출 조건처럼 dp로 피보나치를 풀려면 0과 1의 인덱스는 값이 무조건 있어야 함.

dp는 역으로 생각해야한다. 작은 단위의 성질을 찾아야 한다.

가장 작은 단위부터 성질을 이용해서 현 시점의 최적해를 구한다.

분할 정복과는 dp와 다르다. 분할 정복은 같은 부분 문제가 나타날 경우 다시 계산한다. 재사용하지 않음.

PDF 456

피보나치 수열이 된다. 노파, 노노파, 노노노파파, 의 형식으로 계속 올라가면 된다.

노란색이면 노와 파로 나눠지고 파면 무조건 노이다. 이런 방식도 가능하다.

PDF 472

동전 거스름 돈 구하기. 8원을 거슬러주는데 1, 4, 6원이 있다면?

1원을 썼을 때 7원의 최적해, 4원을 썼을 때 4원의 최적해가 있다. 그러나 이렇게 하게 되면 중복적힌 호출이 많이 일어난다. 이 문제는 DP에 메모이제이션을 해도 되지만 많은 돈을 거슬러주게 된다면 메모리가 많이 필요하게 된다.

dp 접근 상향식 : 1원에 대한 최적해, 2원에 대한 최적해, 3원에 대한 최적해… 8까지 다 찾아본다.

PDF 478

nCr = n-1Cr-1 + n-1Cr

2차원 배열로 한다.

PS 팁

• 문제를 풀기보다 생각하는 시간을 많이 갖자
• 종이로 풀자
• 누가 많은 문제를 풀어봤느냐가 관건이다
• 3시간 넘게 걸린다면 그냥 해답을 보자. 왜냐면 그 시간이 지나서 풀면 풀어도 최적화된 코드가 아닐테니까.
• 된다면 2~3 가지 방법을 생각해보자
• 자기 생각에 갇히지 말고 잘 안 될 때는 빠르게 버릴 줄도 알자

사람들과의 관계성, 인테크.

• 속도 문제가 크다
• 평균적으로 문제를 풀 때, 시간이 얼마나 걸리는 지 파악.
• 어디서 오래걸렸는지 파악.
• 자기 생각에 너무 갇히지 말고 안 되면 다른 방법을 모색하자.
• 3시간이 넘는다면 해답을 보자.

순열과 조합

순열은 완전탐색으로도 풀 수 있기 때문에 잘 나오진 않는다.

조합은 많이 나오는데 next Permutation이라는 알고리즘으로 풀면 빠르다.

BufferedReader vs Scanner

둘 다 동시에 썼더니 스트림에 오류가 생겼는지 입력에 이상이 생긴다. 쓸 거면 하나만 쓰자.

시간복잡도 계산

문제를 풀 때 시간부터 먼저 보고 BufferedReader를 쓸지, Scanner를 쓸지 판단. 당연히 편한 건 Scanner다.

처음에 N 사이즈부터 보고 판단해야된다고 말씀하심.. 교수님도 그랬음.

1초에 1억번 정도 연산

6719 예시

100개의

n!은 조심해야됨. n>12만 되어도 5억정도가 됨

팁

• 행렬을 풀 때 x와 y가 아닌 r과 c를 변수로 두자.
• 메소드를 만들 때 맞다고 확신하지 말고 디버깅으로 System.out.println();을 한 번 찍어보자.
• 입력 받자마자 먼저 확인을 해본다.
• 일단 소팅하는 걸 생각해보자.
• 어떤 생각을 하기 전에 최대 N값을 넣어 최악의 경우를 보자. 시간복잡도부터 생각하자.
• length와 length()는 다르다. length()는 함수이기 때문에 부를 때마다 호출해야해서 변수에 넣어 넣고 쓰는 게 좋다.
• dfs는 시간이 오래 걸린다. bfs는 완전탐색이나 가중치가 없는 그래프, 등등 훨씬 더 많이 쓰인다
• clone함수는 쓰지말자. 2차원 배열일 경우 아예 복사해버리는 함수를 하나 만들자.
• 사방탐색을 할 때는 dr, dc로 미리 만들어놓자. 또는 %4로 처리하는 경우도 있다. 방향을 숫자로 해서.
• pro는 ArrayList나 Queue가 안되니까 아예 지금부터 안 쓰는 연습을 하면 좋다. 단순히 list로만 구현하는 연습. max같은 것들도. 속도의 빠름은 Array > ArrayList > LinkedList 순이다. 최대한 컬렉션 사용을 자제하자. 속도가 더 안 나오니까.
• search라는 함수를 만들어서 아예 쭉 돌도록. cctv하나당 방향 탐색하고 바로 다른 cctv로 가도록.
• long형과 int형의 범위를 잘 알고 있어야 한다. int형이 21억이니까 그 범위를 넘으면 Long형을 써야한다는 것도 감안

학교에서 배운 알고리즘들