조준화의 오류정정

https://www.youtube.com/watch?v=vT1JzLTH4G4&list=PLC1qU-LWwrF64f4QKQT-Vg5Wr4qEE1Zxk&index=3스탠포드 대학교의 유명한 컴퓨터 비전 강의를 보고 정리한 글입니다.https://www.youtube.com/playlist?list=PLetSlH8YjIfXMONyPC1t3uuDlc1Mc5F1ACS231n 강의와 서울대학교 DSBA 연구실의 강의를 참고하여 공부한 부분을 정리하였습니다.이번 강의를 들으면서 처음 AI 공부를 시작했고, 그만큼 틀린 부분 해석이 모호한 부분이 있을 수 있습니다.1. IntroductionImage classification전체 이미지 한 장에 대해 어느 클래스에 속해있는지 분류하는 작업이다.예를 들어 한 장의 사..

데이터베이스를 설계할 때 테이블을 바로 만드는 것이 아니고, 테이블을 설계할 때부터 근거가 있어야 한다.그 첫 단계가 바로 ER 다이어그램이다. 데이터베이스의 설계 과정은 다음과 같다.인터뷰나 업무에 대한 문서를 보고 분석한다.요구사항 수집이 단계에서 요구사항이 무슨 엔티티, 테이블이 필요하고 그런 형태가 아니라 학생들은 무슨 과목을 수강할 수 있어야 한다. 와 같은 방식이다.요구사항은 굉장히 일반적인 단어 예를 들어 학생, 필수 과목, 이런식으로 일반인들이 사용하는 일반적인 단어로 구성된다.요구사항을 바탕으로 ER 다이어그램 모델링ER 다이어그램으로 테이블 구성만들어진 테이블의 중복성을 제거하기 위해 normalization 수행정규화의 핵심은 테이블을 분리시켜서 중복성을 제거하는 것이다.정규화된 테이..

1. Data models, Schemas and InstancesData modelsData Model데이터베이스의 structure, operations, constraints를 설명하기 위한 concepts의 집합이다.Data Model Structure and Constraintsdatabase structure를 정의하기 위해 Constructs가 사용된다.Constructs는 type을 가지는 elements와 elements의 그룹인 record(entity, table), 각 그룹들 간의 relationship를 포함한다.예를 들어, 학생 data가 다음과 같이 구성된다고 생각해보자. [이름, 학번, 연락처, 학과] 여기서 이름, 학번 등이 element가 되고 이름의 type은 strin..

1. Types of Database and Database Applications초창기 데이터베이스에서는 정형화된 Numeric, Textual Data만 다루었다. 이를 바탕으로 만들어진 데이터 베이스 시스템이 잘 상용화되면서 규칙성이 없는 비정형 데이터까지 확장시키려 노력하고 있다. Multimedia, 지도 데이터 등등…하지만 이 과목에서는 정형화된 Numeric, Textual Data에 초점을 맞출 예정이다.2. Basic DefinitionsDatabase관련된 데이터들의 집합Data사실들Mini-world데이터베이스 시스템은 전체 세상이 아닌 일부만을 모델링 하게 된다. 특정 부분의 문제를 해결하기 위해 특정 부분만 떼어낸 것을 Mini-world라 한다.DBMS데이터베이스를 관리해주는 시..

예제454430 2 2 22 0 3 32 3 0 42 3 4 0출력 : 9MST 문제인데 MST 문제는 구현도 어렵지만 왜 MST인지 잘 판단해야 한다. 논을 파는 방법은 직접 논에 우물을 파거나 다른 논에서 끌어오는 방법이 있다.당장 떠오르는 방법은 그리디 하게 가장 싼 우물을 파되, 불필요하게 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야 한다. 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야한다는 점에서 MST를 떠올렸고 프림 알고리즘을 선택했다. 알고리즘은 다음과 같다.우물을 파는 비용을 모두 우선순위 큐에 넣는다.우선순위 큐에서 논을 하나 빼서 MST에 포함시킨다.MST에 포함된 논의 간선 중 MST가 아닌 논과 연결된 간선을 우선순위 큐에 넣는다.N개의 논에 대해 N-1개의 간선이 MST..

