TIL_20230518

오늘 할 일

• LeetCode 데일리 문제 풀기
• 공모전 회의 - 오후 7시 30분 → 오후 9시 30분

오늘 배운 것

LeetCode 데일리 문제 풀기

• 오늘의 문제: 1557. Minimum Number of Vertices to Reach All(https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/)
• 난이도: medium
• 문제 조건
  
  • 0부터 n-1까지의 n개의 정점이 있는 방향성 비순환 그래프와 에지 [i] = [from i, to i]가 노드 from i에서 노드 to i까지의 방향성 에지를 나타내는 배열 에지가 주어진다.
  • 그래프의 모든 노드에 연결할 수 있는 가장 작은 정점 집합을 찾는다. 고유한 솔루션이 존재한다는 것이 보장된다.
  • 임의의 순서로 정점을 반환할 수 있다.
• 문제 해결 과정
  
  • 정점의 개수로 방향을 표시할 수 있는 2차원 배열을 선언한다.
  • edges를 순회하면서 graph에 방향을 표시한다.
  • 모르겠다!
  • 규칙이 있는 것 같은데, 또 x 100000 답봄
  • 진입차수(indegree)를 이용한 접근:
    • 주어진 그래프에서 각 노드의 진입차수를 계산한다. (진입차수란, 다른 노드에서 현재 노드로 들어오는 간선의 수를 의미한다.)
    • 진입차수가 0인 노드들은 다른 어떤 노드에서도 도달할 수 없는 "출발점" 노드들이다.
    • 따라서, 진입차수가 0인 노드들의 번호를 모두 찾아서 결과로 반환한다.
  • 진입차수가 0인 노드들을 출발점으로 선택하면 모든 노드에 도달할 수 있다. 이러한 출발점 노드들만으로도 모든 노드에 도달할 수 있기 때문에, 최소한의 노드 수로 모든 노드에 도달하는 것이 가능하다.
  • 즉, 진입차수가 0인 노드는 다른 노드로부터 진입하는 간선이 없으므로 해당 노드로부터 출발하여 다른 모든 노드에 도달할 수 있다.

공모전 회의

• 서울 공공데이터 공모전을 준비하면서 아이디어를 서로 교환했습니다. 그런데 준비를 하던 중, 공공데이터를 활용한 기획보다 Open API를 사용해야 하는 방식의 서비스에 대해 이야기를 하게 돼서 백엔드를 맡은 제가 할게 없다는 것을 알게 됐습니다.
• 그래서 친구와 협의 후 고용노동부 공공데이터 활용 공모전을 나가기로 방향을 바꿨습니다.
• 필요한 부분을 회의에서 다시 정하고, 아이디어 기획에 관련된 내용은 새로운 팀원들을 구하면 하기로 했습니다. 기존 포맷인 프론트엔드, 백엔드에 UX/UI 디자이너 + 기획자를 생각하고 있습니다. 공고를 만들어서 업로드할 예정입니다.

느낀점

• 처음에 문제를 잘못 이해해서 반환해야 하는 값이 [start, end]로 착각했습니다. 그래서 헤메다가 이내 다시 알게되고 나서는 다른 노드에서 들어오는 간선이 없는 노드의 값을 구해서 문제를 해결했습니다.
• 공모전 준비를 한 지 얼마 되진 않았지만 엎어지고 새로 하려니 살짝 허탈하기도 합니다. 하지만 이런 것들도 다 경험이니까 좋게 받아들이고 다른 공모전으로 빠른 선택과 집중을 했습니다!

내일 할 일

• LeetCode 데일리 문제 풀기
• 영화보기