희연's 개발 일기장

DFS vs BFS

- 모든 경우의 수를 고려하는 문제 -> DFS

-> BFS로 구현시 큐의 크기가 커진다.

- 트리의 깊이가 큰 경우 -> BFS

-> DFS로 구현시 무한 루프 발생

- 최단 거리 구하기 -> BFS

깊이 우선 탐색 DFS

- 트리에서 말단까지 도착할 때까지 한 쪽 방향으로만 내려가는 방식

- 말단에 도착하게 되면 다시 돌아와서 다른 방향으로 간다.

백트래킹

- DFS 활용

- 해를 찾는 도중, 찾는 해가 아닐 경우 되돌아가서 해를 찾는 방법

- ex) N-Queen

너비 우선 탐색 BFS

- 모든 분기점을 다 검사하면서 진행

- Queue 사용

최선 우선 탐색

- BFS에서 업그레이드 된 방식

- 우선순위 큐 사용

- 현재 가장 최적인 경우를 우선적으로 검사하기 때문에 BFS보다 상대적으로 효율적이다.

무방향 그래프

graph[x][y] = 1;

graph[y][x] = 1;

행렬 표현

ex. 1번 정점과 연결된 정점을 찾아라

- 1행에서 1인 정점 찾기 -> 2번, 5번 

방향 그래프

graph[x][y] = 1;

ex. 2번 정점 이동하는 원소를 찾아라

- 2행에서 1으로 되어있는 정점 찾기 -> 5번

가중치 그래프

graph[x][y] = 가중치;

트리 순회(Tree traversal)

- 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정

- 전위 순회(preorder)

- 중위 순회(Inorder)

- 후위 순회(postorder)

- 레벨 순서 순회(breadth-first-traversal)

- 전위 순회 : F B A D C E G I H

- 중위 순회 : A B C D E F G H I

- 후위 순회 : A C E D B H I G F

- 레벨 순서 순회 : F B G A D I C E H

메모이제이션(memoinzation)

- 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해서 프로그램 실행 속도를 빠르게 하는 기술이다.

- 동적 계획법에서 사용되는 기술이다.

- 피보나치 재귀에서 모든 값을 DFS 함수를 거치게 되면, 중복되는 값들도 계산하게 되어 스택 메모리 낭비가 되는 문제점과 시간이 오래 걸린다.

배열에 DFS(n) 값들을 저장해서 개선하는 방법

public class Solution {
    static int[] fibo; // 배열에 저장해서 개선하는 방법
    public static int DFS(int n){
        if(n==1) return fibo[n]= 1;
        else if(n==2) return fibo[n]=1;
        else return fibo[n] = DFS(n-2)+DFS(n-1);
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int n = 15;
        fibo = new int[n+1]; // 0번 인덱스 필요없이 1~10번
        T.DFS(n); // 한 번 돌리고 값들을 배열에 저장해준다.
        for(int i=1; i<=n; i++) System.out.print(fibo[i]+" "); // fibo만 출력
    }
}

메모제이션을 사용해서 개선하는 방법

- if(fibo[n]>0) return fibo[n] 을 추가해줘서 바로 return

public class Solution {
    static int[] fibo; // 배열에 저장해서 개선하는 방법
    public static int DFS(int n){
        if(fibo[n]>0) return fibo[n]; // 0보다 크다는건 그 값이 이미 있다는 뜻
        if(n==1) return fibo[n]= 1;
        else if(n==2) return fibo[n]=1;
        else return fibo[n] = DFS(n-2)+DFS(n-1);
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int n = 45;
        fibo = new int[n+1]; // 0번 인덱스 필요없이 1~10번
        T.DFS(n); // 한 번 돌리고 값들을 배열에 저장해준다.
        for(int i=1; i<=n; i++) System.out.print(fibo[i]+" "); // fibo만 출력
    }
}

재귀 함수(Recursive Function)

- 자기 자신을 호출해서 재참조하는 구조의 함수

반복문(Iteration)

- 프로그램에서 같은 명령을 일정 횟수만큼 반복해서 수행하는 명령문

재귀 함수 vs 반복문 

- 재귀 함수는 스택 프레임에 정보가 저장된다. 그래서 stack에 계속 정보가 쌓이기 때문에 스택 오버플로우가 생길 수 있다는 단점이 존재한다.

- 반복문은 스택에 정보를 저장하지 않기 때문에 실행 속도가 재귀 함수보다 빠르다.

- 반복문이 재귀 함수보다 성능이나 메모리 면에서 좋지만, 알고리즘 자체가 재귀적인 표현이 필요한 경우 재귀 함수를 사용한다.

Set

- 순서가 없는 데이터의 집합

- 중복 허용 X

- HashSet, TreeSet

Map

- key, value가 한 쌍으로 이루어지는 데이터의 집합

- 순서가 없는 데이터의 집합

- key 중복 허용 X, value는 중복 허용

- HashMap, TreeMap, Hashtable, Properties

Hash

- 순서가 없다.

Tree

- 트리 구조로, 순서 유지

HashMap vs HashSet vs TreeMap vs TreeSet

