Example

Solution 🔥

• 문제 초반에 "재귀적인 패턴으로 별을 찍어 보자"라고 적혀있다 이에 재귀함수로 이 문제를 풀려고 하니 도저히 풀리지 않아 다른 코드를 보고 이를 이해하는데에 목적을 두었다. 다음 그림은 오랜만에 재귀를 풀어 봤길래 정리하는겸 어떤식으로 재귀함수가 돌아가는지 순서를 적어봤다. n = 27 의 경우이다. star(27)의 함수를 처음 호출하고 함수 내에서 star(9) 호출, star(3)호출, star(1) 호출이 되고 star(1) 함수가 가장 먼저 반환되고 그다음 차례대로 star(3), star(9), star(27)이 반환된다.

그렇다면 재귀에서 가장 중요하게 생각해야하는 건 무엇일까?

1. 어디가 끝인가? => 여기서는 n = 1이 되는 경우이다 이때 반환 되는 것이 최소 단위가 된다는 것 또한 중요하다

2. 어떻게 반복되는가? 여기서는 밑의 코드에서와 같이 for문을 참고하면 어떠한 반복이 이루어지는지 알수 있을 것이다. 대충 퉁쳐서 말하자면 이 문제는 "*3" 이라고 할수있겠다.(정확한 반복은 for문과 이미지 참고)

Code

