AIB 섹션 5 컴퓨터공학 스프린트 2 랩업

내 컴퓨팅 사고력이 달라졌을까 싶음. 논리적으로 사고를 해야 하는데, 그 사고하는 부분이 글케 많았나 싶다. 문제해결능력도 이론적으로 의사코드를 적어볼 수는 있고, 재귀나 divide-and-conquer도 방법도 배웠지만 이걸 크게 써먹어야 겠다는 생각은 막 와닿지는 않음. 많이 해봐야 느는데, 많이 안 해봄…

일단 노트정리좀 자세히 해봐야겠다. ㄹㅇ 간략하게 매일 강의마다 노트를 적긴 했지만 되게 짧게만 적었음.

랩업시간

스마트폰 앱을 하나 정해서 생각해보자. 메뉴 있을 것이고, 메뉴는 이름과 기능으로 저장되어 있을 것이다. dictionary로 구현 가능할 듯. 카톡 친구: 리스트에 담겨 있을 것 같음.

Q: 이진 검색 알고리즘을 통해 알고지름이 발전되는 원리는?

A: 알고리즘 활용은 인덱스를 하나 하나 세면서 검색하는 선형 검색인데, 이는 데이터가 많은 경우 반복 횟수가 너무 많아서 시간과 메모리를 많이 소비한다. 그래서 반복문과 연산자 등을 활용하면 이보다 더 좋은 검색 알고리즘이 될 수 있는데, 이진검색은 보다 효율적으로 검색하게 된다. 그래서 조건과 반복을 활용하면 알고리즘에 대한 관점이 달라질 수 있다.

Q: 재귀, 분할정복, 퀵정렬의 연관성은?

A: 재귀는 자기 자신을 호출해서 특정 조건을 만족하면 종료하게 되는 함수를 이용하는 방법. 분할정복은 특정 문제를 분할하고 정복한 경우에 재귀적으로 분할된 부분을 순차적으로 해결한다. 퀵정렬은 분할정복을 이용하여 정렬하는 방법.

521

추상자료형은 자료구조의 틀이다. 자료구조의 핵심을 요약해놓은 내용이라고 할 수 있다. 예를 들어 연결리스트라고 하면 각 연결리스트를 이루는 노드들이 연결된 구조이다. 조금 더 구체적으로는 노드와 노드가 연결될 때 이전 노드가 다음 노드의 위치/주소/포인터를 포함한다. 맨 처음을 head, 끝을 tail이라고 할 수 있다. 이 정의로부터 생각해볼 수 있는 점은 연결리스트 중간에서 다음 노드에 대한 주소를 삭제하면 그 이후 노드들은 전부 소실된다. 주소가 없기 때문에 사용 안 함. 추가적으로 stack, queue도 있는데 LIFO, FIFO으로 구분지을 수 있다. deque는 둘 다 합쳐놓은 기능으로 먼저 들어온 것이 먼저 처리되거나 제일 나중에 처리될 수 있다.

실생활에서 연결리스트, 스택, 큐를 생각해보기. 가방에 물건 넣으면 제일 나중에 넣은 물건부터 꺼내야 한다: stack. 글을 작성하면 1페이지부터 읽는다: queue. 연결리스트는 훨씬 더 추상적이긴 한데 나중에 좀 더 생각해보기. 스택과 큐를 연결리스트로 구성할 수 있을 것이다. 스택은 맨 나중에 들어온 것이 가장 먼저 처리되어야 하기 때문에 pop()이 시간복잡도가 상수, queue는 pop(0)이 시간복잡도가 1이 되게끔 작성하는 것이 좋을 것.