06 (화)

Thinking

바디프로필에 대한 고찰

바디프로필은 정말 좋은 걸까? 바디프로필을 찍기위해 몇 달 전부터 다이어트도 하고, 살도 빼고, 스트레스도 받는다.
찍은 바디프로필은 '나 자신'이 맞을까? '평소의 나'와는 조금 괴리감이 있는 이상적인 모습의 나이다.
바디프로필 속 나와 현재의 나를 비교하며 자괴감에 빠지고 우울해 한다면, 바디프로필을 찍은 행위는 옳았다고 할 수 있을까?
청춘시절 아름다운 나를 찍어 간직할 순 있지만 그것을 제외하고 전부 단점인게 바디프로필이라고 생각한다.

맞춰간다는 것

연애는 상대를 바꾸는게 아니라 서로 맞춰가는 것. 사소한 갈등 속에서 상대와 나의 다름을 이해하고 맞춰간다.
서운함을 느끼는 상대를 보며, 서운함을 느껴도 바로 풀리면 좋겠다고 했다.
사람마다 기분이 풀리기 위한 시간의 양은 다른 것.
기분이 풀리는데 필요한 시간이 10인 사람한테 나는 1만큼의 시간만에 기분이 풀리니깐 너도 1만큼의 시간만에 풀리면 좋겠어!라고 하는 건 강요다.
그 다름을 알아가고 맞춰나가기 위해 노력한다.
상대한테 나의 마음을 표현하되 강요하지 않는다.
서운함을 느끼는 부분을 생각해 다시 그러지 않도록 노력하고, 풀어줄 수 있는 방법을 생각한다.

100일 선물

기념적 vs 실용적
선물은 언제나 실용적이여야 된다 생각한다. 미니멀리즘이니깐. 하지만 한 번밖에 없을 기념적인 날엔 무언가 특별한 게 있어도 좋지 않을까? 그럼 둘 다 준비해야지.
크록스+파츠들, 나무액자+편지를 생각 중이다. 근데 크록스가 실용적이기 위해선 상대에게 미리 물어봐야 하는데, 이거 물어봐말아?

Study

자료구조

Disjoint Sets

겹치는게 없는 원소들의 집합, 그 집합들의 모임. 트리 또는 배열로 구현한다.
Find()로 대표노드를 찾고, Union()으로 집합을 합친다.
naive하게 알고리즘을 구현하면 find하는데 시간이 오래걸릴수도 있고 Union과정에서 트리형태가 아닌 배열형태로 구성되어 시간적으로 비효율적일 수 있다.
find과정에서 모든 자식노드들이 대표노드를 가리키게, Union과정에서 집합의 수가 적은 집합이 집합의 수가 큰 집합의 대표노드를 가리키도록 구성해 이를 해결한다.

void weightedUnion(int i, int j) {
    //배열의 값이 갯수를 가리키게 하고, 이때 값은 음수이다.
    int temp = parent[i] + parent[j]; 
    if(parent[i] > parent[j]) {//j의 원소의 갯수가 더 많은 경우
      parent[i] = j;
      parent[j] = temp;
  }
  else {
    parent[j] = i;
    parent[i] = temp;
    } 
}

int collapsingFind(int i) {
    int root, trail, lead;
    //root 노드 설정
    for(root = i; parent[root] >= 0; root = parent[root])
    ;
    //경로에 있는 모든 노드들이 전부 대표노드를 가리키게 바꾼다.
    for(trail = i; trail != root; trail = lead) {
    lead = parent[trail];
    parent[trail] = root;
  }
  return root;
}

Graph

그래프의 구성

V : vertex, 유한개이다.
E : edge, 최대갯수는 $(v+1)v/2$ 이다. 모든 edge가 존재하면 이를 complete graph라고 한다. 주로 G=(V, E)로 그래프를 표현한다.

방향성

보통 indirected graph를 사용하고, 방향성이 있는 그래프를 사용하면 digraph라고 표기한다. indirect graph에서 (t,h)와 (h,t)인 edge는 같은 edge이다.

Definitions

Adjacent : 두 vertex가 edge로 연결되어 있다면 두 vertex는 adjacent하다고 한다.
incident : 두 vertex를 adjacent하게 이어주는 edge를 해당 vertex들에 incident한 edge라고 한다.
subgraph : G에서 파생된 G’를 subgraph라고 한다.
length: # of edges
simple path : 연결된 edge에서 처음과 끝 vertex를 제외하고 겹치는 vertex가 없는 경로
cycle : 처음과 끝의 vertex가 같은 경로
connected : 두 vertex를 연결하는 edge들의 집합이 존재하면 두 vertex는 connected
component connected(연결성분) : 노드들을 연결하는 다른 subgraph가 없다면 이들은 연결성분이다.
tree : graph가 connected acyclic(비순환) graph라면 tree. 즉 Tree는 graph의 한 종류이다.
degree : 해당 vertex에 이어져있는 edge의 갯수 그래프는 행렬혹은 리스트로 표현할 수 있다. 두 그래프 사이에 비용 혹은 거리 같은 변수가 있다면 해당 값을 edge의 가중치로 사용할 수 있다.

DFS

DFS vs BFS
깊이탐색 vs 너비탐색. 상황을 봐가며 필요한 자료구조를 사용한다.
DFS를 구현하기위해 2차원배열과 방문확인을 위한 visited배열이 필요하다.