def star(n):
    if n == 1:
        return ['*']
    stars = star(n//3)
    li = []

    for s in stars:
        li.append(s*3)
    for s in stars:
        li.append(s+' '*(n//3)+s)
    for s in stars:
        li.append(s*3)
    return li

n = int(input())
print('\n'.join(star(n)))

출처

https://lucian-blog.tistory.com/57

Entity Framework(EF)

C#과 같은 객체 지향형 프로그래밍(OOP)에서 데이터베이스를 쉽게 사용하기 위한 ORM(Object-Relational Mapping)도구 => 객체(Object)와 관계형(Relational) 데이터베이스의 테이블을 Mappin하여 쉽게 데이터에 접근 할 수 있다

Microsoft가 직접 구현한 ORM으로는 EF와 LINQ TO SQL이 있다

• Code First 먼저 C# 클래스로 테이블의 구조를 정의한다. 클래스의 속성을 테이블의 column에 Mapping한다. 미리 DB를 설계하지 않고 C# 클래스들로 Domain object를 정의하고 프로그램 실행시 DB가 없으면 자동으로 생성하는 방식

• Model First 기존 DB가 없을 때 직접 Visual Model Designer에 Entity들을 하나씩 추가해 나가면서 Data Model을 구성하는 방식

• Database First 기존 DB로부터 테이블 구조들을 읽어 Visual Model을 구성하는 방식

Reference List

https://www.csharpstudy.com/web/article/8-Entity-Framework

API (Application Programming Interface)

API가 무엇인가?

api라는 맥락에서 Application은 고유한 기능을 가진 모든 소프트웨어를 나타낸다. Interface는 두 application 간의 서비스 계약이라고 할 수 있는데, 이 계약은 요청과 응답을 사용하여 두 Application이 통신하는 방법을 말한다.

API는 어떻게 작동하는가?

보통 clien와 server 측면으로 설명하는데 요청을 보내는 application을 client, 응답을 보내는 application을 server라고 한다.

API가 생성된 시기와 이유에 따라 네가지 방식이 있다.

• SOAP API 과거에 많이 사용했던 API로 단순 객체 프로토콜을 사용하며, 클라이언트와 서버는 XML을 사용하여 메세지를 교환한다

• RPC API 원격 프로시저 호출이라고 하는데, 클라이언트가 서버에서 함수나 프로시저를 완료하면 서버가 출력을 클라이언트로 다시 전송한다

사실 위 두개는 별로 들어본 적이 없다. 밑에 두개는 많이 들어봤을 것이다

• Websocket API JSON 객체를 사용하여 데이터를 전달하는 최신 웹 API로 클라이언트앱과 서버 간의 양방향 통신을 지원한다. 서버가 연결된 클라이언트에 콜백 메세지를 전송할 수 있어 REST API보다 효율적이다.

• REST API 가장 많이 사용되고 있는 API로 클라이언트가 서버에 요청을 데이터로 전송한다. 서버가 이 클라이언트 입력을 사용하여 내부 함수를 시작하고 출력 데이터를 다시 클라이언트에 반환한다.

Endpoint

그래서 endpoint가 뭔데?

api는 한마디로 클라이언트으로부터 요청을 받고 서버로부터 요청에 대한 응답을 전송하는 것이라고 할 수 있다. 여기서 endpoint는 요청을 받아 응답을 제공하는 서비스를 사용할 수 있는 지점을 의미한다

예를 들어 영화 평가를 제공하는 웹서비스가 있다고 할 때, 사용자는 원하는 영화를 검색해 볼 것이다. 이 때 해당 영화에 대한 평가를 이용하기 위한 요청이 향하는 URL이 endpoint 이다.

Reference list

https://aws.amazon.com/ko/what-is/api/ https://blog.hubspot.com/website/api-endpoint https://blog.naver.com/ghdalswl77/222401162545

그래서 정리하는 Local Database 와 Remote Database

Local Database

local = 지역 remote = 원격 이름만 봐도 상대적으로 작은 범위이다.

local database는 어플리케이션과 동일한 시스템에 상주한다. 즉 우리의 핸드폰이나 태블릿 안에 있는 지역 저장소이다.

장점 : database에 접근하기 위해 네트워크 통신을 거쳐 server에 접근 할 필요가 없어 원격 데이터베이스 서버 보다 빠르다.

단점 : 동기화가 어렵다. 상호작용이 불가능하다.

주로 소규모의 데이터를 저장하고 관리할 때 사용하는 데이터베이스이다

SQLite, Room, Realm 등이 있다

Remote Database

외부에서 접근이 가능하도록 네트워크 통신을 거쳐 서버에 도착한 뒤 데이터베이스에 접근하여 데이터를 불러오는 방식이다.

Remote Database의 경우 네트워크 통신에 영향을 많이 받고 대규모의 데이터를 저장하고 관리할 때 사용하는 데이터베이스이다. Local Database의 경우 동기화와 상호작용이 불가능했지만 Remote Database는 상호작용이 가능하고 이 또한 실시간 접근이 가능하다.

Orcale, MySQL, MSSQL 등이 있다.

Reference

https://blog.naver.com/winner23456/222641014262 다음 블로그를 읽으며 다시 정리하였다.

** < MST : Minimum Spanning Tree> **

• 신장 트리 중 가중치의 합이 최소가 되는 신장트리
• 여러개가 존재할 수도 있다.
• 경로 연결간에 가장 저렴한 경로를 찾는데 사용
• 순환되면 안된다
• MST의 간선의 개수 = n - 1
• 탐욕법(Greedy) 알고리즘 중 하나

탐욕법 (Greedy)

• 구성 : 다양한 선택, 모음, 또는 찾아야 할 값들

• 목표 : 구성에 할당된 점수가 존재하며 , 이를 최대화 또는 최소화 해야하는 상황

• 탐욕적 선택 속성 => 출발 구성으로부터 시작하여 지속적인 지역적 향상을 통해 전체 최적해를 찾을 수있는 경우 사용

  ex) 잔돈 거스르기 문제 => 가능한 항상 제일 큰 동전으로 거슬러 준다

  • 동전 종류 (32,8,1) => O
  • 동전 종류 (30,20,5) => X => 탐욕적 선택 속성 없음 => 40원은 2개의 20원으로 가능하지만 30원 1개, 5원 2개를 하게 될것

Prim-Jarnik 알고리즘

• 대상 : 단순 연결 무방향 가중 그래프
• 임의의 정점 s를 택하여 s로부터 시작하여, 현 단계에서 갈 수 있는 모든 곳을 검색해 가장 저렴한 곳 연결 (순환이 되면 X)
• n개의 노드를 채울때까지 반복
• 우선 순위 큐 (이진 힙)이용

<핵심>

트리에 속하지 않은 정점들 중 트리에 인접한 간선에서 최소의 가중치를 갖는 간선을 선택한다는 것이다.

visited 리스트를 이용하여 처리 정점이 트리에 속해질 때마다 정점의 인접 간선 정보 업데이트

** GUI ** Graphic User Inter face 로 CLI와 다르게 화면에서 마우스를 통해 컴퓨터를 조작하는 그래픽 기반의 유저 페이스

Terminal Command

• pwd : 현재 디렉토리

• ls : 현재 디렉토리 파일 리스트 보기

• cd : 디렉토리 이동

• mkdir "폴더명" : 디렉토리 생성

• rmdir : 디렉토리 삭제 (내부에 파일이 없을 때만) rm -r test => 내부까지 삭제

• clear : 현재 화면 클리어

• touch : 파일 생성 (touch test.txt)

• rm : 파일 삭제

• mv : 파일 이동 mv test.txt test (test 폴더로 이동시키기)

• mv : 파일/디렉토리 이름 바꾸기 mv test.txt test2.txt (test2로 이름변경)

• open : Explorer / Finder 에서 열기

• cat : 파일 내용 확인 (concatenate 약자, cat test.txt)

• history : 이전에 사용한 명령어 확인

• man : 명령어 메뉴얼 확인

2.1 기본 구조

Hello.java

public class Hello{
    public static int sum(int n, int m){
        return n+m;
    }

    public static void main(String[] args){
        int i = 20;
        int s;
        char a;

        s = sum(i,10);
        System.out.println(a);
    }
}

main 메소드에서 실행 시작

2.2 식별자

• 클래스 이름 : 첫번째 문자는 대문자로 시작
• 변수, 메소드 이름 : 첫단어는 소문자로 시작, 각 단어의 첫번째는 대문자로 표기 ex) myAge, myName
• 상수 이름: 전체 대문자로 표기

2.3 데이터 타입

• 기본 타입 :
  • boolean
  • char
  • byte
  • short
  • int
  • long
  • float
  • double (문자열은 기본 타입 X , 자바 라이브러리에서 제공하는 String class 이용)

• 레퍼런스 타입 => c/c++의 포인터와 비슷한 개념이지만 실제 주소 값을 가지지는 않는다.

int n = null ; //불가능 => null은 객체 레퍼런스에만 사용 가능
String str = null; // 정상

// var keyword
// var의 사용은 지역 변수에만 한정된다.

var price = 200 ;
var name = "kitae";
var pi = 3.14;
var point = new Point();

// 상수 선언
final double PI = 3.141592

// 강제 타입 변환 ( casting )
int n = 300;
byte b = n ; //compile error

// b에는 44 로 저장됨 300 % 256 = 44 byte(1byte) , int(4byte)
byte b = (byte)n ; // n을 byte 타입으로 강제 변환

2.4 키 입력

• System.in 키보드 장치를 직접 제어하고 키 입력을 받는 표준 입력 스트림 객체 => 단순한 바이트 정보로 응용프로그램에 전달 => 잘 사용 안함

• Scanner class 이용

import java.util.Scanner;

Scanner scanner = new Scanner(System.in);
String name = scanner.next();
int age = scanner.nextInt();
double weight = scanner.nextDouble();
String line = scanner.nextLine(); // '\n'까지 읽고  '\n'을 제외한 너머지 문자열 저장

//scanner 객체 close
scanner.close();

=> Scanner 객체를 이용하여 키보드로부터 바이트 정보를 받고, 이를 원하는 타입으로 변환하여 제공 => 공백문자를 기준으로 분리하여 토큰 단위로 읽는다.

2.5 연산

• 연산자는 모든 프로그래밍 기본과 동일 하기에 작성하지 않겠다. 우선순위만 한번 확인하자

  2.6 조건문

  - if 문

  if (n % 2 == 0) {
    System.out.println(n + "is Even.");
  }
  else if(조건문){
  }
  else(조건문){
  }

- switch 문

//switch 문

switch (score/10){
    case 10: 
    case 9:
        grade = 'A';
        break;
    case 8: 
        grade = 'B';
        break;
       default:
        grade = 'F';
}

🤍 접근

처음에는 dfs로 접근하였는데 위의 예시에서 1, 3, 2 와 같은 경우에서 1과 2 사이의 거리는 1인데 1->3->2와 같이 측정되어 거리가 2로 인식되는 오류가 생겼다. 그래서 bfs로 다시 접근하여보았다.

완성 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

//bfs => 최단경로 ,미로찾기 같은거 <= queue 이용

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> graph(n+1);
    vector<bool> visited(n+1,false);
    queue<int> q;
    vector<int> distance(n +1 , 0);

    for(vector<int> e : edge){
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    q.push(1);
    visited[1] = true;

    while(!q.empty()){
        int start = q.front();
        q.pop();

        for(int i = 0; i < graph[start].size() ; i++){
            int end = graph[start][i];
            if(!visited[end]){
                visited[end] = true;
                distance[end] = distance[start] + 1;
                q.push(end);
            }
        }
    }

    sort(distance.rbegin(), distance.rend()); // 내림차순
    for(int d : distance){
        if(d == distance[0]) answer++;
        else break;
    }

    return answer;
}

✅ Bayes' Theorem

- 베이즈 정리의 의미와 의의

베이즈 정리는 단순히 조건부 확률을 풀어낸것이 아니다. 새로운 정보를 토대로 어떤 사건이 발생했다는 ** 주장에 대한 신뢰도를 갱신 ** 해 나가는 방법이다.

- 베이지안 주의?(Bayesianism)

또한 베이지안 주의 관점으로 확률을 보면 전통적인 확률관(빈도주의)와는 다르다. 베이지안 주의 관점으로 보면 확률은 "주장에 대한 신뢰도"라고 할수있다. 예를 들어 주사위를 던져 1이 나올 확률을 1/6하는 것을 빈도주의에서는 600번 던졌을때 100번은 1이 나올 것이다 해석하는 것이고, 베이지안 주의에서는 주사위가 1이 나왔다는 주장의 신뢰도가 1/6라고 보는 것이다.

- 용어

H : Hypothesis (가설) => 어떤 사건이 발생했다는 주장 E : Evidence (증거) => 새로운 정보 Posterior probability : 사후 확률 Likelihood : 우도 (가능성) Prior probability : 사전 확률 Evidence : 증거

베이즈 정리는 두 확률 변수의 사전 확률과 사후 확률 사이의 관계를 나타내는 정리다. 베이즈 확률론 해석에 따르면 베이즈 정리는 사전확률로부터 사후확률을 구할 수 있다. 먼저 단어부터 들이대 보았다. 근데 또 일단 문제부터 한번 풀어보자. 가장 흔한 예시 질병이다.

예제

질병 A의 발병률은 0.1%로 알려져있다. 이 질병이 실제로 있을 때 질병이 있다고 검진할 확률(민감도)은 99%, 질병이 없을 때 없다고 실제로 질병이 없다고 검진할 확률(특이도)는 98%라고 하자.

만약 어떤 사람이 질병에 걸렸다고 검진받았을 때, 이 사람이 정말로 질병에 걸렸을 확률은?

📜 solution

-> 먼저 hypothesis와 Evidence를 정의해보자

evidence : 새로운 정보 => 질병에 걸렸다고 검진을 받았을때 (positive) hypothesis : 주장 => 정말로 질병에 걸렸다 => 구하고자 하는 것 : P(H|E)

그러므로

질병 A의 발병률은 0.1%이므로 임의의 사람이 이 질병에 걸렸을 확률은 P(H)로 쓸 수 있으며, ** P(H)=0.001 ** 이다.

민감도: $$ P(E|H)=0.99 $$ 특이도 : $$ P(E^c|H^c)=0.98 $$

위의 식 와 같이 조건부 확률만 알아도 풀 수 가있다. 하지만 베이즈 정리의 진정한 의의는 알기 어렵다. 베이즈 정리의 진정한 의의는

** 사전확률을 모르는 상황에서 사전확률을 가정하고, 발생한 사건(새로운 정보)를 토대로 사전확률을 "갱신" 해나가는데 있다. **

다음 예시를 보자.

예제

상대가 나를 좋아하는지 궁금한 상황이다. 그런데 상대방이 먼저 나에게 디엠이 왔다고 하자. 여기서 사전확률은 그가 나를 좋아할 확률이다. 그가 나를 좋아할 확률? 잘모르겠다. 좋아하지도 싫어하지도 않는것 같다. 그러면 좋아할 확률을 0.5라고 사전확률을 놓자. $$ P(L) = 0.5 $$ 이제 상대방의 행동을 기반으로 사전확률을 갱신해나갈 것이다. 상대방의 행동 => 나에게 디엠을 보낸 것이다 이제 알아야 할 것은

상대방이 나를 좋아하는데 먼저 디엠을 보낼 확률 : P(D|L) 상대방이 나를 좋아하지않는데 먼저 디엠을 보낼 확률 : P(D|L')

이 확률을 안다는 것이 비현실적이긴 하지만 여러명을 조사해본결과 P(D|L) = 0.6 P(D|L') = 0.4 이라고 하자

그렇다면 다음과 같이 구할수있다. 그러면 디엠을 받음으로써 상대방이 날 좋아 할 확률이 0.6로 갱신되었다. 이것을 베이즈 갱신이라 하며 갱신된 확률을 사후 확률이라고 한다.

이 상황에서 상대방이 영화를 보자고 한다면? 다시 새로운 정보가 들어온 것이다 그러면 앞에 구한 사후확률은 다음 갱신에서 사전확률이 된다. 이제 갱신된 상대방이 나를 좋아할 확률은 0.6이다. $$ P(L) = 0.6 $$ 이제 상대방의 행동을 기반으로 사전확률을 갱신해나갈 것이다. 상대방의 행동 => 나에게 영화를 보자고 하였다. 이제 알아야 할 것은

상대방이 나를 좋아하는데 먼저 디엠을 보낼 확률 : P(M|L) 상대방이 나를 좋아하지않는데 먼저 디엠을 보낼 확률 : P(M|L')

또 이 확률을 조사해본 결과 P(M|L) = 0.7 P(M|L') = 0.3 이라고 하자 그러면 다음과 같이 또 0.75로 갱신된 것을 볼 수있다. 베이즈 정리는 이와 같이 갱신해 나가는 것에 의의가 있다.

** * 알고리즘 시간 복잡도 순서 **

시간 복잡도 크기 순서 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

** * 우선순위 큐와 큐 **

• 큐는 FIFO 구조로 먼저 들어간것이 먼저 나오는 구조
• 우선순위 큐는 들어간 순서와 관계없이 우선순위가 높은 데이터가 먼저 나온다
• 우선순위 큐로 무슨 자료구조가 가장 구현하기 적합한가? => 힙 ( 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현)

** * 정렬 알고리즘 정리 **

( 정렬의 자세한 코드는 제 velog 확인 )

• 합병 정렬, 삽입 정렬, 버블 정렬만 안정 정렬이다.
• 삽입 정렬 최선의 경우 O(n) -> 처음부터 자료가 정렬되어있는경우 => 자료가 정렬이 되어있을수록 빠르다
• 힙 정렬 -> 위의 표는 어디서 가져왔는데 힙정렬은 추가 메모리 없이 제자리 정렬도 가능하다. (합병정렬만 추가 메모리 필요)
• 합병 정렬, 퀵 정렬 알고리즘 설계기법 => "분할 통치법" (분할->정복(재귀)->합병(통치))
• 합병 정렬 외부 메모리 필요, 순차적 데이터 접근
• 퀵 정렬 최악의 경우 O(n^2) => pivot(기준원소)가 항상 유일한 최소이거나 최대원소일 경우 => LT 와 GT 중 하나는 크기가 n-1, 다른쪽은 크기가 0
• 우선순위 큐 (선택 : 무순리스트 , 삽입 : 순서리스트, 힙 : 힙)
• 분할 통치 (합병,퀵)

** 사전 ADT **

분할 통치 vs 이진 탐색

• 분할 통치 : (정렬시) 이등분된 두개의 범위 모두 고려

• 이진 탐색 : (탐색시) 이등분된 두개의 범위 중 한쪽을 고려대상에서 배제

• • 이진 탐색 트리 **
  • key(lchild) < key(parent) <= key(rchild)
  • 완전 이진트리로 전제
  • 탐색 성능 최악(O(n)) 최선 O(log n)
• • AVL Tree **

• 높이 균형 속성 ( 트리의 모든 내부 노드에 대해 자식들의 좌우 높이 차이가 1을 넘지 않는다)

• 탐색,삽입,삭제 O(log n)

• • Splay Tree **

• 트리의 노드가 탐색 또는 갱신을 위해 접근된 후, 스플레이되는 이진 탐색 트리를 말합니다. (스플레이 된다 = 해당 노드가 루트로 이동된다)

• 탐색,삽입,삭제 O(log n) (상각실행시간)

• AVL보다 구현이 더 간단

  ** 해시 테이블 **

• 버켓 배열 + 해시 함수 해시함수 => 무작위하게 분산 ,가능한 상수시간 임의의 키 => < 해시코드 맵 > => < 압축 맵 >

• 압축맵 ( 나누기 , 승합제( |ax + b| % M {a % M != 0}) )

  • 충돌 해결

    • 분리 연쇄 법 ( 테이블 외부에 추가적인 공간 요구)

    • 개방 주소법 ( 공간절약, but 삭제가 어려움 , 군집화 발생 )

      • 선형 조사법 => 바로 다음 테이블 셀에 저장 (1차 군집화 발생)

      • 2차 조사법 => 1 , 4, 9, 16 ...다음 테이블 셀에 저장(2차 군집화 발생)

      • 이중 해싱!!! => 군집화를 최소화 더하는게 함수값임 함수값과 M은 서로소관계 cf) M은 소수이면 더 좋음 => 소수가 아니면 충돌 발생 가능성이 더 높음

  ** 그래프 **

• 간선 리스트 구조

• 인접 리스트 구조

• 인접 행렬 구조

• 인접 리스트 vs 인접 행렬 희소 그래프 => 인접 리스트 밀집 그래프 => 인접 행렬

• DFS

  • 스택 사용 구현 / 재귀 구현 두가지 방법 존재
  • O(n+m)

• BFS

  • 큐 사용 구현
  • O(n+m)
    • 최단경로에 사용

** 방향 그래프 **

• 진입 간선 , 진출 간선 이용
• 이행적 폐쇄 => DFS 로 찾기 O(n(n+m)) => 플로이드와샬 (동적프로그래밍) O(n^3)

💞 깊이 우선 탐색(DFS)란?

** < DFS : Dept First Search >**

• 그래프 전체를 탐색하는 방법 중 하나로 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법
• 구현에는 스택을 통해 구현 / 재귀함수로 구현 2가지 존재 => 재귀함수로 구현이 더 간편

DFS 코드

//인접 리스트를 이용한 dfs 구현

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct incidenceType{
    int vertex;
    struct incidenceType *next;
}incidence;
typedef struct vertextType{
    incidence *head;
    int vertex;
    int isVisited;
}vertext;
typedef struct graphType{
    vertext *vertext;
}graph;

void makeEdge(graph g,int v1,int v2);
void DFS(graph g,int v);

int main(){
    int n,m,s,i,v1,v2;
    graph g;

    scanf("%d %d %d",&n,&m,&s); //정점개수, 간선 개수, 조사 시작할 정점 번호
    //그래프 초기화
    g.vertext = (vertext*)malloc((n+1)*sizeof(vertext));
    for(i=1;i<=n;i++){
        g.vertext[i].vertex=i;
        g.vertext[i].isVisited=0;
        g.vertext[i].head = (incidence*)malloc(sizeof(incidence));
        g.vertext[i].head->next = NULL;
        g.vertext[i].head->vertex =0;
    }

    for(i=0;i<m;i++){
        scanf("%d %d",&v1,&v2);
        makeEdge(g,v1,v2);
    }

    DFS(g,s);

    return;
}

void makeEdge(graph g,int v1,int v2){
    incidence *node1,*node2,*new1,*new2;
    node1 = g.vertext[v1].head;
    node2 = g.vertext[v2].head;

    new1 = (incidence*)malloc(sizeof(incidence));
    new2 = (incidence*)malloc(sizeof(incidence));

    new1->next = NULL;
    new1->vertex = v2;
    new2->next = NULL;
    new2->vertex = v1;
    // 정점 번호 순서대로 넣음
    while(node1->next!=NULL){
        if(node1->next->vertex>new1->vertex)
            break;
        node1 = node1->next;
    }
    new1->next = node1->next;
    node1->next = new1;

    while(node2->next!=NULL){
        if(node2->next->vertex>new2->vertex)
            break;
        node2 = node2->next;
    }
    new2->next = node2->next;
    node2->next = new2;
}

void DFS(graph g,int s){
    incidence *node = g.vertext[s].head;

    if(g.vertext[s].isVisited == 1)
        return;

    g.vertext[s].isVisited = 1;
    printf("%d\n",s);

    while(node->next!=NULL){
        DFS(g,node->next->vertex);
        node=node->next;
    }
}

DFS 시간복잡도

인접 리스트로 구현 : O(n + m) 인접 행렬로 구현 : O(n^2)

💞 너비 우선 탐색(BFS)란?

** < BFS : Breadth First Search >**

• 그래프 전체를 탐색하는 방법 중 하나로 시작점으로부터 인접한 노드를 먼저 탐색하는 방법
• 구현에는 큐를 통해 구현

BFS 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct incidenceType{
    int vertex;
    struct incidenceType *next;
}incidence;

typedef struct vertextType{
    incidence *head;
    int vertex;
    int isVisited;
}vertext;

typedef struct graphType{
    vertext *vertext;
}graph;

typedef struct nodeType{
    int data;
    struct nodeType *next;
}node;

typedef struct queueType{
    node* head;
}queue;

void makeEdge(graph g,int v1,int v2);
void BFS(queue *q,graph g,int v);
void enQueue(queue *q,int data);
int deQueue(queue *q);

int main(){
    int n,m,s,i,v1,v2;
    graph g;

    //큐 초기화
    queue *q = (queue*)malloc(sizeof(queue));
    q->head = (node*)malloc(sizeof(node));
    q->head->next = NULL;
    q->head->data = 0;

    scanf("%d %d %d",&n,&m,&s); //정점 개수, 간선 개수, 탐색시작할 정점 번호

    //그래프 초기화
    g.vertext = (vertext*)malloc((n+1)*sizeof(vertext));
    for(i=1;i<=n;i++){
        g.vertext[i].vertex=i;
        g.vertext[i].isVisited=0;
        g.vertext[i].head = (incidence*)malloc(sizeof(incidence));
        g.vertext[i].head->next = NULL;
        g.vertext[i].head->vertex =0;
    }

    for(i=0;i<m;i++){
        scanf("%d %d",&v1,&v2);
        makeEdge(g,v1,v2);
    }

    BFS(q,g,s);

    return;
}

void makeEdge(graph g,int v1,int v2){
    incidence *node1,*node2,*new1,*new2;
    node1 = g.vertext[v1].head;
    node2 = g.vertext[v2].head;

    new1 = (incidence*)malloc(sizeof(incidence));
    new2 = (incidence*)malloc(sizeof(incidence));

    new1->next = NULL;
    new1->vertex = v2;
    new2->next = NULL;
    new2->vertex = v1;

    // 정점 번호 순대로 삽입
    while(node1->next!=NULL){
        if(node1->next->vertex>new1->vertex)
            break;
        node1 = node1->next;
    }
    new1->next = node1->next;
    node1->next = new1;

    while(node2->next!=NULL){
        if(node2->next->vertex>new2->vertex)
            break;
        node2 = node2->next;
    }
    new2->next = node2->next;
    node2->next = new2;
}

void BFS(queue *q,graph g,int s){
    int v;
    incidence *node;
    //시작 정점 삽입
    enQueue(q,s);
    g.vertext[s].isVisited = 1;

    while(q->head->next!=NULL){
        v = deQueue(q);
        printf("%d\n",v);

        node = g.vertext[v].head;
        //인접 정점 큐에 삽입, 방문처리
        while(node->next!=NULL){
            if(g.vertext[node->next->vertex].isVisited==0){
                enQueue(q,node->next->vertex);
                g.vertext[node->next->vertex].isVisited = 1;
            }
            node = node->next;
        }
    }
}

void enQueue(queue *q,int data){
    node *newnode;
    node *tmp = q->head;

    newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
    newnode->next = NULL;

    while(tmp->next!=NULL)
        tmp = tmp->next;
    tmp->next = newnode;
}
int deQueue(queue *q){
    int ret;
    node *del;
    node *tmp = q->head;

    del = tmp->next;
    tmp->next = del->next;
    ret = del->data;
    free(del);
    return ret;
}

BFS 시간복잡도

인접 리스트로 구현 : O(n + m) 인접 행렬로 구현 : O(n^2)

💞 DFS & BFS 응용

• 최단경로 : BFS
• 이중 연결 요소 : DFS
• 신장숲, 연결 요소, 경로, 싸이클 : DFS, BFS

신장 트리 , 신장 숲

• ** 신장 트리 (Spanning Tree) ** : 그래프의 정점들을 가지고 있는 트리(연결되고 , 싸이클이 없음) => n개의 정점을 n-1개의 간선으로 연결 => 구현 : DFS or BFS 도중에 사용된 간선들만 남겨두면 된다.
• ** 신장 숲 (Spanning forest) **: 그래프가 연결되어 있지 않을 때 신장트리를 만들수 없다. => 각 연결된 요소들이 신장 트리들을 가짐

사전 구현에 따른 탐색 기법

무순 사전

• 사전 항목들을 임의의 순서로 리스트에 저장

• insertItem() : 맨 앞 또는 맨 뒤에 삽입 => O(1)

• findElement() or removeElement() : 최악의 경우(항목이 존재 안하는 경우) 리스트 전체 순회 => O(n)

• 사용 ) 소규모의 사전 , 삽입은 빈번하지만 탐색이나 삭제는 드문 사전 (ex : 서버의 로그인 기록)

• 선형 탐색 사용 (단순히 리스트 전체를 순회하며 원소를 찾음) => O(n)

순서 사전

• 사전 항목들을 정렬된 순서로 저장

• findElement() : 이진 탐색 이용 => O(log n) 시간 소요

• insertItem() : 공간 확보를 위해 최악의 경우 n개의 항목 이동이 필요 => O(n)

• removeElement() : 항목이 삭제된 공간을 기존 항목들로 메꾸기 위해 최악의 경우 => O(n)

• 사용 ) 소규모 사전, 탐색은 빈번하지만 삽입이나 삭제는 드문 사전 (ex : 전화번호부, 신용카드 사용승인)

• 이진 탐색 사용

이진 탐색

• 키로 정렬된 배열에 기초한 리스트로 구현된 사전에 대해 findElement 수행
• 재귀가 발생할 때마다 탐색해야할 원소의 수가 반감 => 최대 log(n)회 실행 됨

  // 중복된 숫자가 없는 정렬된 배열에서의 탐색
  

// x = k 인 숫자 index 찾기 int rFE(int * arr, int k, int l, int r) { int mid = (l + r) / 2;

if (l > r) return -1;

if (k == arr[mid]) return mid;
else if (k < arr[mid]) rFE(arr, k, l, mid - 1);
else rFE(arr, k, mid + 1, r);

}

// x <= k 만족하는 숫자 index찾기 int rFE(int* arr, int k, int l, int r) { int mid = (l + r) / 2;

if (l > r) return -1;

if (k == arr[mid]) return mid;
//왼쪽 보ㅓ기
else if (k < arr[mid]) return rFE(arr, k, l, mid - 1);
//오른쪽 보기
else
{
    if (mid == r) return mid;
    if (arr[mid + 1] > k) return mid;
    else return rFE(arr, k, mid + 1, r);
}

} int findElement(int* arr, int n, int k) { return rFE(arr, k, 0, n - 1); }

