전공/Computer Science13 [알고리즘과 자료구조] 07. 삽입 정렬과 합병 정렬 및 재귀적 알고리즘의 복잡도 내용 정리 오늘은 Insertion Sort와 merge sort에 대해 배웠다. 필기 먼저 봅시다. 우리가 algorithm을 배울 때 Sorting문제를 많이 배우는 이유는 sorting problem이 다양한 algorithm 접근법을 제시하는 간단한 예제이기 때문이다. Insertion Sort는 이름과 같이 새로운 element를 삽입하며 정렬하는 알고리즘인데, 우리 수업에서 두 가지 구현 방법을 배웠다. 아참 여기서 하나의 element는 정렬된 상태라고 가정한다. 첫번째는 새로운 element를 앞의 list의 변수 하나하나와 비교하여 swap한다. 이렇게 하면 코드에서 알 수 있듯이 복잡도가 O(n^2)으로 복잡하다. 두번째는 보다 효율적으로 변수를 사용하여 shift시키다가 적절한 위치에.. 2022. 2. 26. [알고리즘과 자료구조] 06. 알고리즘 복잡도 분석 내용 정리 오늘은 asymtotic analysis에 대해 배우고 여러가지 알고리즘의 복잡도를 표현하는 notation에 대해 배웠다. 6주차 수강 후기 5주차에도 3주차와 마찬가지로 과제가 있는데 생각보다 너무 어렵다. 완전 코딩테스트 문제인데 아마도 C++로 구현하는 것이 과제겠지... 2022. 2. 24. [자료구조와 알고리즘] 05.함수의 점근적 분석 내용 정리 오늘은 asymtotic analysis에 대해 배우고 여러가지 알고리즘의 복잡도를 표현하는 notation에 대해 배웠다. 5주차 수강 후기 5주차에도 3주차와 마찬가지로 과제가 있는데 생각보다 너무 어렵다. 완전 코딩테스트 문제인데 아마도 C++로 구현하는 것이 과제겠지... 이게 본 과목이었다면 properties of notation들을 달달 외웠겠지만 자율적인 공부라 확실히 부담이 덜하다. 논리적으로 모두 이해한 것들이니 괜찮다고 생각하지만 그래도 더 열심히 봐야하나 싶다. 아무리 가볍게 스스로 하는 공부라지만 그래도 제대로 아는 것이 좋으니까.. 2022. 2. 22. [자료구조와 알고리즘] 04.그래프 탐색 알고리즘 내용 정리 오늘은 nonlinear한 자료구조인 그래프를 탐색하는 두 가지 알고리즘을 배웠다. 너비를 우선적으로 탐색하는 탐색 기법(BFS)과 깊이를 우선적으로 탐색하는 기법(DFS)인데, 각각 queue와 stack을 사용하여 구현할 수 있다. 그 구현 방법도 교수님과 함께 직접 프로그래밍해봤다. 4주차 수강 후기 벌써부터 위기였다. 솔직히 4주차 내용자체는 없는데 코딩할 때 자꾸 졸게 돼서 여러 번 다시 들었다. 허재필교수님께서 C++에 엄청 능숙해 보이셨다. 그런데 스스로 다시 짜보라고 하면 못할듯... 그래도 BFS와 DFS는 확실하게 알게 되었다. 2022. 2. 18. [알고리즘과 자료구조] 03. 비선형 자료구조 내용 정리 오늘은 2주차 linear 자료구조에 이어 non-linear 자료구조를 살펴보았다. 생각보다 알아야 할 용어가 많아서 필기가 길어졌다. 3주차 수강 후기 3주차에는 간단한 과제가 있었다. 참여하지 못하는 게 아무리 생각해도 아쉽다. 일상생활에서 마주하는 문제들 중 스택이나 큐 자료구조를 사용하고 있거나 이를 사용하여 해결할 수 있는 문제의 예시를 찾아보고 이를 논의해보자. 우리집 흰양말을 사용할 때 stack자료구조처럼 Last in First out된다. 무선통신을 할 때 시간 축에 대하여 큐를 사용하여 FIFO 순서대로 처리할 수 있다. 그리고 아래 사진은 강의 자료의 일부인데, 아무리 봐도 틀린 것 같다. graph의 connected를 살펴보는 문제인데 strongly고 weakly고.. 2022. 2. 17. [알고리즘과 자료구조] 02. 선형 자료구조 내용 정리 오늘은 linear 자료구조 몇 가지와 이를 이용한 코드 몇 개를 살펴보았다. 코드와 함께 call by value와 call by reference등 개념도 배웠다. array int scrore[10]; 위 문장을 이용해 정적으로 array를 할당할 수 있다. data type, array name, array size가 필요하다. 그렇게 하면 index순으로 연속적인 memory공간이 할당된다. 한편 아래와 같이 동적으로도 array를 할당할 수 있다. int *score = new int [10]; 저기서 star(*)를 dereference operator라고 하는데 한국어로 '역으로 참조된 연산자', 즉 '포인터 연산자'라고 한다. 저렇게 주소값을 참조하여 할당하면 배열의 길이 등을.. 2022. 2. 16. 이전 1 2 3 다음 반응형
