모두를 위한 딥러닝 강좌 시즌1을 통해 공부한 내용을 정리해봤습니다

Lec 00 - Machine/Deep learning 수업의 개요와 일정

 

 

나는 A나라의 대학생이다

(A나라에서는 공부한만큼 비례하여 성적이 나온다)

그래서 궁금해졌다 '이만큼 공부하면 성적이 얼마나 나올까?'

이럴때 사용할 수 있는 것이 Linear Regression이다

 

더보기

AI의 발전으로 우리는 이러한 문제에 쉽게 답할 수 있게 되었다

 

기존의 방식대로 하면 모든 조건에 대해 설계하고 통제해야 한다

하지만 AI를 사용하면 그럴 필요가 없어진다

AI가 학습하고, 답변을 내놓는다

 

이 문제를 풀어내기 위해선

공학도의 접근 방식이 필요하다

 

=> 문제를 새롭게 정의하기

 

예상 성적을 구하기 위해서는..

해당 조건에 가장 어울리는 직선을 찾으면 되지 않을까? 라는 가설을 세웠다

 

기존의 문제 정의 : 이 정도 공부했을때 성적이 얼마나 나올까?

새로운 문제 정의 : 조건을 만족하는 직선을 찾자!

 

A나라에서는

공부한 시간에 비례하여 성적이 나오기 때문에

해당 조건을 만족하는 직선의 방정식을 찾으면 된다

ax+b

 

가설을 h(x)라고 표현한다면

h(x) = ax + b 라고 쓸 수 있다

 

직선의 방정식에다가

공부한 시간을 넣어주면

예상 성적을 구할 수 있다

 

찾은 직선의 방정식이 3x+2일때,

x에 공부한 시간을 넣어준다

30시간이라고 하면..

3*30 + 2 = 90+2 = 92

92점을 받는다는 것을 알 수 있다

 

그럼 이런 직선은 어떻게 찾을 수 있을까

 

정답은..

데이터를 이용하면 된다

 

A나라의 학생들 3명에게 물어본 결과

공부시간     성적
10        28
15              40
20              65

 

이러한 데이터를 얻었다

 

좌표에 찍어보면 다음 그림과 같다

주어진 데이터를 가장 잘 표현하는 선 하나를 찾으면 된다!

무작위로 선을 하나 긋고

점과 선 사이의 거리들을 살펴본다 (여기서의 거리는 y좌표의 차이를 의미함)

 

선을 긋고 거리를 살피는 과정을 반복하면서

이 거리들이 가장 최소가 되는 선을 찾는다

그럼 아래와 같은 직선을 찾을 수 있다

이 선이 바로 우리가 찾던 직선이다

 

직선의 방정식을 수학적으로 표현하면 ax + b

즉 우리가 방금 한 과정을 수학적인 관점에서 본다면,

주어진 데이터를 가장 잘 표현하는 선을 찾는다 = 직선의 방정식에서 a와 b를 찾는다

라고 볼 수 있다

 

점과 선 사이의 거리 차이를 보는 과정으로 돌아가보자

이러한 거리 차이를 비용이라고 보겠다

우리는 비용이 최소인 직선을 찾으면 된다

 

비용을 cost(a,b) 라고 한다면

cost(a,b) = (실제 데이터값 - 우리가 예측한 값)^2  의 평균값

이고, 아래처럼 표현할 수도 있다

cost(x) = (Y - h(x))^2 의 평균값

 

제곱을 하는 이유는 접은글에서 확인

더보기

점 A와 점 B는 +2만큼 떨어져 있고

점 A와 점 C는 -2만큼 떨어져 있을때,

B랑 C는 같은 거리만큼 떨어져있다

하지만 제곱을 하기 전에는 다른 값을 가지고 있다

부호가 양수일때나 음수일때나

같은 값을 가지도록 하기 위해

제곱을 해준다 

 

절대값을 씌울수도 있겠지만

더욱 극명한 효과를 위해 제곱을 사용한다

 

cost(a,b)는 엄밀하게 살펴보면 무언가의 제곱 형태이다

그 안을 살펴보면 h(x) 즉 ax+b가 제곱되어있는 형태이므로

그래프로 그려보면 이차함수 모양을 확인할 수 있다

아래로 볼록한 이차함수가 된다

우리는 이 cost가 최소가 되도록 하는 a,b를 찾고 싶다

딱 봤을때 아래로 볼록한 저 부분이 최소값을 가지는 부분이다

 

그 부분에 특징은 바로 기울기가 0 이라는 것!

 

무작위로 시작하므로 기울기가 0인곳의 왼쪽 혹은 오른쪽에서 시작할 수 있다

어디에서 시작하든 우리는 기울기가 0인 곳으로 가면 되기 때문에

값을 수정해 나가면 기울기가 0이 되는 곳을 찾을 수 있다

 

비용이 최소가 되는 곳이다

즉 가장 알맞은 직선 ax+b를 찾은 것이다

 

드디어 예상 성적을 구할 수 있게 되었다

 

A나라에서 예상 성적 구하기 마침.

 

질문 환영합니다

1. 브루트 포스