// + 비재귀 x>=k 만족하는 숫자 index 찾기 int findElement(int* arr, int n, int k) {

int l = 0, r = n - 1;
int mid;

while (l <= r) {
    mid = (l + r) / 2;
    if (arr[mid] == k) return mid;
    else if (k < arr[mid]) {
        if (mid == l) return mid;
        if (arr[mid - 1] < k) return mid;
        r = mid - 1;
    }
    else {
        l = mid + 1;
    }
}
return n;

}

• ** 노드(Node) 또는 정점(vertex) ** 와 노드와 노드를 연결하는 ** 간선(Edge) ** 으로 구성

  ✔ 관련 용어

  • 정점(vertex) : 위치라는 개념
  • 간선(edge) : 위치 간의 관계 , 노드를 연결하는 선(link, branch)
  • 인접 정접(adjacent vertex) : 간선에 의해 직접 연결된 정점
  • 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 => 무방향 그래프에서 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
  • 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수
  • 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수
  • 경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
  • 단순 경로(simple path) : 경로 중 반복되는 정점이 없는 경우
  • 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

✔ 그래프 종류

무방향 그래프 VS 방향 그래프

** 무방향 그래프(Undirected Graph) **

• 무방향 그래프는 방향이 없는 그래프로 간선을 통해 양방향 모두 접근 가능
• (A,B) = (B,A)

