프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스의 후보키 문제입니다. 2레벨 문제예요. 만만히 봤다가 블로그에 알고리즘 문제 풀이 카테고리를 만들게 되었습니다. 하... 문제 설명 프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다. 그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다. 후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 ..
친구를 맺어주는 소셜 네트워크를 만든다고 하자. 친구 관계는 상호적이다. 이런 데이터를 가장 잘 조직하는 방법은 무엇일까? 한 가지, 매우 간단한 접근 방식은 2차원 배열로 친구 관계 리스트를 저장하는 것이다. 그러나 2차원 배열로는 A의 친구가 누구인지 빠르게 알 수 없다. 컴퓨터는 목록을 전부 확인해야 하므로 O(N)이 필요하다. 그래프를 사용하면 A의 친구를 O(1)만에 빠르게 찾을 수 있다. 1. 그래프 그래프는 관계에 특화된 자료구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 1.1 그래프 대 트리 그래프는 앞서 다뤘던 트리와 비슷하다. 사실 트리도 그래프의 한 종류다. 모든 트리는 그래프이지만, 모든 그래프가 트리는 아니다. 트리로 규정되는 그래프는 사이클이 없어야 하며, 모든 ..