브루트 포스 Part 1

브루트 포스 Part 2

브루트 포스 Part 3

 

2. 그래프와 BFS

그래프 알고리즘

BFS 알고리즘

 

 

3. 다이나믹 프로그래밍

 

4. 시뮬레이션과 구현

'알고리즘 > 문제모음집' 카테고리의 다른 글

백준 코딩 테스트 준비 - 연습  (2) 2023.01.07
백준 코딩 테스트 준비 - 기초  (2) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 2/2  (0) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 1/2  (0) 2023.01.07
백준 알고리즘 중급 3/3  (0) 2022.12.31

1. 브루트 포스 연습

 

브루트 포스 - 재귀

브루트 포스 - 순열

브루트 포스 - 비트마스크

브루트 포스 - 기타

2. 그래프와 BFS

 

그래프 알고리즘

BFS 알고리즘

3. 다이나믹 프로그래밍

4. 시뮬레이션과 구현

'알고리즘 > 문제모음집' 카테고리의 다른 글

백준 코딩 테스트 준비 - 문제  (0) 2023.01.07
백준 코딩 테스트 준비 - 기초  (2) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 2/2  (0) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 1/2  (0) 2023.01.07
백준 알고리즘 중급 3/3  (0) 2022.12.31

1.수학

주로 사용하는 수학 관련 알고리즘인 소수 판별, 최대 공약수

 

2. 브루트 포스

모든 경우의 수를 다 해보는 브루트 포스 알고리즘

모든 방법을 만드는 방법인 재귀, 순열, 비트마스크

재귀가 브루트 포스에서 가장 중요

브루트 포스

브루트 포스 - N과 M

브루트 포스 - 재귀

브루트 포스 - 순열

브루트 포스 - 비트마스크

 

3. 다이나믹 프로그래밍

다이나믹 프로그래밍의 개념과 점화식을 세우는 방법

다이나믹 프로그래밍 Part 1

다이나믹 프로그래밍 Part 2

 

4. 그래프와 BFS

가장 중요한 자료구조인 큐에 대해서 알아보고, 그래프와 DFS, 그리고 BFS

이후 BFS를 이용해서 풀 수 있는 문제들 연습

큐와 그래프

BFS

 

5. 시뮬레이션과 구현

시뮬레이션과 다양한 구현 문제

 

'알고리즘 > 문제모음집' 카테고리의 다른 글

백준 코딩 테스트 준비 - 문제  (0) 2023.01.07
백준 코딩 테스트 준비 - 연습  (2) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 2/2  (0) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 1/2  (0) 2023.01.07
백준 알고리즘 중급 3/3  (0) 2022.12.31

1330 - 다이나믹 프로그래밍 5

1331 - 다이나믹 프로그래밍 5 (연습)

1332 - 다이나믹 프로그래밍 5 (도전)

1610 - 세그먼트 트리와 펜윅 트리 2

1611 - 세그먼트 트리와 펜윅 트리 2 (연습)

1612 - 세그먼트 트리와 펜윅 트리 2 (도전)

1700 - 네트워크 플로우

1701 - 네트워크 플로우 (연습)

1710 - 네트워크 플로우 2

1720 - 최소 비용 최대 유량

1721 - 최소 비용 최대 유량 (연습)

1722 - 최소 비용 최대 유량 (도전)

'알고리즘 > 문제모음집' 카테고리의 다른 글

백준 코딩 테스트 준비 - 연습  (2) 2023.01.07
백준 코딩 테스트 준비 - 기초  (2) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 1/2  (0) 2023.01.07
백준 알고리즘 중급 3/3  (0) 2022.12.31
백준 알고리즘 중급 2/3  (0) 2022.12.31

1320 - 다이나믹 프로그래밍 4

1321 - 다이나믹 프로그래밍 4 (연습)

1322 - 다이나믹 프로그래밍 4 (도전)

1310 - 조합 게임 1

1311 - 조합 게임 1 (연습)

1500 - 문자열 알고리즘 2

1501 - 문자열 알고리즘 2 (연습)

1502 - 문자열 알고리즘 2 (도전)

1600 - 세그먼트 트리와 펜윅 트리

1601 - 세그먼트 트리와 펜윅 트리 (연습)

1602 - 세그먼트 트리와 펜윅 트리 (도전)

'알고리즘 > 문제모음집' 카테고리의 다른 글

백준 코딩 테스트 준비 - 기초  (2) 2023.01.07
백준 알고리즘 고급으로 가는 연결고리 2/2  (0) 2023.01.07
백준 알고리즘 중급 3/3  (0) 2022.12.31
백준 알고리즘 중급 2/3  (0) 2022.12.31
백준 알고리즘 중급 1/3  (2) 2022.12.31
 

11656번: 접미사 배열

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

www.acmicpc.net

문제 간단설명)

한 단어를 여러개로 쪼개고 사전순으로 정렬

 

풀이)

입력받은 단어를 substring() 이용해서 여러 접미사로 나눠주고,

이를 list에 넣어준다.

Collections.sort()안에 이 list를 넣어서 정렬한다.

