JaeHyung

Just Do It

최대 1 분 소요

BFS

알고리즘 설명

  • 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
  • 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
  • 큐에서 원소를 pop하고 그 칸에 상하좌우로 인접한 칸 확인
  • 방문하지 않고 조건에 만족하면 push
  • 큐가 빌때까지 반복

    자주 실수하는 것들

  • 시작점에 방문했다는 표시를 남기지 않음
  • 큐에 넣을 때 방문했다는 표시하기!
  • 큐에서 빼낼 때 방문하면 시간초과가 날 수 있음
  • 범위 체크하기

    DFS

    알고리즘 설명

  • 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘
  • 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
  • 스택에서 원소를 꺼내고 조건에 맞고 방문하지 않았다면 해당하는 다음 칸을 스택에 삽입
  • 스택이 빌때까지 반복

참고

그래프

1 분 소요

그래프 정의 그래프: 정점과 간선으로 이루어진 자료구조 차수(degree): 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수 무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프 방향 그래프(Directed Graph): 간선의 방향이 있...

우선순위 큐

최대 1 분 소요

우선순위 큐 정의와 성질 우선순위 큐: pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐 원소의 추가(Heap): O(lgN) 우선순위가 가장 높은 원소의 확인(Heap): O(1) 우선순위가 가장 높은 원소 제거(Heap...

이진 검색 트리

1 분 소요

이진 검색 트리 정의와 성질 정점(Vertex/Node): 트리에서 각 원소 루트(Root): 트리에서 가장 꼭대기의 정점 리프(leaf): 제일 말단에 위치해 자식이 없는 정점 간선(Edge): 정점을 연결하는 선 이진 트리(Binary Tree): 각 노드의...

해시 구현

3 분 소요

해시 구현 구현 해시 테이블 크기, 해시 함수를 정해야 함 Load factor: 원소의 개수/테이블의 크기 Load factor를 작게 유지하면 충돌이 덜 생겨서 각 연산이 거의 O(1)에 동작하지만 cache hit rate가 줄어들고 메모리도 많이 차지하는 단점이...