2025-08-26

오늘 배운 것

Algorithm

크루스칼(Kruskal)

개념

  • 간선 중심으로 가중치가 작은 간선부터 선택해 사이클이 없으면 포함하는 그리디 MST 알고리즘
  • 사이클 판정은 Union-Find로 처리

언제 유리한가

  • 간선 수가 많지 않은 희소 그래프 (E ≈ V)에서 간선 정렬만 잘 하면 효율적
  • 그래프가 여러 컴포넌트로 나뉘어도 동작
  • 간선 리스트가 이미 주어졌거나 정렬이 쉬운 경우

시간 복잡도

  • O(E log E) (간선 정렬 지배) + Union-Find 거의 상수 → 전체 O(E log E).
  • V ≤ E ≤ V²에서 보통 O(E log V) 와 동일하게 봐도 무방.

코드

import java.io.*;
import java.util.*;

public class KruskalMST {
    static class Edge implements Comparable<Edge> {
        int u, v; long w;
        Edge(int u, int v, long w) { this.u=u; this.v=v; this.w=w; }
        public int compareTo(Edge o){ return Long.compare(this.w, o.w); }
    }
    static class DSU {
        int[] p, r;
        DSU(int n){ p=new int[n+1]; r=new int[n+1];
            for(int i=1;i<=n;i++) p[i]=i;
        }
        int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
        boolean union(int a,int b){
            a=find(a); b=find(b);
            if(a==b) return false;
            if(r[a]<r[b]){ int t=a; a=b; b=t; }
            p[b]=a; if(r[a]==r[b]) r[a]++;
            return true;
        }
    }
    // 입력: 1-indexed 정점 V, 간선 리스트 edges
    static long kruskal(int V, List<Edge> edges){
        Collections.sort(edges);
        DSU dsu = new DSU(V);
        long cost=0; int pick=0;
        for(Edge e: edges){
            if(dsu.union(e.u,e.v)){
                cost += e.w;
                if(++pick == V-1) break;
            }
        }
        // 연결 안되면 pick < V-1 (필요시 처리)
        return cost;
    }
}

프림(Prim)

개념

  • 정점 중심으로 하나의 시작 정점에서 출발, 현재 트리에 가장 싸게 연결되는 간선을 매번 확장하는 그리디 MST
  • 구현은 보통 우선순위큐(최소힙) + 인접 리스트

언제 유리한가

  • 밀집 그래프에서 인접행렬
  • 희소 그래프에서는 인접 리스트
  • 시작점이 정해져 있을 때

시간 복잡도

  • 인접리스트 + PQ: O(E log V) (실전 기본형)
  • 인접행렬 + 배열: O(V²) (dense에서 실용적)

코드

import java.io.*;
import java.util.*;

public class PrimMST {
    static class Node implements Comparable<Node> {
        int v; long w;
        Node(int v, long w){ this.v=v; this.w=w; }
        public int compareTo(Node o){ return Long.compare(this.w, o.w); }
    }

    // 입력: 1-indexed, adj[u] = (v,w) 리스트
    static long prim(int V, List<Node>[] adj, int start){
        boolean[] vis = new boolean[V+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        long cost=0; int pick=0;

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            if(vis[cur.v]) continue;
            vis[cur.v]=true;
            cost += cur.w;
            if(++pick == V) break;
            for(Node nx : adj[cur.v]){
                if(!vis[nx.v]) pq.offer(new Node(nx.v, nx.w));
            }
        }
        // 연결 안되면 pick < V (필요시 처리)
        return cost;
    }

    // adj 초기화 예시:
    // List<Node>[] adj = new ArrayList[V+1];
    // for (int i=1;i<=V;i++) adj[i]=new ArrayList<>();
    // adj[u].add(new Node(v,w)); adj[v].add(new Node(u,w));
}

CSS

기본 문법

  • 선택자와 선언부로 구성 : h1 { color : blue; font-size : 12px;}
    • 선택자 : 정의한 스타일을 적용할 대상
    • 선언부 : 선택자에 적용할 스타일로 {} 안에 작성하며 여러 개일 경우 ;으로 구분
      • 속성 : 지정할 속성
      • 값 : 지정할 값
  • 주석 : /* */

스타일 적용방법

  • 인라인 스타일
    • 개별 태그들에 style = "property : value" 형태로 지정
    • 별도로 선택자를 사용하지는 않으며 재사용은 불가
    • 일반적으로 다른 스타일에 비해 강력한 우선 순위를 가짐
  • 내부 스타일
    • 일반적으로 <head>의 <style> 태그 안에 집중해서 작성
    • 해당 html 페이지 내에서는 선택자 기준으로 재사용 가능
    • 페이지에 특화된 내용을 작성할 때 사용
  • 외부 스타일
    • 외부의 별도의 스타일 시트 파일(.css)을 만들고 <link> 태그르 이용해서 연결
      • <link rel = "stylesheet" href = "./abc.css"/>
    • 모든 페이지에서 재사용 가능
    • @import
      • linke와 달리 <style>태그 안에 설정하며 다른 css 파일 내부에서도 사용 가능
      • <style>태그의 맨 상단에 위치해야 함
      • @import url("file path"); 또는 @import "file path"; 형태로 사용