** 방향 그래프(Directed Graph) **

• 간선에 방향성이 존재
• (A,B) != (B,A)

가중치 그래프 ** 가중치 그래프(Weighted Graph) **

• 간선에 비용이나 가중치가 할당된 그래프

연결 그래프 VS 비연결 그래프

** 연결 그래프(Connected Graph) **

• 무방향 그래프에 있는 모든 정점쌍에 대하여 항상 경로가 존재하는 경우

** 비연결 그래프(Disconnected Graph) **

• 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

완전 그래프 ** 완전그래프(Complete Graph) **

• 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프 => 정점수 : ** n * (n -1) / 2 ** {n = 간선의 수}

✔ 그래프의 구현

1. 인접 행렬(Adjacency Matrix)

< 무방향 그래프 인접 행렬 표현>

if(간선 x,y가 그래프에 존재) M[x][y] = 1;
otherwise M[x][y] = 0

#include <stdio.h>
#include <stdlib.h>

#define VERTICES 6 //vertex 개수

void printIncidence(int ** g, int v) {
    if (v < 1 || v > 6 ) {
        printf("-1\n");
        return;
    }
    for (int i = 1; i <= VERTICES; i++) {
        if (g[v][i] != 0) printf(" %d %d", i, g[v][i]);
    }
    printf("\n");
}

void makeEdge(int** g, int v1, int v2, int w) {

    if (v1 < 1 || v1 > VERTICES || v2 < 1 || v2 > VERTICES) {
        printf("-1\n");
        return;
    }
    //무방향그래프
    g[v1][v2] = w;
    g[v2][v1] = w;
}

void makeGraph(int** g) {

    for (int i = 1; i <= VERTICES; i++) {
        for (int j = 1; j <= VERTICES; j++) {
            g[i][j] = 0;
        }
    }
    //간선 삽입 예시
    makeEdge(g, 1, 2, 1); // 1과 2 사이에 가중치 1인 간선 생성
    makeEdge(g, 1, 3, 1); // 1과 3 사이에 가중치 1인 간선 생성
    makeEdge(g, 1, 4, 1); // 1과 4 사이에 가중치 1인 간선 생성
    makeEdge(g, 1, 6, 2); // 1과 6 사이에 가중치 2인 간선 생성
    makeEdge(g, 2, 3, 1);
    makeEdge(g, 3, 5, 4);
    makeEdge(g, 5, 5, 4);
    makeEdge(g, 5, 6, 3);
}
int main() {
    char c;
    int v, v2, w;
    int** g = (int *)malloc(sizeof(int*) * (VERTICES + 1));

    for (int i = 1; i <= VERTICES; i++) {
        g[i] = (int*)malloc(sizeof(int) * (VERTICES +1 ));
    }

    makeGraph(g);

    return;
}