Collections.sort()에 별다른 comparator 없이 리스트만 들어있다면 

그 list를 사전순으로 정렬한다.

만약 자신만의 방식으로 정렬하고 싶다면

comparator를 구현하여  Collections.sort()에 넣어주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        ArrayList<String> li = new ArrayList<>();
        for(int i = 0; i < input.length(); i++){
            li.add(input.substring(i));
        }
        Collections.sort(li);
 
        for(String s:li)
            bw.write(s+"\n");
        bw.flush();
        bw.close();
    }
}
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 10824 네 수 자바[java]  (4) 2023.01.07
백준 11655 ROT13 자바[java]  (0) 2023.01.07
백준 2743 단어 길이 재기 자바[java]  (0) 2023.01.07
백준 10820 문자열 분석 자바[java]  (2) 2023.01.07
백준 10809 알파벳 찾기 자바[java]  (0) 2023.01.07
 

10824번: 네 수

첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000)

www.acmicpc.net

문제 간단설명)

A B C D가 주어지면 AB + CD 값 출력

 

 

풀이)

핵심은 Long타입의 정수형과 Long.parseLong()...

 

입력 받은 값을 공백을 기준으로 배열에 저장한다.

첫 번째와 두 번째 배열 값을 합치고

정수형으로 변환한다.

세 번째와 네 번째 배열 값을 합치고

정수형으로 변환한다.

이때 Long.parseLong()을 사용한다.

1 ~ 1,000,000의 자연수가 주어지므로

합쳤을때 1조단위가 될 수 있다.

int형은 약 20억까지 가능하므로

더 큰 타입인 Long을 사용한다.

 

더보기

여태까지 Integer.parseInt()만 써봤었다.

자연수 범위도 제대로 안 보고 썼다가 틀렸다.

당황스러웠다. 

하지만 다시 보고 범위 문제임을 깨달았고,

혹시 Long.parseLong()도 있나 써봤더니 있었다.

예~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        String[] arr = input.split(" ");
 
 
        long a = Long.parseLong(arr[0] + arr[1]);
        long b = Long.parseLong(arr[2] + arr[3]);
        bw.write(String.valueOf(a+b));
        bw.flush();
        bw.close();
    }
}
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 11656 접미사 배열 자바[java]  (0) 2023.01.07
백준 11655 ROT13 자바[java]  (0) 2023.01.07
백준 2743 단어 길이 재기 자바[java]  (0) 2023.01.07
백준 10820 문자열 분석 자바[java]  (2) 2023.01.07
백준 10809 알파벳 찾기 자바[java]  (0) 2023.01.07
 

11655번: ROT13

첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다.

www.acmicpc.net

문제 간단설명)

소문자 대문자를 13칸 밀어서 출력.

 

풀이)

아스키코드를 참고했다.

>아스키코드는 더보기에..

소문자나 대문자를 입력받으면 +13 을 해주는데,

그 값이 대문자일때 90을 넘기거나, 소문자일때 122를 넘긴다면

26을 빼주고 출력한다.

나머진 그대로 출력.

 

아스키코드에 의해 컴퓨터에서 문자 'A'는 숫자 65와 같다.

그래서 13칸을 밀려면 65+13 = 78 인데 이를 문자형으로 출력하면 'N'이 나온다.

ROT13문제는 이를 이용하여 푼다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
 
        for(int i = 0; i < input.length(); i++){
            char ch = input.charAt(i);
 
            if(('a' <= ch && ch <= 'z')){
                ch += 13;
                if(ch > 122) ch -= 26;
                bw.write(ch);
 
            }else if('A' <= ch && ch <= 'Z'){
                ch += 13;
                if(ch > 90) ch -= 26;
                bw.write(ch);
            }else{
                bw.write(ch);
            }
        }
        bw.flush();
        bw.close();
    }
}
 
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 11656 접미사 배열 자바[java]  (0) 2023.01.07
백준 10824 네 수 자바[java]  (4) 2023.01.07
백준 2743 단어 길이 재기 자바[java]  (0) 2023.01.07
백준 10820 문자열 분석 자바[java]  (2) 2023.01.07
백준 10809 알파벳 찾기 자바[java]  (0) 2023.01.07
 

2743번: 단어 길이 재기

알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

문제 간단설명)

단어길이출력

 

풀이)

String타입에 구현되어있는 메서드인 length()로 단어 길이 구해서 출력한다.

BufferedWriter를 이용하는 경우 정수 출력은 String으로 해줘야한다.

1
2
3
4
5
6
7
8
9
10
11
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        bw.write(String.valueOf(input.length()));
        bw.flush();
        bw.close();
    }
}
 cs
 

'알고리즘 > 백준' 카테고리의 다른 글

백준 10824 네 수 자바[java]  (4) 2023.01.07
백준 11655 ROT13 자바[java]  (0) 2023.01.07
백준 10820 문자열 분석 자바[java]  (2) 2023.01.07
백준 10809 알파벳 찾기 자바[java]  (0) 2023.01.07
백준 10808 알파벳 개수 자바[java]  (0) 2023.01.07

+ Recent posts

티스토리툴바