코딩테스트 문제 (25) - 텀 프로젝트
문제 1. p = [3,1,3,7,3,4,6], N = 7 => 3 2. p = [1,2,3,4,5,6,7,8], N = 8 => 0 풀이 입력을 통해 그래프를 구성하고 사이클에 속하지 않은 정점들의 개수를 출력하는 문제입니다. DFS를 통해 노드를 재귀적으로 방문하면서 리스트를 채워주고 이미 방문한 정점에 도달했을 때, 그 시작점부터의 리스트를 반환하면 사이클에 속한 정점을 구할 수 있습니다. 이를 전체 노드 수에서 빼주면 답을 구할 수 있습니다. kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도: 중 DFS를 이용한 그래프 사이클 판별 참조 claude-u.tistory.com/435 www.acmicpc.net/problem/9466
코딩테스트 문제 (24) - 순열 사이클
문제 1. p = [3,2,7,8,1,4,5,6] => 3 2. p = [2,1,3,4,5,6,7,9,10,8] => 7 풀이 입력으로 들어온 순열로 그래프를 구성하고 그래프 내의 사이클의 개수를 출력하는 문제입니다. DFS를 통해 문제를 해결할 수 있습니다. 매 노드에 대해 DFS 함수를 호출하고 방문 노드를 기록합니다. 사이클이라면 DFS가 종료되고 방문하지 않은 다음 노드에 대해 DFS를 호출합니다. 호출한 DFS 횟수마다 카운트 하면 전체 사이클 개수를 얻을 수 있습니다. kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도: 중 DFS, 사이클 판별 참조 www.acmicpc.net/problem/10451
코딩테스트 문제 (19) - 무지의 먹방 라이브
카카오 2019 블라인드 코딩테스트 기출문제입니다. 문제 1. food_times = [3,1,2], k = 5 => 1 2. food_times = [8,6,4], k = 15 => 2 풀이 효율성 테스트까지 통과해야 합니다. 일반적인 for 문을 지속적으로 돌면서 시뮬레이션 할 경우 정확성 테스트는 통과할 수 있으나 효율성 테스트는 통과할 수 없을 겁니다. 1번 케이스를 한 번 생각해보죠. 5초가 되기 전까지 1->2->3->1->3의 순으로 음식을 먹어 남아있는 음식은 1이 될겁니다. 이렇게 생각을 해보면 어떨까요? 우선 먹는 시간이 적은 음식부터 오름차순으로 (시간, 음식 index) 형태로 나열해봅시다. 그렇다면 [(1,2), (2,3), (3,1)] 이 될겁니다. 음식의 개수가 3개이기 때문에..
코딩테스트 문제 (18) - 후보키
카카오 2019 블라인드 코딩테스트 문제입니다. 데이터베이스의 후보키의 수를 추출하는 문제입니다. 문제 1. relations = [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"], ["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] => 2 ([0], [1,2]) 풀이 먼저 유일성을 확인하기 위해 칼럼의 모든 부분 집합을 생성해야 합니다. 부분 집합을 만드는 것은 dfs로 구현할 수 있고 만든 부분 집합이 유일성을 만족하는 지 확인합니다. 그 후, 유일성을 만족하는 부분 집합에 대해 최소성 검증을 하..