다음과 같이 표현 할 수 있다.

2. 인접 리스트(Adjacency List)

• 가장 일반적인 방법

#include <stdio.h>
#include <stdlib.h>

#define VERTICES 6 //vertex 개수

typedef struct incidence {
    int weight;
    int vertex;
    struct incidence* next;
}incidence;

typedef struct vertex {
    incidence * head;
    int vertex;
}vertex;

typedef struct graph {
    vertex vertexs[VERTICES + 1];
}graph;

void printIncidence(graph* g, int v) {
    incidence* temp;
    if (v <= 0 || v > VERTICES) {
        printf("-1\n");
        return;
    }
    temp = g->vertexs[v].head->next;
    while (temp) {
        printf(" %d %d", temp->vertex, temp->weight);
        temp = temp->next;
    }
    printf("\n");
}

void printGraph(graph* g) {
    incidence* temp;

    for (int i = 1; i <= VERTICES; i++) {
        printf("graph < %d > : ", i);
        temp = g->vertexs[i].head->next;
        while (temp) {
            printf(" %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
    printf("\n");
}

//간선 삭제 수정 삽입 모두 가능 + 정점 크기 순으로 삽입됨
void makeEdge(graph* g, int v1, int v2, int w) {
    incidence* temp1,* temp2;
    incidence* new1, * new2;
    incidence* prev1, * prev2;
    int plus = 0;
    temp1 = g->vertexs[v1].head;
    temp2 = g->vertexs[v2].head;

    // 정점 존재하지 않을 시 종료
    if (v1 <= 0 || v1 > VERTICES || v2 <= 0 || v2 > VERTICES) {
        printf("-1\n");
        return;
    }
    prev1 = g->vertexs[v1].head;
    prev2 = g->vertexs[v2].head;
    //삭제의 경우
    if (w == 0) {
        while (temp1) {
            if (temp1->vertex == v2) {
                prev1->next = temp1->next;
                free(temp1);
                break;
            }
            prev1 = temp1;
            temp1 = temp1->next;
        }
        while (temp2) {
            if (temp2->vertex == v1) {
                prev2->next = temp2->next;
                free(temp2);
                break;
            }
            prev2 = temp2;
            temp2 = temp2->next;
        }
        return;
    }
    new1 = (incidence*)malloc(sizeof(incidence));
    new1->vertex = v2;
    new1->weight = w;
    new1->next = NULL;

    new2 = (incidence*)malloc(sizeof(incidence));
    new2->vertex = v1;
    new2->weight = w;
    new2->next = NULL;


    //삽입 or 수정
    while (temp1) {
        //삽입

        if (temp1->vertex > v2) {
            break;
        }
        //수정 (간선 가중치 수정도 가능)
        if (temp1->vertex == v2) {
            temp1->weight = w;
            plus = 1;
            break;
        }
        prev1 = temp1;
        temp1 = temp1->next;
    }
    if (plus == 0) {
        prev1->next = new1;    
        if (temp1 != NULL) {
            new1->next = temp1;

        }
    }

    while (temp2) {
        //삽입
        if (temp2->vertex > v1) {
            break;
        }
        //수정 (간선 가중치 수정도 가능)
        if (temp2->vertex == v1) {
            temp2->weight = w;
            plus = 1;
            break;
        }
        prev2 = temp2;
        temp2 = temp2->next;
    }
    if (plus == 0) {
        prev2->next = new2;
        if (temp2 != NULL) {
            new2->next = temp2;
        }
    }
}

void makeGraph(graph * g) {
    //초기화
    for (int i = 1; i <= VERTICES; i++) {
        g->vertexs[i].vertex = i;
        g->vertexs[i].head = (incidence*)malloc(sizeof(incidence));
        g->vertexs[i].head->vertex = 0;
        g->vertexs[i].head->weight = 0;
        g->vertexs[i].head->next = NULL;
    }
    //예시
    makeEdge(g, 1, 2, 1); // 1과 2 사이에 가중치 1인 간선 생성
    makeEdge(g, 1, 3, 1); // 1과 3 사이에 가중치 1인 간선 생성
    makeEdge(g, 1, 4, 1); // 1과 4 사이에 가중치 1인 간선 생성
    makeEdge(g, 1, 6, 2); // 1과 6 사이에 가중치 2인 간선 생성
    makeEdge(g, 2, 3, 1);
    makeEdge(g, 3, 5, 4);
    makeEdge(g, 5, 5, 4);
    makeEdge(g, 5, 6, 3);
}

✔ 인접 행렬 VS 인접 리스트

뭐가 더 효율적인가?

• 희소 그래프 VS 밀집 그래프

=> 희소 그래프 만약 정점이 1000개가 있는데 간선은 10개 뿐인 그래프가 있다고 하자. 이렇게 간선의 수가 적은 그래프를 희소 그래프(sparse graph)라고 한다. 이를 행렬로 구현하기위해서는 10개의 간선을 나타내기 위해 1000x1000행렬을 사용해야한다. 하지만 인접 리스트로 구현시 1000 + 10개의 노드만 있으면 구현이 가능하다. 따라서 인접 리스트는 희소 그래프를 표현할때 적당하다.

=> 밀집 그래프 만약 정점이 1000개가 있는데 간선이 2000개가 있는 그래프가 있다고 하자. 이렇게 간선 수가 가 많은 그래프를 밀집 그래프(dense graph)라고 한다. 이때는 인접행렬로 그래프를 구현하는 것이 더 효과적이다. 왜냐하면 행렬은 인덱스로 바로 접근이 가능하기 때문이다

➕ ** STACK **

** LIFO ** (Last Input First Out)

• 마지막에 넣은 원소가 먼저 나온다는 것이다.

• 아래가 막혀있고 위가 뚫린 형태로써, 차곡차곡 쌓는 구조이다.

• 스택에서 삽입은 PUSH, 삭제는 POP 이라는 용어로 사용한다.

• DFS 탐색시 사용

  ex) 문서 작업에서 컨트롤 + Z 와 같은 이전 상태로 되돌리기 등처럼 캐시와 같은 모습으로 많이 존재한다.

😨 stack overflow?

• stack이란 것을 배우기도 전부터 많이접해보았을 것이다.
• 말 그대로, 위와 같이 정해진 크기에 무언가를 계속 넣고 있다가 받아들일 수 있는 크기를 초과해서 흘러넘쳐버린 것을 말한다.

*코드(연결리스트 이용, c로 구현) *

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char* data; struct Node* prev; struct Node* next; } Node;

typedef struct LinkedListStack { Node* top; int size; } LinkedListStack;

LinkedListStack* init() { LinkedListStack* stack; stack = (LinkedListStack*)malloc(sizeof(LinkedListStack)); stack->top = NULL; stack->size = 0; return stack; }

Node* NodeInit(char* str) { Node* newNode = (Node)malloc(sizeof(Node)); newNode->data = (char)malloc(strlen(str)+1); strcpy(newNode->data, str); newNode->next = NULL; newNode->prev = NULL; return newNode; }

void push(LinkedListStack* list, char* str) { Node* newNode = NodeInit(str); Node* oldTop;

if(list->top == NULL) {
    list->top = newNode;
}
else {
    oldTop = list->top;
    oldTop->next = newNode;
    newNode->prev = oldTop;
    list->top = newNode;
}
list->size++;

}

void pop(LinkedListStack* list) { Node* currentTop = list->top; Node* newTop;

if(currentTop == NULL) return;
else {
    newTop = list->top->prev;
    newTop->next = NULL;
    list->top = newTop;
}
list->size--;
free(currentTop->data);
free(currentTop);

}

Node* Top(LinkedListStack* list) { return list->top; }

➕ ** Queue **

** FIFO ** (First Input First Out)

• 가장 현생활에서 많이 쓰이는 구조이다.
• 먼저 줄 선 사람이 먼저 계산을 하는 것이다.
• 큐에서 삽입은 EnQueue, 삭제는 DeQueue 이라는 용어로 사용한다.
• BFS 탐색에서 사용

👉 코드 (연결리스트 이용 , c 로 구현)

#include<stdio.h>
#include<stdlib.h>

typedef char element;

typedef struct QNode { element data; QNode* link; }QNode; typedef struct LinkedQueue { QNode* front; QNode* rear; }LinkedQueue;

LinkedQueue* createLinkedQueue() { LinkedQueue* LQ = (LinkedQueue)malloc(sizeof(LinkedQueue)); LQ->front = NULL; LQ->rear = NULL; return LQ; } int isEmpty(LinkedQueue LQ) { if (LQ->front == NULL) return 1; else return 0; } void enQueue(LinkedQueue* LQ, element item) { QNode* new = (QNode)malloc(sizeof(QNode)); new->data = item; new->link = NULL; if (LQ->front == NULL) { LQ->front = new; LQ->rear = new; } else { LQ->rear->link = new; LQ->rear = new; } } element deQueue(LinkedQueue LQ) { if (isEmpty(LQ)) exit(1); else { QNode* old = LQ->front; element item = LQ->front->data; LQ->front = LQ->front->link; if (isEmpty(LQ)) LQ->rear = NULL; free(old); return item; } }

** 1. 행렬과 행렬의 연산 ** - 행렬 - 행렬의 합과 스칼라 곱 - 행렬의 곱

** 2. 특수한 행렬 ** - 대각 행렬 - 항등 행렬과 영행렬 - 전치행렬 - 대칭행렬과 교대행렬 - 삼각행렬

** 3. 행렬의 기본 연산과 사다리꼴 ** - 행렬의 기본 연산 - 행 사다리꼴 (Echelon Form) - 계수 (Rank) - 행렬의 표현과 응용

** 1. 행렬과 행렬의 연산 **

✔ 행렬

• 가로줄을 행(Row), 세로줄을 열(Column)이라고 부르며, m X n 행렬은 m개의 행과 n개의 열로 이루어진 행렬이다.

- 행벡터, 열벡터

• 행벡터 : [X1,...Xn] 1 X n 행렬
• 열벡터 : m X 1 행렬

✔ 행렬의 합과 스칼라 곱

- 행렬의 합과 차

• 두 행렬의 크기가 같아야만 연산 가능!
• 합 : A + B
• 차 : A - B (= A + (-B))

- 행렬의 스칼라 곱(Scalar Multiplication)

• 행렬 A에 실수 k를 곱하는 연산 => 행렬의 각 원소마다 k를 곱해준다.

- 상등(equal)한 행렬

• 두개의 행렬에서 각각 대응하는 항들이 모두 동일하다면 상등하다고 한다.

✔ 행렬의 곱(Multiplication)

• (m X n) 행렬인 A와 (n X p) 행렬인 B 경우 AB = C 라 할때, C 는 (m X p) 행렬이 된다.

• A의 열의 숫자(n) B의 행의 숫자(n)가 같을 경우에만 정의 된다.

  • AB 와 BA는 다른 값이다.(교환 법칙 성립 X)

• ex)

