희연's 개발 일기장

무방향 그래프

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에서 가장 큰 원소 일 경우에만 수행

목차

• 꼭 필요한 자료구조 기초 124
• 탐색 알고리즘 DFS/BFS 134
• [실전 문제] 음료수 얼려 먹기 149
• [실전 문제] 미로 탈출 152

꼭 필요한 자료구조 기초

• 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘 : DFS(Depth First Search), BFS(Breadth First Search)
  • 스택, 큐, 재귀 함수 이해 필요

• 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
  • 삽입(Push), 삭제(Pop)
  • 스택, 큐를 사용할 경우 삽입, 삭제 이외에도 overflow, underflow 고려 필요
    • 오버플로(Overflow) : 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 경우 발생
    • 언더플로(Underflow) : 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산 수행 시 발생

책에서는 파이썬으로 내용을 다루지만, 자바 기준으로 포스팅하겠습니다.

• 스택(Stack) 
  • 선입후출(First In Out), 후입선출(Last In Frirst Out)
  • stack.push() : 스택에 원소를 삽입한다.
  • stack.pop() : 스택의 맨 위의 원소를 삭제한다.
  • stack.peek() : 스택의 맨 위의 원소를 출력한다.
  • stack.size() : 스택의 크기 출력
  • stack.empty() : 스택이 비어있는지 확인
  • stack.contains() : 함수 안에 있는 인자 값이 스택에 포함되어 있는지 확인
  • stack.clear() : 스택에 있는 모든 데이터를 한 번에 삭제한다.

• 큐(Queue)
  • 선입선출(First In First Out)
  • queue.offer() : 큐에 원소를 삽입
  • queue.pool() : 큐에서 제일 처음(맨 앞)에 넣은 값을 삭제
  • queue.peek() : 값을 삭제하지 않고, 맨 앞의 값을 출력

• 재귀 함수(Recursive Function) 
  • 자기 자신을 다시 호출하는 함수
  • 프랙털(Fractal) 구조와 흡사 : 시에르핀스키 삼각형
  • 종료 조건을 꼭 명시해야 한다.
  • 재귀 함수는 내부적으로 스택 자료구조와 동일하다.
  • ex. factorial : 반복문보다 재귀 함수를 사용한 이점은?
    • 간결한 코드 = 점화식 사용

탐색 알고리즘 DFS/BFS

• 그래프 
  • 노드(Node) = 정점(Vertex)
  • 간선(Edge)
  • 그래프 표현 방식 2가지
    1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계 표현
    2. 인접 리스트(Adjacency List) : (연결)리스트로 그래프의 연결 관계 표현

• 인접 행렬 vs 인접 리스트
  • 인접 행렬 : 모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리 낭비
  • 인접 리스트 : 연결된 정보만 저장하기 때문에 메모리 효율적, but 조회 속도 저하

• 그래프 탐색
  • 하나의 노드를 시작으로 다수의 노드를 방문하는 것
  • 두 노드가 간선으로 연결 = 두 노드는 인접하다(Adjacent)

• DFS(Depth-First Search) 깊이 우선 탐색
  • 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드 방문 후, 돌아가서 다른 경로 탐색
  • 데이터 개수가 N개일 경우 시간복잡도 : O(N)
  • 재귀함수 이용
    • 재귀 함수는 스택구조와 동일하지만, 실제로 스택을 사용하지는 않는다.(Stack Overflow)
  • 활용 문제
    • 백트래킹, 위상 정렬
      • 백트래킹 : 해를 찾는 도중, 찾는 해가 아닐 경우 되돌아가서 해를 찾는 방법
  • 동작 과정
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
    2. 스택의 최상단 노드에 방문하지 않은 인접 노드(white)가 있으면 그 인접 노드를 스택에 넣고 방문 처리(gray)를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (방문하지 않은 노드가 여러 개일 경우 번호가 낮은 순서부터 처리)
    3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
  • 노드의 탐색 순서(스택에 들어간 순서) 1->2->7->6->8->3->4->5

• BFS(Breadth First Search) 너비 우선 탐색
  • 가까운 노드부터 탐색하는 알고리즘
  • 시간복잡도 : O(N), 일반적인 경우 실제 수행 시간은 DFS보다 빠르다.
  • Queue 이용(선입 선출 방식)
  • 활용 문제
    • 최단 경로 찾기, 위상 정렬
  • 동작 과정
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. (인접한 노드가 여러 개일 경우, 숫자가 작은 노드부터 먼저 큐에 삽입)
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
  • 노드의 탐색 순서(큐에 들어간 순서) 1->2->3->8->7->4->5->6

• DFS vs BFS 방식 비교

• 1차원 배열과 2차원 배열은 그래프의 형태로 바꿔서 생각할 수 있다. (단, 상하좌우로만 이동하는 경우)
• DFS, BFS는 배열로 풀이 가능

실전 문제 (1)

• 음료수 얼려 먹기

• 문제 요약
  • N X M 크기의 얼음 틀
  • 구멍 0, 칸막이 존재 1 
  • 상하좌우로 붙어 있는 경우 연결되어(두 노드가 간선으로 연결) 있는 것으로 간주
  • 생성되는 아이스크림 개수 구하기
  • 위의 문제의 출력 값은 3

• 문제 해설
  • 그래프에서 묶음을 찾아주는 프로그램은 어떻게 작성? -> DFS 사용
    1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
    2. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문 가능
    3. 1~2번의 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 센다.

실전 문제(2)

• 미로 탈출

• 문제 요약
  • N X M 크기의 미로
  • 현재 위치(1, 1)
  • 출구 위치(N, M)
  • 괴물이 있는 부분 0, 괴물이 없는 부분 1
  • 최소 이동 칸의 개수 구하기(시작, 마지막 칸 포함)

• 문제 해설
  • 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드 탐색. 최단 거리 -> BFS 사용
  • (1, 1) 부터 모든 노드의 값을 거리 정보로 넣는다.
  • 특정 노드에 방문할 때 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

<참고> DFS와 BFS 시간 복잡도
인접 행렬 : O(N^2)
인접 리스트 : O(N+E)