프로그래머스
[프로그래머스] 2018 카카오 블라인드 [1차] 뉴스 클러스터링
문제 https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 풀이 알고리즘은 따로 고민할 것이 없었고 문제에 주어진 그대록 구현하는 문제였다. 간단히 하자면 다음과 같다. 두 자씩 잘라 리스트에 넣는다. 영문자 아닌건 버린다. 두 리스트의 교집합을 합집합으로 나눈다. def solution(str1, str2): sp_str1 = [] sp_str2 = [] for i in range(1, le..
[프로그래머스] 탐욕법 5. 섬 연결하기
문제 https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 최소신장트리 문제인 것 같아 검색해 보았다. MST 문제에는 크게 두 가지 방법의 해결책이 있는 듯 했다. 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복 Prim의 알고리즘의 시간 복잡도는 O(n^2) Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고 그래프에 간선이 많이..