목차

• 범위를 반씩 좁혀가는 탐색
• [실전 문제] 부품 찾기
• [실전 문제] 떡볶이 떡 만들기

범위를 반씩 좁혀가는 탐색

• 순차 탐색(Sequential Search)
  • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
  • 정렬되지 않은 리스트에서 데이터를 찾을 때 사용
  • 시간 복잡도 O(N)
• 이진 탐색(Binary Search) : 반으로 쪼개면서 탐색하기
  • 배열 내부의 데이터가 정렬되어 있어야 사용 가능
  • 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.
  • 변수 3개 사용 : 시작점, 끝점, 중간점
  • 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
  • 동작 원리
    • 시작점[0]과 끝점[9]을 확인하고, 중간점(나누고, 소수점을 버린다)[4]을 정한다. 
    • 구하려는 값 4가 중간점[4] 작을 경우, 오른쪽 값은 상관없이 끝점을 중간점 보다 한 칸 앞으로 끝점[3]으로 옮긴다.
    • 시작점[0]과 끝점[3]과 중간점[1]에서 중간점[1]보다 4가 더 클 경우, 시작점을 중간점 보다 한 칸 뒤로 시작점[2]으로 옮긴다.
    • 시작점[2]과 끝점[3] 중간점[2]으로, 구하려는 값 4와 동일하기 때문에 탐색을 종료한다.
  • 이진 탐색을 한 번씩 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다 -> 시간 복잡도 O(logN)
  • 이진 탐색 구현 방법 2가지
    • 재귀 함수
    • 반복문
  • 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해보자.

• 트리 자료구조
  • 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree) 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
• 이진 탐색 트리
  • 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
  • 이진 탐색 트리의 특징
    • 부모 노드보다 왼쪽 자식 노드가 작다.
    • 부모 노드보다 오른쪽 자식 노드가 크다.
  • 출제 빈도가 낮다.

실전 문제 (1)

• 부품 찾기

• 문제 요약
  • 부품 N개
  • M개의 종류
  • N개의 부품 번호 중에 M개의 종류가 있는지 확인하는 프로그램

• 문제 해석
  • N개의 부품을 번호를 기준으로 정렬
  • M개의 찾고자 하는 부품이 각각 존재하는지 확인
  • (정렬되어 있기 때문에) 이진 탐색 사용

실전 문제 (2)

• 떡볶이 떡 만들기

• 문제 요약
  • 떡의 개수 N개
  • 요청한 떡의 길이 M
  • 서로 다른 높이의 떡이 있을 경우, 같은 높이로 떡을 잘랐을 때 남는 떡의 총 길이는 M이다.
  • 남는 떡의 총 길이를 M으로 만드는 높이의 최댓값을 구하는 프로그램

• 문제 해석
  • 이진 탐색 문제
  • 파라메트릭 서치(Parametric Search) 유형
    • 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
    • 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용
    • 일반적으로 재귀 함수보다, 반복문 구현이 더 간결하다.
    • ex.범위 내에서 조건을 만족하는 가장 큰 값을 찾는 문제일 경우, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
  • 현재 이 높이로 잘랐을 경우, 조건을 만족하는지 확인 -> 조건의 만족 여부(yes or no) 확인 후 탐색 범위 좁히기(이진 탐색)
  • 문제 풀이
    • 시작점 0, 끝점 19 -> 중간점 9 -> 얻는 떡 25은 6보다 크기 때문에 시작점 증가
    • 시작점(중간점+1) 10, 끝점 19 -> 중간점 14 -> 떡의 합계 9은 6보다 크기 때문에 시작점 증가
    • 시작점(중간점+1) 15, 끝점 19 -> 중간점 17 -> 떡의 합계 2은 6보다 작기 때문에 끝점 감소
    • 시작점15, 끝점(중간점-1) 16 -> 중간점 15 -> 떡의 합계(4+0+0+2) 6은 조건 만족

목차

• 기준에 따라 데이터를 정렬
• [실전 문제] 위에서 아래로
• [실전 문제] 성적이 낮은 순서로 학생 출력하기
• [실전 문제] 두 배열의 원소 교체

기준에 따라 데이터를 정렬

• 정렬(Sorting)
  • 데이터를 특정한 기준에 따라서 순서대로 나열
  • 이진 탐색(Binary Search)에서 사용
  • 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
  • 리스트를 뒤집는 연산 시간 복잡도 : O(N)
• 선택 정렬(Selection Sort)
  • 매번 가장 작은 것을 선택하는 알고리즘
  • 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 전체 데이터 정렬이 이루어진다.
  • 시간 복잡도 : O(N^2)
    • N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
    • N X (N+1) / 2 = (N^2 + N) / 2 = O(N^2)
• 데이터가 늘어날 경우의 정렬 수행 시간(파이썬 기준)

• 삽입 정렬(Insertion Sort)
  • 특정한 데이터를 적절한 위치에 삽입
  • 그 앞의 데이터들은 이미 정렬되어 있다고 가정한다.
  • 첫 번째 데이터는 그 자체로 정렬되어 있다고 생각하기 때문에 두 번째 데이터부터 시작한다.
  • 시간 복잡도 O(N^2)
  • 현재 리스트의 데이터가 거의 정렬되어 있는 상태일 경우 매우 빠르게 동작한다.