정리

• 곱셈의 결합 법칙 => A(BC) = (AB)C
• 배분 법칙 => A(B+C) = AB + AC
• 스칼라 곱 => k(AB) = (kA)B = A(kB)
• 행렬 곱셈의 항등식 => In = A = AI (I는 항등 행렬)

행렬의 거듭 제곱

• A가 nXn 행렬이고 k가 양의 정수라고 할때 A의 k승은 A를 k번 곱한느 것이다.

• A의 0승은 I(항등행렬)

  부행렬 (submatrix)

  

** 2. 특수한 행렬 **

✔ (n차) 정방행렬 (Square matrix)

• n 개의 행과 n개의 열을 가지는 행렬
• 주대각선 : 정방행렬에서의 다음과 같은 대각선을 ** 주 대각선(Main diagonal) ** 이라 부른다.
• 주 대각선 위의 모든 성분들을 대각항이라고 하고, 각 대각항의 합을 대각합(trace)라고 하며
• tr(A) 또는 trace(A)*로 표기한다.

대각합 특성

=> A와 B가 같은 크기의 정방행렬인 경우

• $\displaystyle \operatorname {tr} (cA)=c\operatorname {tr} (A)$
• $\displaystyle \operatorname {tr} (A)=\operatorname {tr} (A^{\operatorname {T} })$
• $\displaystyle \operatorname {tr} (AB)=\operatorname {tr} (BA)$
• $\displaystyle \operatorname {tr} (A+B)=\operatorname {tr} (A)+\operatorname {tr} (B)$

✔ 대각 행렬 (Diagonal matrix)

• 주 대각선 성분이 아닌 모든 성분이 0인 정방 행렬이다.

✔ 항등 행렬 (Identity matrix)

• 대각행렬이면서 대각선의 항들이 모두 1인 정방행렬을 항등행렬 또는 단위행렬이라 한다.
• 
• 

✔ 영행렬 (zero matrix)

• 성분이 모두 0인 행렬
• 기호로는 O로 적는다.
• A+O=O+A=A

✔ 전치행렬 (Tranpose matrix)

• 
• 
• 전치 행렬 성질

✔ 대칭행렬 (symmetric matrix)

• 정방행렬 n X n행렬이 자신의 전치 행렬과 똑같을때 대칭행렬이라 한다.
• 

✔ 교대행렬 (symmetric matrix)

• 
• 전치행렬에 음수를 곱한것과 같을 경우 교대행렬이라 한다.

✔ 삼각행렬 (Triangular matrix)

• 주대각선 위에 있는 모든 항들이 0인 행렬을 하부 삼각행렬
• 주대각선 아래에 있는 모든 항들이 0인 행렬을 상부 삼각행렬이라한다.
• 상부 삼각행렬의 전치는 하부 삼각행렬이고, 하부 삼각행렬의 전치는 상부 삼각행렬이다.

** 3. 행렬의 기본 연산과 사다리꼴 **

✔ 기본 행 연산(Elementary row operation)

• 행 동치 : 기본 행 연산을 필요에 다라 한번 또는 여러 번 거친 것
• 기본 행렬 : n X n 항등 행렬에서 한번의 기본 행 연산을 거쳐 만들어지는 행렬
• 피벗 : 행렬의 각 행에서 0이 아닌 가장 처음 나타나는 수를 행렬에서 피벗으로 삼을 수 있다.

✔ 행 사다리꼴(row echelon form)

m X n 행렬 A가 기본 행 연산들을 거친 후 다음 3가지 조건을 만족시키면 행 사다리꼴이라 한다.

• (1) 0으로만 이루어진 행들이 있는 경우, 행렬의 아래쪽에 나타낸다.

• (2) 모두가 0은 아닌 행의 가장 왼쪽에 가장 처음 나타나는 0이 아닌 수를 피벗으로 삼는다.
• (3) 모두가 0은 아닌 연이은 두 행이 있으면 아래쪽 행의 피벗은 위쪽행의 피벗보다 오른쪽에 있다

• 위 세개의 조건을 만족하면서 ** <각 행의 피벗을 포함하는 열에는 피벗 이외의 항들은 모두 0 이다 > ** 를 만족하면 ** "기약 행 사다리꼴"(reduced row echelon form) **라 한다.

✔ 기약 행 사다리꼴을 구하기 위한 기본 행 연산

• 전향단계(forward phase) : 피벗의 아랫부분이 0이 되도록 한다.

• 후향단계(backward phase) : 피벗의 윗부분까지 0이 되도록 한다.
• 전향 단계까지만 실행시 => 행 사다리꼴 (=가우스 소거법)
• 전향 단계 + 후향단계 실행시 (=가우스-조단 소거법)

- 계수(rank)

• 행 사다리꼴로 만들었을 때 <행 전체가 0이 아닌 행의 개수 = 피벗의 개수 = 계수>

** 1. 선형 대수와 선형 시스템 ** ** 2. 선형방정식의 소거법 **

고등 수학과 다를 것이 없는 내용이므로 이번 글에서는 위의 두개에 대하여 간단한 용어정리만 할것이다.

✔선형 대수학에서 다루게 될 내용 미리보기

• 선형 방정식

• 행렬 , 행렬식
• 벡터 , 벡터공간 , 내적과 외적, 고유값/고유벡터
• 선형변환

• *선형 방정식 * a₁x₁ + a₂x₂+ a₃x₃ + ... + anxn = bn

• *선형 시스템 *

  • 유한개의 선형 방정식의 집합을 선형 시스템이라고 한다.
  • 입출력 관계가 선형으로 주어지는 시스템
  • 중첩의 원리가 성립

• ** 동차 선형 시스템(homogeneous system) **

  • 선형 방정식에서 b1 = b2 ... bm = 0 일 경우를 말한다.

  • 이 경우 x1 = x2 ... xn = 0은 항상 동차 선형시스템의 해가 된다. ( = 자명해(trivial solution))

  • 만일 x1,x2,...xn 중 어느 하나라도 0 이 아닌 경우 비자명해(nontrivial solution)이라고 한다.

  • ** 동치(equivalent) ** 선형 방정식들이 똑같은 해를 가질 때 두 식이 동치라고 한다.

  • ** 선형 방정식의 소거법 **

    1. 한 방정식에 0이 아닌 상수를 곱한다.
    2. 방정식들의 위치를 서로 교환한다.
    3. 한 방정식에 0이 아닌 상수를 곱하여 다른 방정식에 더한다.

  ✔ ** 예시 1 ) **

  2 x₁+ x₂+ x₃= 5 4 x₁ - 6x₂= -2 -2x₁+7 x₂ + 2x₃ = 9

  ** 1) 전향 소거법 단계 ** 첫번째 식에 -2를 곱한 식 -4x₁-2x₂-2x₃= -10

  -4x₁-2x₂-2x₃= -10        4x₁ - 6x₂= -2

  ---

       -8x₂-2x₃ = -12

  2 x₁+ x₂+ x₃= 5         -8x₂-2x₃ = -12 -2 x₁+7x₂ + 2x₃ = 9

  1번째 식과 3번째 식을 더한다.

  결과 : -8x₂-2x₃ = -12 , 8x₂+ 3x₃ = 14 => x₃= 2

  ** 2) 역대입법 단계 ** x₃= 2를 1번째,2번째 식에 대입하여 x₂= 1, x₁ = 1 을 구한다

