백준4 3강 수학 1 - 수학 1 이번엔 3강이다! 얼른 듣자!! 이번 강의에서는 알고리즘을 공부할 때 필요한 기초적인 수학 관련 내용이었다. 그 중에서도 나머지연산, 최대공약수, 소수와 팩토리얼에 대해 배웠다. -나머지 연산 나머지 연산은 말 그대로 수의 나머지를 구하는 연산이다. 나머지 연산을 할 때 연산을 다해서 나머지를 구하면 오래걸리기도 하고 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에 직접 연산하지 않고 나머지만 구한다. (직접 연산하는 경우 int나 long long과 같은 자료형의 범위를 넘어갈 수 있다) > (A+B) % M = ((A%M) + (B%M)) % M > (A*B) % M = ((A%M) * (B%M)) % M 이는 나누기의 경우에는 성립하지 않는다. 또한 빼기의 경우에는 음수가 나올 수 있기.. 2020. 8. 19. 2강 자료구조 1 - 연습 이번 강의는 지금까지 배운 자료구조의 연습문제를 풀어보는 시간을 갖도록 한다. 주로 스택을 다루는 문제를 풀어본다고 한다. 이 문제는 단어 뒤집기 문제와 비슷하지만 다른 점은 태그가 있다는 점이다. 태그 안에 있는 단어는 뒤집지 않고 밖에 있는 단어만 뒤집어준다. 그래서 단어 뒤집기 문제에서 태그 판단만 추가를 해주고 나머지는 거의 동일하게 구현하면 된다. 이 문제의 Worst case는 모든 단어가 스택에 추가되는 경우이기 때문에 시간 복잡도는 문자열의 길이가 N이라고 할 때, O(N)이 된다. 조금 헷갈리긴 했는데 출력, tag가 true면 뒤집지말고 그대로 출력, 아니면 공백이 아닌 경우에는 스택에 단어 넣어두고 공백이면 스택 출력. 이렇게 하면 된다! 1 2 3 4 5 6 7 8 9 10 11 1.. 2020. 8. 16. 2강 자료구조 1 - 스택 자료구조 1 강의에서는 크게 스택, 큐, 덱에 대해 배우는데 스택을 주로 다루고 큐와 덱은 그래프(BFS)에서 자세하게 다룬다고 한다. 스택(Stack)이란 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. LIFO(Last in First Out)라고도 부른다. 그래서 나중에 들어간 데이터가 제일 먼저 나올 수 있다. 위의 그림처럼 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조로 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO라고 한다. 따라서 만약 데이터를 저장하고 가운데에 저장한 데이터를 pop해야 하는 연산이 필요하다면 이는 스택을 사용하면 안되는 알고리즘이다. 다음은 스택 연산이 종류이다. - push : 스택에 자료를 넣는 연산 - pop : 스택에서 자료를 빼는 연산 - .. 2020. 8. 9. 1강 - 알고리즘 시작 강의를 들을까 말까 고민하고 있는데 밍구가 선뜻 자기 아이디를 알려주었다! 뭔가 미안한데 고맙고 음... 그래서 그냥 강의 살 돈으로 밍구 맛있는거 많이 사줘서 갚기로 했다ㅋㅋㅋ 사룽해 밍구 ios_base::sync_with_stdio(false); -> cin.tie(NULL); -> cout.tie(NULL); 보통 위의 두 줄만 추가해도 충분히 속도가 빨라지고 아래의 두 줄은 cin.tie(nullptr)/cout.tie(nullptr)로도 많이 쓰인다고 한다. 위의 경우를 사용할 경우에는 scanf/printf를 사용하면 안되고 오직 cin/cout만 써야 하므로 주의하자! - cout을 사용할 때 개행문자로 endl을 사용하는데 이를 사용하는 것보다 '\n'을 사용하는 것이 훨씬 속도가 빠르다.. 2020. 8. 6. 이전 1 다음
