본문 바로가기
1강 행렬과 행렬식 행렬 대문자로 표기 소괄호를 쓰든, 대괄호를 쓰든 상관 없음 ex) $$A=\begin{pmatrix} 1 & 2 & 3\\ a & b & c \end{pmatrix}=\begin{bmatrix} 1 & 2 & 3\\ a & b & c \end{bmatrix}=\begin{vmatrix} 1 & 2 & 3\\ a & b & c \end{vmatrix}$$ (1) 용어 정리 성분: 행렬 안에 배열된 구성원(=항=원소) $a_{ij}$는 i번째 행, j번째 열 행(row): 행렬의 가로줄 열(column): 행렬의 세로줄 mXn 행렬: m개의 행과 n개의 열로 이루어진 행렬. 'm행 n열 행렬'이라고 읽으면 된다. $(a_{ij})_{m \times n}$ 또는 $(a_{ij})$로 표기할 수 있다. 주대각..
0강 수학의 절반. 선형대수 선형대수학이란? 선형대수의 역사 요약 1750년경 "크래머의 공식" 1800년경 "가우스 소거법" 1850년경 케일리, 실베스터 "행렬이론" 위 순서를 거쳐 20세기 부터 대학 수학의 기본 과목으로 정립 선형대수학이란? "행렬"과 "벡터"라는 수학 대상을 연구하는 학문 선형대수학의 중요성 군론, 추상대수학, 함수해석학 등 다양한 수학 과목의 출발점 미적분학과 더불어 수학이라는 세계를 이루는 주요 과목 과학, 공학, 컴퓨터공학, 경영, 경제, 사회과학 등과 같은 분야에서 활용 행렬 처음에는 행렬을 연립방정식을 풀기 위한 도구로 다루기도 하겠지만, 그것은 어디까지나 행렬에 익숙해지기 위함 행렬은 그 자체로도 수학의 대상 많은 분야에서 실질적인 응용의 열쇠 앞서 선형대수학은 과학, 공학 등의 분야에서 활용된다..
[백준 C++] 11053, 12015 가장 긴 증가하는 부분 수열 1, 2 가장 긴 증가하는 부분 수열 1 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 자료 출처 1. [최장 증가 수열] LIS(Longest I..
[백준 C++] 9935번 문자열 폭발 문자열 폭발 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 자료 유형 : 스택인 줄 알았지만 문자열을 다루는 것이 핵심 문자열과 함께 나도 폭발했다. 수 차례 WA를 받고 주먹구구 식으로 코드를 고쳐나가는 내 모습이 비참했다. 문자열과 폭발 문자..
[백준 C++] 7785번 회사에 있는 사람 7785번 회사에 있는 사람 7785번: 회사에 있는 사람 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성 www.acmicpc.net 문제 유형 : set 시간 복잡도 : nlogn 아래와 같이 n과 n만큼의 출퇴근 로그가 주어진다. 로그는 직원의 이름과 enter 혹은 leave로 주어지며, 현재..
[백준 C++] 나는야 포켓몬 마스터 이다솜 나는야 포켓몬 마스터 이다솜 문제 분류 : map(unordered_map) 전에 brute force로 풀려고 하다가 시간초과로 못 풀었던 문제다. map을 배우고 나니 풀 수 있을 것 같아서 시도해봤다. N개의 포켓몬 이름(string)을 입력받고, M개의 int 혹은 string을 입력받는다. int라면 int를 index로 삼아 포켓몬의 이름을 출력하고, string이라면 해당 포켓몬의 index를 출력하면 된다. 1. '이름 -> 인덱스'나 '인덱스 -> 이름' 중 하나만 해도 되는 것이라면 map 하나만 써서 손쉽게 해결할 수 있지만, 둘 다를 요구하기 때문에 string을 저장해놓는 별도의 array를 만들어야 한다는 점이 까다로웠다. 2. cin, cout보다 printf, scanf가 유..
레드블랙 트리(red-black tree) 0. 출처 1) [알고리즘] 제12-1강 red black tree1 2) [알고리즘] 제12-2강 red black tree2 3) [알고리즘] 제12-3강 red black tree3 4) Introduction to Algorithms 1. 개요 1. 1 레드블랙 트리란 이진 탐색 트리에서 탐색, 삽입, 삭제의 시간 복잡도는 O(h)이다. 즉, 트리의 높이에 비례한 만큼의 시간이 걸린다. 원소들이 트리에 잘 분산되어 있다면 별 문제가 없으나, 한 쪽으로 치우친 트리(skewd tree)의 경우에는 높이가 n이 되고, 시간 복잡도도 O(n)이 된다. 랜덤하게 만들어진 이진 탐색 트리는 높이가 lgn임이 보장되나, 현실에서의 데이터는 랜덤하지 않다는 점이 문제가 된다. 예를 들어, 키가 정렬된 상태(1..
[std]set, map set set은 고유한 키를 특정한 순서로 저장하는 컨테이너다. set에 저장되는 원소들은 항상 const와 저장되기 때문에 수정할 수 없다. (삽입이나 삭제는 가능) strict weak ordering criterion에 따라 정렬된다고 하는데 무슨 말인지 모르겠다. 먼저, 을 include해야 한다. int를 저장하는 set은 다음과 같이 만들면 된다.(오름차순) set s; 내림차순으로 정렬하려면 다음과 같이 하면 된다. set s; 오름차순으로 정렬되는 set을 정의했다면 아래와 같이 넣고 출력해도 10, 20, 30, 40, 50이 출력된다. s.insert(10); s.insert(50); s.insert(20); s.insert(40); s.insert(30); 원소를 출력하는 것은 다음과..

티스토리툴바