이전 글에 이어지는 글입니다. [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Sjun-n.tistory.com크루스칼 알고리즘에 이어서 프림 알고리즘을 알아보자. 임의의 정점을 선택해 최소 신장 트리에 추가최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가최소 신장 트리에 V-1 개의 간선이 추가될 때까지 2번 과정을 반복방법 자체는 크루스칼과 유사..

[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Spanning이나 신장 이 단어가 너무 낯설지blog.encrypted.gg바킹독님 블로그를 참조하여 쓴 글입니다. 신장 트리란?신장 트리는 무방향 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리이다. 사진의 왼쪽 그래프에서 오른쪽 그래프는 모두 신장 트리이다. 신장 트리라 하면 당연히 연결 그래프가 되겠고, 트리이므로 당연히 사이클이 존재해선 안된다. 최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 말한다. 최소 신장 트리는 동일한 그래프에서 여러 개 존재할..

https://www.acmicpc.net/problem/2637 예제785 1 25 2 27 5 26 5 26 3 36 4 47 6 37 4 5출력 : 1 162 163 94 17하나의 완제품을 완성하는데 필요한 기본 부품의 수를 구하는 문제이다. 어떤 부품이 기본 부품인지를 구하고, 중간 부품을 기본 부품으로 치환하는 방식으로 풀이를 떠올렸다. dp를 사용한 방식인데 2차원 배열로 dp 배열을 선언해서 dp [i][j]를 i번 부품을 만드는데 필요한 j 부품의 수 (j는 기본 부품)로 생각하고 구현했다. 해당 풀이의 점화식은 다음과 같다.i번 부품에 대해(i는 중간 부품) dp[i] = dp [next.first] * next.second. next는 i번 부품을 만드는데 필요한 부품이다. 백준에서 ..

https://www.acmicpc.net/problem/21276문제를 보고 떠올린 방법은 다음과 같다.indegree를 측정하는데, 편하게 측정하기 위해 string -> int로 index를 가지고 있는 map list를 생성하였다.indegree가 0인 노드가 가문의 시조가 되고, 위상 정렬을 하면서 사전순으로 방문해야 한다.위상 정렬을 하면서 하나 방문하고 직계 자식을 구해야 하는데, 직계 자식은 indegree가 1이어야 한다. 즉, 현재 노드와 현재 노드와 연결된 간선을 제거했을 때 indegree가 0인 노드가 직계 자식이다.이 정도로 알고리즘을 생각해 두고 구현해 봤는데 정렬을 하면서 직계 자식을 구하고, 위상 정렬을 수행하고 하는 과정이 너무 번거롭고 시간 복잡도 상으로 비효율적이었다...

[실전 알고리즘] 0x1A강 - 위상 정렬안녕하세요, 이번 시간에는 위상 정렬을 다뤄보도록 하겠습니다. 위상 정렬이 무엇인지도 소개해드릴거고 구현과 연습 문제도 다룰 예정입니다. 위상 정렬의 본격적인 정의를 배워보기 전에 실blog.encrypted.gg바킹독님의 블로그를 보고 이해한 부분을 정리한 글입니다.위상 정렬이란 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 정렬하는 방법이다. 대표적인 예시로 교과 이수 제도가 있다. 선수 과목을 다 들어야 다음 과목을 이수할 수 있다는 것인데, 이 선수과목이 서로 겹치는 경우가 있다. 이게 실제 선수과목인데 이를 트리로 나타내보자. A -> B라면 A를 듣고 나서 B를 들어야 한다는 의미로 그려보았다.복잡한 부분만 나타내면 이렇게 될 텐데..