명시도 X-Y-Z

  • 선택자를 이용해서 우선 순위를 정하기 위한 값
    • X : ID 선택자의 개수
    • Y : class 선택자, 속성 상태자, 가상 클래스 선택자의 개수
    • Z : 타입 선택자, 가상 요소 선택자의 개수

기본 선택자

  • * {} : 전체 선택자
    • 명시도 0-0-0
    • HTML 문서 내 모든 요소를 선택하며, 주로 user agent의 css를 reset하는 용도로 사용
  • p {} : 태그 선택자
    • 명시도 0-0-1
    • 지정된 태그명을 가진 요소를 선택
  • .header {} : 클래스 선택자
    • 명시도 0-1-0
    • 특정 클래스 속성 값을 가진 요소를 선택. 하나의 태그에 여러 클래스 선언 가능
  • #logo {} : ID 선택자
    • 명시도 1-0-0
    • 특정 id 속성 값을 가진 요소를 선택

복합 선택자

  • section > p {} : 자식 선택자
    • 명시도 각 선택자의 합(예시 -> 0-0-2)
    • 부모 요소의 직계 자식 요소를 선택
  • section p {} : 자손 선택자
    • 명시도 각 선택자의 합(예시 -> 0-0-2)
    • 부모 요소의 하위 모든 요소(자손)를 선택
  • header + p {} : 인접 형제 선택자
    • 명시도 각 선택자의 합(예시 -> 0-0-2)
    • 지정된 요소의 바로 다음 형제 요소를 선택
  • header ~ p {} : 일반 형제 선택자 선택자
    • 명시도 각 선택자의 합(예시 -> 0-0-2)
    • 지정된 요소의 다음에 오는 모든 형제 요소 선택

속성 선택자

  • [data-type] {} : [attr] 선택자
    • 명시도 0-1-0
    • 특정 속성을 가진 요소를 선택
  • [type="text"] {} : [attr=val] 선택자
    • 명시도 0-1-0
    • 특정 속성 값이 정확히 일치하는 요소를 선택
  • [lan|="ko"] {} : [attr|=] 선택자
    • 명시도 0-1-0
    • 특정 속성 값이 정확히 일치하거나 해당 값 뒤에 하이픈(-)이 오는 경우
  • [href^="https"] {} : [attr^=val] 선택자
    • 명시도 0-1-0
    • 특정 속성 값으로 시작하는 요소를 선택
  • [href$=".pdf"] {} : [attr$=val] 선택자
    • 명시도 0-1-0
    • 특정 속상 값으로 끝나는 요소를 선택
  • [class~="button"] {} : [attr~=val] 선택자
    • 명시도 0-1-0
    • 특정 속성 값을 단어로 포함하는 요소를 선택 (해당 속성 값 앞뒤에 바로 글자가 오면 안되고 공백으로 구분되어야함)
  • [class*="dark"] {} : [attr*=val] 선택자
    • 명시도 0-1-0
    • 특정 속성 값을 포함하는 요소를 선택(이건 그냥 포함!)

가상 클래스 선택자

  • 실제로 class 형태로 존재하지는 않지만 상황에 따라 적용되는 class를 지정하기 위한 것
  • 클래스 이름 앞에 : 추가

  • 개발자가 태그에 가상 클래스를 지정할 필요는 없음

  • 구조적 가상 클래스
    • li:first-child {} : E:first-child 선택자
      • 명시도 0-1-0
      • E가 첫번째 자식으로 등장한 요소
    • li:last-child {} : E:last-child 선택자
      • 명시도 0-1-0
      • E가 마지막 자식으로 등장한 요소
    • tr:nth-child(2n) {} : E:nth-child(n) 선택자
      • 명시도 0-1-0
      • 앞에서 n 번째 자식 요소
      • 처음 요소는 1
      • n 은 0부터 시작하는 정수값이며 2n, 2n+1 등 연산식 사용 가능
      • 짝수 번째, 홀수 번째를 의미하는 evne, odd사용 가능
    • tr:nth-last-child(even) {} : E:nth-last-child(n) 선택자
      • 명시도 0-1-0
      • 뒤에서 n 번째 자식 요소

box model

  • 텍스트, 이미지 등의 모든 콘텐츠를 사각의 박스 형태로 관리하는 모델
  • 구성 요소
    • content
    • padding
    • border
    • margin

display 속성

  • block 계열
    • block 요소는 width와 height를 갖지만 inline 요소는 무시됨
    • inline-block은 width, height 가짐
  • box 계열
    • flex
    • grid
  • 기타
    • none : 요소를 표시하지 않음

box-sizing

  • width와 height를 측정할 때의 기준 설정
    • box-sizing : content-box;
      content만 해당 width, height
    • box-sizing : border-box;
      content + padding + border 합해서 해당 width, height

line-height

  • 줄 간격을 지정하는 속성으로 블록 요소내 컨텐트의 세로 중앙 정렬에 자주 사용됨

results matching ""

    No results matching ""