• 퀵 정렬(Quick Sort)
  • 가장 많이 사용되는 알고리즘
  • 기준을 설정한 다음 큰 수와 작은 수를 교환한 후에 리스트를 반으로 나누는 방식으로 동작한다.
  • 피벗(Pivot)이 사용되고, 다양한 분할 방법이 있다.
  • 호어 분할(Hoare Partition) : 가장 대표적인 분할 방식. 리스트에서 첫 번째 데이터를 피벗으로 정한다.
    • 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 
    • 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
    • 왼쪽과 오른쪽에서 찾는 값이 엇갈린 경우 작은 데이터와 피벗의 위치를 서로 변경해준다.
    • 분할 = 파티션(Divide = Partition) : 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업
    • 파티션이 완료된 상태에서 왼쪽 배열을 정렬 오른쪽 배열을 정렬
    • (퀵 정렬 종료 조건) 현재 리스트의 데이터 개수가 1개인 경우, 이미 정렬이 되어 있다고 간주하여 분할이 불가능하다.
  • 시간 복잡도 평균 : O(NlogN), 최악의 경우 : O(N^2)
  • 무작위 데이터는 빠르게 동작할 확률이 높지만, 왼쪽 데이터를 피벗으로 삼을 때 이미 데이터가 정렬되어 있는 경우라면 매우 느리게 동작한다.
  • 데이터 유형을 파악하기 어렵다면 퀵 정렬을 사용하는 것이 유리하다.

• 계수 정렬(Count Sort)
  • 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
  • 데이터 개수 N, 최대 값 K 
  • 최악의 경우에도 수행 시간 O(N + K) 보장
  • (제한 조건) 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 -> 리스트(배열)을 선언해야 되기 때문
  • 0이상 100이하인 성적 데이터 정렬에 효과적이다.
    • 모든 범위를 담을 수 있는 배열을 생성하고, 모든 데이터를 0으로 초기화한다.
    • 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시켜준다.

JAVA 정렬 라이브러리

• Arrays.sort() 
  • 듀얼 피봇 퀵 정렬 사용
  • 시간 복잡도
    • 평균 O(Nlog(N)
    • 최악의 경우 O(N^2)
• Collection.sort()
  • Timesort 사용
    
    • 삽입 정렬과 합병 정렬을 결합하여 만든 정렬
  • 시간 복잡도 
    • 평균 O(Nlog(N))
    • 최악의 경우 O(Nlog(N))
    • 최선의 경우 O(N)
  • 삽입 정렬을 사용하는데 O(N^2)이 나오는 이유
    • 삽입 정렬은 인접한 메모리와 비교를 반복하기 때문에 참조 지역성의 원리를 만족하고 있다.
    • 작은 n 에 대하여 삽입 정렬이 빠른 속도를 보여준다.
    • (아이디어) 전체를 작은 덩어리로 잘라 각각의 덩어리를 삽입 정렬을 사용하여 병합하면 좀 더 빨라질 것이다.
    • 참고 글
    • https://d2.naver.com/helloworld/0315536

실전 문제 (1)

• 위에서 아래로

• 문제 요약
  • 하나의 수열을 내림차순으로 정렬하는 프로그램

• 문제 해설
  • 수의 개수가 500개 이하로 매우 적기 때문에, 모든 수는 1~100,000개이다. 어떠한 정렬 알고리즘이어도 상관 없기 때문에 가독성을 위해 기본 정렬 라이브러리를 사용한다.

실전 문제 (2)

• 성적이 낮은 순서로 학생 출력하기

• 문제 요약
  • N 명의 학생
  • 학생의 정보 - 이름, 성적
  • 성적이 낮은 순서대로 학생 이름을 출력하는 프로그램

• 문제 해설
  • 학생의 정보가 최대 100,000개이므로, 최악의 경우 O(NlogN)을 보장하는 알고리즘 혹은 O(N)을 보장하는 계수 정렬 사용

실전 문제 (3)

• 두 배열의 원소 교체

• 문제 요약
  • 두 개의 배열 A, B은 N개의 원소로 구성
  • 배열의 원소는 모두 자연수
  • 최대 K번 바꿔치기 연산 수행 : 배열 A의 원소와 배열 B의 원소 하나를 골라서 서로 바꾸는 것
  • 배열 A의 모든 원소 합의 최대값을 출력하는 프로그램

• 문제 해설
  • 매번 배열 A에서 가장 작은 원소를 고르고, 배열 B에서 가장 큰 원소와 교체한다.
  • 배열 A의 원소를 오름차순 정렬 후, 배열 B 원소를 내림차순 정렬한다.
  • 그리고 두 배열의 원소를 가장 첫 번째 인덱스부터 비교해나간다.
  • 단, 배열 A에서 가장 작은 원소 < 배열 B에서 가장 큰 원소 일 경우에만 수행