프로그래머스[Python] - 거리두기 확인하기, 후보키

거리두기 확인하기[2021 카카오 채용연계형 인턴쉽]

문제 url : https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 거리두기 확인하기

문제 내용 : 시험을 봐야하는데, 사회적 거리두기에 따라 사람들이 떨어져 앉아야 한다.

조건 1) 맨해튼 거리가 2 이하인 곳에는 앚을 수 없다.

조건 2) 파티션이 존재하기 때문에 막혀있다면 상관이 없다.

사람들이 앉아있다고 가정했을때, 사회적 거리두기를 잘 유지했는지 판단하자!

알고리즘 : 약 BFS, 분할 정복

풀이과정 : 맨해튼 거리라고 하면 총 12가지 경우에 대해서 따져주면 되는 줄 알고 간단하겠다 싶었지만, 아니나 다를까 칸막이가 있었다. 그래서 어떻하면 좋을까 했는데, 맨해튼 거리를 잘 생각해보면

내가 있는 자리에서 동서남북 따져주고, 문제없으면 동서남북 이동한 지역에서 다시 동서남북 따져주면 맨해튼 거리에 있는 지역을 다 볼 수 있다. 동서남북같은 경우 ⇒ pos_x, pos_y 두 거리를 통해 구하면 될 것이다.

이때, 함정이 칸막이이다. 이는 분할 정복으로 풀면 된다고 생각했다. 우선 현재 P라면 사람이 있으니, 주변을 확인해서 책상인 곳이라면 queue에 담을 것이다. 만일 사람이 있다면 그냥 return False로 보내서 사람이 발견이 되었으니 거리를 지키지 않았다고 판단하면 된다. 그렇게 queue에 담긴 것들(빈책상)에서 동서남북을 확인해서 사람이 있는 경우만 False로 보내고 아닌 경우는 그냥 냅둔다.(문제 없으니 True로 반환)

visited 를 사용한 이유는 이전에 방문한 곳은 볼 필요가 없기 때문에 만들어놨다.(사실 그냥 x,y 아니면 된다고 예외처리하면 되는데..)

후보키[2019 KAKAO BLIND RECRUITMENT]

문제 url : https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

문제 내용 : 데이터베이스에서 후보키의 후보 갯수를 찾아야한다. 이때, 유일성과 최소성을 만족시키는 것을 따져야 한다.

• 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

알고리즘 : 구현

알게된 내용 : combinations를 사용해서 모든 경우의 조합에 대해서 하나씩 처리하면 되겠다고 생각해서 키의 조합을 구했다. 그다음 각 열에 대해서 해당 키에 속하는 것들을 열마다 비교해서 겹치지 않는다면(열의 길이와 동일하다면) 유일성까지 만족하게 구현했다.

최소성을 만족하는 것을 어떻게 처리해야할지 생각을 해봤는데, 이부분만 30분을 봤는데 잘 몰라서 찾아보았다.

하나라도 제외하는 경우 유일성이 깨진다... 이부분이 명확히 이해되지 않았다.

찾아보니 intersection을 이용해서 집합의 교집합을 구해서 처리했다. 알게된 접근법은 이 unique 리스트에서 요소끼리 비교한다는 것이었다. 왜냐? 생각을해보자.

(0)번째 인덱스와 (0,1) 이 두개의 키를 비교했을때, 둘다 유일성을 만족한다고 했을때, (0,1)에서 0을 지운다면 유일성이 깨져버리게 될 것이다. 왜냐면 0자체로 유일성을 만족하고 있기 때문이다.

(최소성에 대해서 더 깊게 공부해봐야 될 것 같다.)

또 알게된 점은 discard함수이용해서 set에서 처리한다는 것이다. 이는, 지우려는 element가 없어도 에러없이 종료된다.