void dfs(int v) {
  /* depth first search of a graph beginning at v */
  nodePointer w;
  visited[v] = 1;  // visited[] is a global variable
  printf("%5d", v);
  for(w = graph[v]; w; w = w->link)
    if(!visited[w->vertex])
      dfs(w->vertex);
}

이를 반복문으로 구현해보면

void dfs_iterative(int v) {

  nodePointer w;
  int u;
  push(&top, v);
  
  while(top) {
    u = pop(&top);
    if(!visited[u]) {
      printf("%5d", u);
      visited[u] = 1;

      for(w = graph[u]; w; w = w->link)
        if(!visited[w->vertex])
          push(&top, w->vertex);
    }
  }
}

BFS

void bfs(int v) {
  nodePointer w;
  visited[v] = 1;
  printf("%5d", v);
  addq(&front, &rear, v);
  while(front) {
    v = deleteq(&front);
    for(w = graph[v]; w; w=w->link)
      if(!visited[w->vertex]) {
        printf("%5d", w->vertex);
        addq(&front, &rear, w->vertex);
        visited[w->vertex] = 1;
      }
  }
}

Connected Components

DFS, BFS를 돌려 연결되어있는 노드들은 connected components이다. 즉, 방문체크를 하는 배열에 반복문을 돌려 방문되지 않은 노드라면 dfs혹은bfs를 실행한다.

Spanning Trees

그래프의 모든 vertex들을 순회하는 트리를 Spanning Tree라고 한다. Graph에서 DFS, BFS를 실행하면 spanning tree를 찾을 수 있다.

특징

edge를 두 집합으로 나눌 수 있다.

T : 검색과정에서 사용된 edge
N : 검색과정에서 사용되지 않은 edge 스패닝트리는 T로 이루어져 있고, N의 어느 edge든 추가하면 이는 Cycle이 생긴다. 일단은 이대로 하면 될 거같다.

Biconnected Components

articulation point : vertex와 vertex와 인접한 edge들을 삭제 시켰을 때 그래프가 disconnected된다면 해당 vertex는 articulation point이다. ariticulation point에서 분할한 그래프들의 집합을 BCC라고 한다. ariticulation point는 DFS과정에서 찾을 수 있다. DFS를 돌려 spanning tree를 만든다. 그리고 기존 그래프에는 있으면서 SpanningTree에 있지 않는 edge(back edge)를 점선으로 만든다.

Spanning tree의 root 노드가 두개이상의 자식을 가지고 있으면 이 노드는 AP이다.
nonroot노드들에 대하여 영토확장을 해가며, 겹치는 포인트는 AP가 된다.
Spanning tree의 leaf노드들은 AP가 될 수 없다.

Kruscal’s Algorithm

Minimum spanning tree(MST)를 구하기 위한 방법 중 하나이다.

간선들의 가중치를 오름차순으로 정렬한다.
작은 가중치를 가지고 있는 간선들을 먼저 택하며, cycle이 만들어지지 않도록 한다.
간선이 n-1개 선택되면 종료한다.

자구 과제

pseudo code

#include <stdio.h>
#include <stdlib.h>

int main(void){
  파일열기;
  if(파일의 인자가 1개가 아니라면){
    printf("usage: ./fp1 input_filename:\n");
    return 0;
  }
  else if(파일이 없다면){
    printf("The input file does not exist.\n");
    return 0;
  }
  //vertex_number : vertex의 갯수
  //edge_number : edge의 갯수
  int vertex_number, edge_number;
  fscanf(f,"%d%d",&vertex_number, &edge_number);
  for(){
    간선의 정보 입력받기{src,det,weight};//구조체 정의
    minheap(간선);//minheap 정의, 가중치를 기준으로 minheap구현
  }
  int sum_weight=0;//가중치의 합 연산
  struct aa[];//가중치가 낮은 순서대로 간선을 출력하기 위한 구조체 배열
  int i=0;
  while(선택된 간선의 갯수<vertex_number-1){//disjoint set의 배열 값이 set의 배열값이 되도록 설정
    struct a=delete_minheap();//가중치가 작은 간선부터 선택
    if(a==NULL) break;//disconnected라면 break;
    if(find(src)!=find(det)){//간선이 서로 다른 집합이면
      union(src,det);
      sum_weight+= a.weight;
      aa[i++]=a;
    }
  }
  for(aa에 있는 배열들 순서대로 파일에 출력);
  fprintf(f,"%d\n",sum_weight);
  if(while문이 disconnected로 종료되었다면) fprintf(f,"DISCONNECTED");
  else fprintf(f,"CONNECTED");
  파일닫기;
  return 0;
}

컴실 Maze 구현하기

미로 찾기를 dfs, bfs로 구현해야되는데 어떻게 해야되는지를 모르겠다.
2차월 배열로 저장해서 벽을 1로 처리..?
한줄씩 입력받으며 노드들을 이어주기..?

Thinking

바디프로필에 대한 고찰​

맞춰간다는 것​

100일 선물​

Study

자료구조​

Disjoint Sets​

Graph​

그래프의 구성​

방향성​

Definitions​

DFS​

BFS​

Connected Components​

Spanning Trees​

특징​

Biconnected Components​

Kruscal’s Algorithm​

자구 과제​

컴실 Maze 구현하기​