https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리를 2차원 vector로 구현하였다. 클래스로 트리를 만드는 것도 고민해봤는데 아직 거기까진 구현을 안해봐서 간단히 벡터로 구현하기로.. 문제에 주어지는 노드의 관계는 순서 상관없이 무작위로 주어진다. > n; tr.resize(n + 1); for (int i = 0; i > x >> y; tr[x].push_back(y); tr[y].push_back(x); } parents(1); for (int i = 2; i

Vector (array list) cf. python에는 array를 대신해서 array list가 들어가있다. 좀 더 유저 친화적인 High-level array ADT이다. 벡터 ADT가 가진 함수들(배열과 유사함) : at(i) : V(벡터)의 i번째 요소 return. i가 범위를 벗어날 경우 에러 발생 set(i, e) : i번째 요소를 e로 바꾼다. i가 범위를 벗어날 경우 에러 발생 insert(i, e) : V의 i번째에 새로운 요소 e를 삽입한다. i가 범위를 벗어날 경우 에러 발생 erase(i) : V의 i번째 요소를 지운다. i가 범위를 벗어날 경우 에러 발생 복습 Array에서 insert, erase(add, remove) : O(n) space used by the data ..

Array add(i, o) : i번째 자리에 o를 추가하는 함수 ( size = n )요소를 n-i번 이동시켜야 한다.첫번째 인덱스에 넣는다고 가정하면, 들어있는 n개의 요소를 모두 옮겨줘야 한다. worst case : i = 0 , f(n) = n O(n) remove(i) : i번째 자리를 지우는 함수 요소를 n-i-1번 이동시켜야 한다. 첫번째 인덱스를 지운다고 가정하면, n-1개의 요소를 당겨줘야 한다. worst case : i = 0 , f(n) = n-1 O(n) 단순히 요소에 접근하는 것은 O(1) : Global Dynamic Array Array는 static하다 - 실행하는 동안 size의 변화가 불가능하다. dynamic array - growable : array가 꽉찬 경우에..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net n!에서 r의 개수를 구하는 방법을 이용 예시) 10!, 2 10/2 = 5 5/2 = 2 2/2 = 1 10 9 8 7 6 5 4 3 2 1 1 3 1 2 1 2가 여러번 곱해진 수는 곱한 횟수 만큼 나누어 떨어진다. #include #include using namespace std; int cnt(int n, int r) { int count = 0; while (n) { n /= r; count += n; } return count; } int main() { unsigned..

간단한 구현 연습 Singly Linked List Stack에서 top의 위치는 head size : 스택에 저장된 정수의 개수를 출력한다. empty : 스택이 비어 있으면 1, 비어 있지 않으면 0을 출력한다. top : 스택의 가장 위에 저장된 정수를 출력. 만약 스택이 비어 있는 경우, -1을 출력한다. push X : 정수 X(단, 1 ≤ X ≤ 10,000)를 스택에 삽입한다. pop : 스택의 가장 위에 저장된 정수를 출력하면서 삭제. 만약 스택이 비어 있는 경우, -1 을 출력한다. t번 명령어 작동 #include using namespace std; class Node { Node* next; int data; friend class SinglyLinkedStack; }; class ..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net #include #include using namespace std; int main() { int n, m; cin >> n >> m; queue q; for (int i = 1; i

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net n!에서 2와 5의 개수(1)와 k!과 (n-k)!에서 2와 5의 개수(2)를 구하면 0의 개수를 알 수 있다. (1) - (2)를 한 뒤, 2의 개수와 5의 개수 중 작은 쪽의 개수가 0의 개수이다. 원하는 수가 몇번 나왔는지 구하는 cnt 함수를 작성한다. 10!에서 2의 개수를 구해보자. 10/2 = 5개 - 2,4,6,8,10 (2^1) 5/2 = 2개 - 4, 8 (2^2) 2/2 = 1개 - 8 (2^3) (2의 배수를 카운팅) #include ..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net #include #include using namespace std; int main() { string str; getline(cin, str); int size = str.length(); int i = 0, cnt = 0; int answer = 0; while (i < size) { if (str[i] == ')') { if (str[i - 1] == ')') { //막대기 끝났을 때 answer +..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net #include #include #include #include using namespace std; int main() { char ch; int check = 0; string str; stack s; while (true) { getline(cin, str); if (str[0] == '.') break; for (int i = 0; i < str.length(); i++) {..

https://opentutorials.org/course/3086 WEB2 - CSS - 생활코딩 수업소개 이 수업은 https://opentutorials.org 를 만들어가면서 CSS에 대한 지식과 경험을 동시에 채워드리기 위한 목적으로 만들어진 수업입니다. 수업대상 이 수업은 웹 페이지를 아름답게 디자인 opentutorials.org 위의 강의 복습용 포스팅입니다. 아직 작성중 CSS - html의 문법에 태그를 추가하는 대신 디자인을 맡는 프로그램을 제작하게 되었다 선택자 우선순위 tag id값은 단 한 번 등장해야함 모든 a 태그 선택 vs 하나의 id 선택 => tag 선택자는 id 선택자보다 포괄적..

https://opentutorials.org/course/3084 WEB1 - HTML & Internet - 생활코딩 --- 우리는 지금부터 코딩 웹 인터넷 컴퓨터라는 거대한 주제에 대한 탐험을 시작할 거예요. 이 여행을 시작하기에 앞서서 한가지 준비가 필요한데요. 바로 우리들의 상상력입니다. 지금부터 여 opentutorials.org 위의 강의 복습용 포스팅입니다. 아직 작성중 인터넷을 여는 열쇠 : 서버와 클라이언트 두 대의 컴퓨터 , 두 개의 프로그램 1번엔 Web Browser, 2번엔 Web Server(http://info.cern.ch, index.html) Web Browser에 http://info.cern.ch/index.html 입력 -> 인터넷을 통해서 info.cern.ch에..

elementary linear algebra 9th edition의 내용을 개인 공부용으로 나름대로 이해하고 정리한 것 -Linear Equations (선형 방정식) 최고 차수의 항의 차수가 1을 넘지 않는 다항 방정식. b가 0인 경우에, homogeneous linear equation 이라고 한다. (동차 연립방정식) -General Linear m개의 방정식, n개의 미지수 Solution = 해 -Linear Systems in Two Unknowns 두 개의 미지수를 가질 때, solution은 세 가지 경우가 가능하다. 1. No solution 두 직선이 평행하여 교점이 존재하지 않을 때 2. One solution 두 직선이 하나의 교점을 가질 때 3. Infinitely many s..