20230511목-적응?

 

목차

 

프밍기초

퀴즈. 3문제에 오픈북 형식으로 나왔다. 오픈북이라고 해봤자, 기존에 있던 자료들만 볼 수 있고 인터넷 검색은 허용되지 않았다. 문제가 3개밖에 없어서 그다지 어렵지는 않았고, 심지어 시간도 2시간이나 주어서 별 문제 없이 풀 수 있었다. 시간보다 먼저 푼 사람은 그냥 나가서 시간이나 떼우고 오라고 해서 알고리즘 잘하는 학우랑 같이 카페 가서 편하게 노가리 까다가 대충 시간 맞춰서 들어가니까 조교님이 해설해주시고 수업이 끝났다. 사실 해설할 만한 게 그다지 없어서 금방 끝내신 것도 있고.. 아무튼 거의 16시에 수업이 끝나 자유시간을 매우 많이 확보했다!

알림 스터디

그래프 이론, 자료구조.

비선형 구조 - 그래프, 트리.
데이터를 한줄로 나열하는 구조가 선형 구조, 그렇지 않은 것이 비선형 구조.
대표적으로 트리와 그래프가 있다. 트리도 그래프로 분류되지만, 트리는 트리만의 특성이 있기에 보통 구분하는 편이다.

컴퓨터과학에서의 그래프는 정점과 간선으로 이루어져있다. node(vertex), edge. 

데이터 간의 관계가 중요시되는 케이스일 때 그래프를 도입할 수 있다?
최단거리, 친구 관계, 미로 찾기. 

간선에 방향이 부여된 케이스, 간선에 가중치가 부여된 케이스. 자기 자신을 향하는 노드 등 다양한 조건이 걸릴 수 있다.
어떤 식으로든 자기 자신으로 돌아오는 간선의 경로가 존재할 때 사이클이라고 부른다. 
무방향 그래프 기준으로 사이클이 없는 그래프들을 트리라고 부른다.  아무것도 연결되지 않은 노드가 있는 경우에도 트리라고 부를까? 이분될 수 있는 그래프라면? -- 이정의는 조금 부족하다. 아래 참고
트리의 정의?트리의 특징. 정점이 n개일 때 n-1개의 간선이 나온다. 서로 다른 정점으로 가는 경로가 유일하다. 
일반 트리를 이진트리로 변환하는 방법?? - 중간에 가짜 노드를 끼우는 방식으로 가능. 다이아5급의 문제라고함.
다른 정점으로 가는 경로가 반드시 존재하고, 경로가 유일한 그래프라면 트리라고 말해봄직할 듯.
회로가 없는 연결 그래프. - 여기에서 연결이라는 말은 모두가 연결되어 있다는 것을 뜻하는 듯. 회로는 사이클.

포레스트- 트리의 집합. 트리들을 연결요소로 보고 각각을 합칠 때 이를 포레스트라고 부른다.

그래프의 모든 요소들이 전부 연결되어 있으리라는 법은 없다. 서로 연결되어 있는 정점을 그룹화하여 연결 요소라고 부른다. 

그래프를 코드로 표현하는 방법.
인접 행렬, 인접 리스트를 통해 표현할 수 있다.
c기준으로는 인접행렬을 구현하는 것이편하다. 그러나 인접리스트를 쓰는 것이 대체로 더 빠르고 효율적이다. 

인접행렬은 정점의 개수 * 정점의 개수 모양의 행렬을 만들고 이어진 간선에 해당하는 인덱스에 값을 매긴다. 
인접리스트는 정점의 개수만큼 연결리스트를 만들고, 해당 리스트에 연결되어 있는 정점들을 저장한다. 

bfs 너비 우선 탐색. 그래프를 탐색하는 알고리즘
큐를 사용함. 한 정점에서 시작해서 가까운 정점을 순서대로 방문. 한 정점 탐색이 끝날 시 큐에서 앞 원소를 꺼내와 해당 정점 탐색을 시작한다. 양방향 그래프의 경우, 반드시 탐색하는 정점에 대해 방문 표시를 해주어야 한다. 그렇지 않을 시 무한루프를 돈다.
시작 정점을 기준으로 깊이를 늘리는데 시간이 걸린다. 고작 3개의 노드를 사이에 두는 두 정점을 잇는데 시간이 엄청 걸릴 수도 있다. 
언제 쓸 것인가? 최단 경로를 구할 때. - 모든 간선의 가중치가 같을 경우의 최단 경로이다. 가중치가 있다고 해도 결국 사용되기는 하는 듯? 다익스트라도 결국 bfs..이지는 않다. 우선순위 큐로 구현할 경우에는 가중치를 기준으로 우선적으로 방문하니까.

bfs의 응용. 연결 요소의 개수. 

dfs. 스택의 원리. 최대한 깊숙히 들어가는 것을 우선하여 진행하는 탐색방법.

회고 및 다짐

본격적으로 알림 스터디 내에서 소규모 그룹을 구성해서 스터디를 진행할 것으로 보인다. 세미나가 끝나고 나서 잠시 인원들을 모이게 해서 어떻게 진행할지 이야기를 하던데, 일단 다음주에 한번 회식자리를 가지는 것으로 이야기가 됐다. 아무래도 그날은 밥을 걸러야 할 듯! 나 혼자 심히 고학번이라 조금 눈치가 보였다..ㅋㅋ

두부 썰고, 청경채 데치고, 양배추 삶고 전부 다 하는데 10여 분. 확실히 익숙해지니 속도가 붙는다. 곧 10kg 감량 들어설 것 같은데, 15kg까지만 빼면 조금 적당히 요리도 새로운 것들 도전해보면서 내 요리 풀을 조금 늘려보고 싶다. 근데.. 마구 도전하기에는 환기가 잘 되는 편이 아니라 냄새 많이 나는 음식은 힘들 것 같고..해도 지나치게 다양하게 도전하기는 힘들겠지.

당장 토요일에 또 테스트를 받으니까 알고리즘 공부에 집중하고 있는 요즘이다. 발상과 구현, 두 마리 토끼 다 잡아보고 싶다.