✔** 머신 러닝이란? **

• 컴퓨터를 인간처럼 학습시킴으로써 인간의 도움 없이 컴퓨터가 스스로 새로운 규칙을 생성할 수 있지 않을까?로 부터 시작 되었습니다.

• 기계를 어떻게 가르칠 것인가에 따라 크게 세가지로 나눠서 생각할 수 있습니다.

  • Supervised Learning(지도 학습)
  • Unsupervised Learning(비지도 학습)
  • Reinforcement Learning(강화 학습)

✔ Supervised Learning(지도 학습)

• 간단히 말해 여러 문제를 답과 같이 학습함으로써 미지의 문제에 대한 올바른 답을 예측하고자 하는 방법이다. 따라서 학습데이터에는 문제와 함께 정답까지 알고있어야 한다.

• 지도학습을 위한 모델은 크게 Classification(분류)모델과 Prediction(예측)모델로 구분된다.

  • ** Classification(분류) **: 연속적이지 않은 값, 즉 '무엇'을 예측 사용하는 알고리즘에 따라 KNN(K Nearest Neighbor), SVM(Support Vector Machine), Decision trees(의사결정 트리)등으로 구분 된다.
    • ** Prediction(예측) ** : 연속된 값, 즉 '얼마나'을 예측 Regression(회귀)모델이 대표적으로 사용되고 있다.

  => 분류모델은 학습데이터의 레이블(답)중 하나가 결과값이 되며, 예측 모델은 학습데이터에서 도출된 함수식에서 계산된 임의의 값이 결과값이 된다.

  ** Classification **

  • 레이블(정답)이 이산적인 경우로 숫자 인식, 번호판 인식, 스팸메일 구분등 정답이 가질 수 있는 값이 유한한 경우이다.

    Regression

  • 레이블(정답)이 실수인 경우로 특성들을 바탕으로 구분선을 찾아내는 방법
  • 데이터들을 쭉 뿌려놓고 이를 가장 잘 설명하는 직선 또는 이차함수 곡선을 그리고 싶을때 회귀 기능을 사용한다.
  • 선형회귀 기법이 가장 대표적이며 회귀 분석에서 종속변수란 결과값을 가리키며, 독립변수란 이러한 결과값에 영향을 주는 입력값(특성)들을 가리킨다.
    • *Simple Linear Regression Analysis(단순 선형 회귀 분석) *: 하나의 종속 변수, 하나의 독립변수 사이의 관계 분석
    • *Multiple Linear Regression Analysis(다중 선형 회귀 분석) *: 하나의 종속 변수, 여러개의 독립변수 사이의 관계 분석

✔ Unsupervised Learning(비지도 학습)

• 레이블(정답)이 정해져 있지 않은 데이터들을 기반으로 데이터의 고유한 구조나 패턴을 익히는 학습이다.
  • Clustering(군집화) : 대표적인 비지도 학습으로 데이터에서 패턴과 구조를 찾아 그룹을 지어준다.

✔ Reinforced Learning(강화 학습)

• 시행착오를 통해 학습하는 방법 중 하나로 실수와 보상을 통해 학습을 하여 목표를 찾아가는 알고리즘이다.

• 분할, 정복, 결합으로 문제를 2개의 작은 문제로 분할하고 각각을 해결한 다음 , 결과를 모아 원래의 문제를 해결하는 방법이다.
• 합병 정렬과 퀵 정렬이 해당된다.

🔨 합병 정렬

• 분할 정복 알고리즘의 하나로 힙 정렬처럼 비교에 기초한 정렬이며 O(nlog n)시간에 수행한다.
• 외부의 우선순위 큐를 사용하지 않고, 데이터를 순차적 방식으로 접근한다.

👉 ** 과정 **

1. 리스트의 길이가 1인 경우 이미 정렬된 것으로 본다. (재귀의 base case)
2. base case가 아닌경우 리스트를 절반으로 비슷한 크기의 두개의 리스트로 나눈다.
3. 두개로 나뉜 리스트들을 또 각각 재귀적으로 합병 정렬을 이용해 정렬해 준다.
4. 두개로 나뉜 리스트들을 다시 하나의 정렬된 리스트로 결합해준다.

👉 코드 (단일 연결리스트 이용)

mergeSort()

linkedList* mergeSort(linkedList* li) {
    linkedList* L1 = li;
    linkedList* L2;

    if (L1->num == 1) return L1;
    int k = (L1->num) / 2;

L2 = partition(L1, k);
L1 = mergeSort(L1);
L2 = mergeSort(L2);

return merge(L1, L2);

} linkedList * partition(linkedList* L, int k) { linkedList* re = init(); node* temp = L->Header; re->num = L->num - k; L->num = k;

while (temp && k > 0) {
    temp = temp->next;
    k--;
}

re->Header->next = temp->next;
temp->next = NULL;

return re;

} linkedList * merge(linkedList* L1, linkedList* L2) { node* tmp1 = L1->Header->next; node* tmp2 = L2->Header->next; linkedList * L = init(); node* tmp3; if (tmp1->key <= tmp2->key) {

    L->Header->next = tmp1; 
    tmp1 = tmp1->next;
}
else {
    L->Header->next = tmp2;
    tmp2 = tmp2->next;
}
tmp3 = L->Header->next;

while (tmp1 && tmp2) {
    if (tmp1->key <= tmp2->key) {
        tmp3->next = tmp1;
        tmp3 = tmp3->next;
        tmp1 = tmp1->next;
    }
    else {
        tmp3->next = tmp2;
        tmp3 = tmp3->next;
        tmp2 = tmp2->next;
    }        
}
while (tmp1) {
    tmp3->next = tmp1;
    tmp3 = tmp3->next;
    tmp1 = tmp1->next;
}
while(tmp2) {
    tmp3->next = tmp2;
    tmp3 = tmp3->next;
    tmp2 = tmp2->next;
}
L->num = L1->num + L2->num;
return L;

}

전체 코드

#include <stdio.h>
#include <stdlib.h>
>
//더미 노드 있는 연결리스트
>
typedef struct node {
    int key;
    struct node * next;
}node;
>
typedef struct linkedList {
    struct node* Header;
    int num;
}linkedList;
>
linkedList * init() {
    linkedList* li = (linkedList*)malloc(sizeof(linkedList));
    li->Header = (node*)malloc(sizeof(node));
    li->Header->next = NULL;
    li->num = 0;
    return li;
}
>
node* createNode(int key) {
    node* new = (node*)malloc(sizeof(node));
    new->key = key;
    new->next = NULL;
    return new;
}
>
void addNode(linkedList* li, int key) {
    node* new = createNode(key);
    node* temp = li->Header;
>
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = new;
    li->num++;
}
void printList(linkedList* li) {
    node* tmp = li->Header->next;
>
    for (int i = 0; i < li->num; i++) {
        printf(" %d", tmp->key);
        tmp = tmp->next;
    }
    printf("\n");
}
linkedList * merge(linkedList* L1, linkedList* L2) {
    node* tmp1 = L1->Header->next;
    node* tmp2 = L2->Header->next;
    linkedList * L = init();
    node* tmp3;
    if (tmp1->key <= tmp2->key) {        
        L->Header->next = tmp1; 
        tmp1 = tmp1->next;
    }
    else {
        L->Header->next = tmp2;
        tmp2 = tmp2->next;
    }
    tmp3 = L->Header->next;
>
    while (tmp1 && tmp2) {
        if (tmp1->key <= tmp2->key) {
            tmp3->next = tmp1;
            tmp3 = tmp3->next;
            tmp1 = tmp1->next;
        }
        else {
            tmp3->next = tmp2;
            tmp3 = tmp3->next;
            tmp2 = tmp2->next;
        }        
    }
    while (tmp1) {
        tmp3->next = tmp1;
        tmp3 = tmp3->next;
        tmp1 = tmp1->next;
    }
    while(tmp2) {
        tmp3->next = tmp2;
        tmp3 = tmp3->next;
        tmp2 = tmp2->next;
    }
    L->num = L1->num + L2->num;
    return L;
}
>
linkedList * partition(linkedList* L, int k) {
    linkedList* re = init();
    node* temp = L->Header;
    re->num = L->num - k;
    L->num = k;
>
    while (temp && k > 0) {
        temp = temp->next;
        k--;
    }
>
    re->Header->next = temp->next;
    temp->next = NULL;
>
    return re;
} 
>
linkedList* mergeSort(linkedList* li) {
    linkedList* L1 = li;
    linkedList* L2;
>
    if (L1->num == 1) return L1;
    int k = (L1->num) / 2;
>
    L2 = partition(L1, k);
    L1 = mergeSort(L1);
    L2 = mergeSort(L2);
>
    return merge(L1, L2);
}
>
int main() {
    int n;
    int key;
    linkedList* li = init();
>
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        addNode(li, key);
    }
    li = mergeSort(li);
>
    printList(li);
}

👉 합병정렬 알고리즘 시간 복잡도

** < 시간 복잡도 계산 > **

• 분할 단계 : 비교 연산과 이동 연산이 수행 되지 않는다.

• 합병 단계 : 이진 트리로 도식화 할 수 있다. 트리의 높이는 log n 이고 한번의 합병 단계에서는 n번의 비교연산을 한다.

• 이동 횟수: 깊이 (log n) * 이동 (2n) (=n개의 요소가 임시배열에 복사 된 뒤 다시 가져오므로) = 2nlog(n)

  • T(n) = nlog n(비교) + 2nlog n(이동) = O(nlog n)

  다음 표를 보면 (퀵정렬,힙정렬, 합병정렬) **은 다른 정렬에 비해 효율적** 이다는 것을 알수있다.

👉 합병정렬 알고리즘 특징

• 장점

  • 안정 정렬 로 중복된 값을 입력 순서와 동일하게 정렬 해준다.
  • 시간 복잡도가 좋은 편 이다.
  • 데이터의 분포의 영향을 덜 받는다.
  • 만일 연결리스트로 구성하면, 링크 인덱스만 변경하면 되므로 제자리 정렬이 가능하다.

• 단점

  • 배열로 정렬시 추가적인 리스트가 필요하다.(제자리정렬이 아니다)
  • 자료가 큰 경우 이동횟수가 많다.

👉 관련된 post

• 선택 정렬(selection sort) : Selection Sort
• 삽입 정렬(insertion sort) : Insertion Sort
• 힙 정렬(heap sort) : Heap Sort
• 합병 정렬(merge sort) : Merge Sort

1. 문제

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

2. 생각 과정

(다소 더럽긴하지만,,,,)

각 선수마다 bool배열을 만들어준다. 해당 bool배열은 해당 선수와의 대결에서 이겼는지 졌는지 알수있다면 true로 바꾼다. 위의 예시 5명의 선수를 예를 들면 2번 선수는 자기 자신과의 대결은 바로 true로 바꿔지고, 5와의 대결에서 승리하여 2,5가 true로 바뀐다. 그다음 누구한테 졌는가를 찾아보면 4,3,1에게 패배하여 4,3,1이 true로 바뀐다. 그러면 5개의 bool배열이 true로 되면 이는 2번 선수가 몇등인지 알수있다는 것이다.

먼저 각 선수들이 누구한테 졌는지 확인하고 그다음 누구한테 이겼는지 확인한다. 확인 과정은 bfs로 큐에 확인해야할 선수들을 넣어주는 방식이다.

bfs 과정을 말로 설명해보면, 예를 들어 5번 선수가 누구한테 졌는지 알아본다고 하자, results를 확인하면 5번 선수는 2번 선수에게 졌다는 걸 알 수있다. 그러면 2번 bool은 true가 되고 queue에 2번이 담긴다. 그리고 더이상 queue에 담을 선수가 없으니 2번을 pop해주면 2번에게 진 선수들 4,3,1이 모두 queue에 담기고 해당 bool은 true가 된다. 그러면 5번 선수의 bool배열은 1,2,3,4,5 모두 true가 되어 5번 선수의 등수를 알 수 있다는 것을 알수있다.

3. 풀이 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    vector<vector<bool>> info (n + 1 , vector<bool> (n + 1, false));

    // 대결 시 진 애들 표시
    for(int i = 1 ; i <= n ; i++){
        queue<int> q;
        q.push(i);
        info[i][i] = true;
        while(!q.empty()){
            int start = q.front();
            q.pop();

            for(vector<int> r : results){
                if(r[0] == start && !info[i][r[1]]){
                    info[i][r[1]] = true;
                    q.push(r[1]);
                }
            }
        }
    }

    // 대결시 이긴 애들 표시
    for(int i = 1 ; i <= n ; i++){
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int start = q.front();
            q.pop();

            for(vector<int> r : results){
                if(r[1] == start && !info[i][r[0]]){
                    info[i][r[0]] = true;
                    q.push(r[0]);
                }
            }
        }
    }

    for(vector<bool> bools : info){
        int i = 0;
        for(bool b : bools) {
            if(b == true) i++;
        }
        if(i == n) answer++;
    }                                       
    return answer;

}

문제풀이 글을 처음 쓰고 해서 풀이 생각과정을 말로 길게 써보았다. (질문 또는 지적이 있다면 댓글 남겨주시면 감사하겠습니다 🙇‍♀️)

🔨 먼저 힙(Heap)이란?

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위하여 고안된 완전 이진 트리를 기본으로 한 자료구조

  • 최대 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 크다.
  • 최소 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 작다. 키 값의 대소관계는 오로지 부모와 자식 관계에서만!! 형제사이에서는 안정해져있다 !

👉 이번 과정에서는 최대 힙을 이용한 내림차순 정렬을 알아보려고 한다

🔨 힙 정렬

• 최대 힙 트리 or 최소 힙 트리를 구성하여 정렬 하는 방법
• 내림 차순 정렬을 위해서는 최대힙을 구성, 오름차순 정렬을 위해서는 최소 힙을 구성

👉 ** 과정 **

** <내림차순의 경우> **

1. n개의 자료들로 최대 힙을 만든다.
2. 힙에서 root의 자료(최대값)를 꺼내서 배열의 뒤로 저장한다.
3. 다시 힙 정렬 (그 다음 최대값이 root로 정렬됨)
4. 위의 과정 반복 하면 감소되는 순서로 배열에 저장된다

👉 *최대 힙(Max Heap) 구현 (삽입식 힙) *

힙 구현시 연결리스트과 배열을 이용하여 구현 할 수 있다. 이번 과정에서는 배열을 이용한 순차 힙에 대해 다루겠다.

** 1. 최대 힙(max heap) 삽입 **

1. 새로운 요소가 들어왔을 때, 가장 마지막 노드에 이이서 삽입한다.
2. 힙 순서 속성 복구 ( 부모 노드들과 교환해서 제자리를 찾는다)

int H[101]; // 전역 변수 H배열
int n; // 전역 변수 요소 개수

void insertItem(int key) {
    n++;
    H[n] = key; // 마지막 노드에 삽입
    upHeap(n);
    printf("0\n");
}

//힙 순서 복구 (부모와 비교하여 교환)
void upHeap(int idx) {
    int parent = idx / 2; 
    int tmp;
    if (H[parent] < H[idx] && parent >=1) {
        tmp = H[parent];
        H[parent] = H[idx];
        H[idx] = tmp;
        upHeap(parent);
    }
    return;
}

** 2. 최대 힙(max heap) 삭제 **

1. 루트 노드(최댓값) 삭제
2. 삭제된 루트 노드에 힙의 마지막 노드를 가져온다
3. 힙 순서 속성 복구 (자식 노드들과 비교해서 제자리를 찾는다)

int H[101]; // 전역 변수 H배열
int n; // 전역 변수 요소 개수

int removeMax() {
    int key = H[1];
    H[1] = H[n--];
    downHeap(1);
    return key;
}
void downHeap(int idx) {
    int left = idx * 2;
    int right = idx * 2 + 1;
    int tmp;

    if (left <= n) {
        if (right <= n) {
            if (H[left] > H[right]) {
                if (H[idx] < H[left]) {
                    tmp = H[idx];
                    H[idx] = H[left];
                    H[left] = tmp;
                    downHeap(left);
                }
            }
            else {
                if (H[idx] < H[right]) {
                    tmp = H[idx];
                    H[idx] = H[right];
                    H[right] = tmp;
                    downHeap(right);
                }
            }
        }
        else {
            if (H[idx] < H[left]) {
                tmp = H[idx];
                H[idx] = H[left];
                H[left] = tmp;
            }
        }
    }
    else return;
}

👉 선택정렬 알고리즘 시간 복잡도

** < 시간 복잡도 계산 > **

• 완전 이진 트리의 경우 높이가 log n이므로 하나의 요소 삽입시 힙을 재정비 하는 시간이 log n만큼 소요
• 요소의 개수가 n개 이므로 전체적으로 O(nlog n)
• *T(n) = O(nlog n) *

다음 표를 보면 (퀵정렬,힙정렬, 합병정렬) **은 다른 정렬에 비해 효율적** 이다는 것을 알수있다.

👉 삽입정렬 알고리즘 특징

• 장점
  • 시간 복잡도가 좋은 편 이다.
  • 전체 자료 정렬이 필요한 경우가 아닌 가장 큰 값(작은 값) 몇개만 필요한 경우 매우 유용하다.

👉 관련된 post

• 선택 정렬(selection sort) : Selection Sort
• 삽입 정렬(insertion sort) : Insertion Sort
• 힙 정렬(heap sort) : Heap Sort
• 합병 정렬(merge sort) : Merge Sort