목록파이썬 (40)
DevKim
programmers.co.kr/learn/courses/30/lessons/17677# 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 다중 집합에 대해 확장할 수 있다는 조건으로, 단순히 파이썬의 내장 함수 set을 사용하여 교집합과 합집합을 구할 수 있는 문제가 아니었다. 또한 영문자외의 다른 문자뒤나, 앞에 오는 문자들은 함수에 들어가지 않는다는 점을 고려해야했다. 입력 : AA_bb_aa_AA,BBB 출력 : 13107 이 반례가 오류를 고치는..
programmers.co.kr/learn/courses/30/lessons/17686 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 문자열을 잘 다루느냐와 정렬을 할 수 있는지가 이문제의 관건이라고 생각한다. 1. 문제에서 대소문자를 고려하지 않기 때문에, 처음부터 모두 소문자로 바꿔주고 시작 2. 파이썬 정규표현식 re를 이용하여 HEAD 부분과 NUMBER 부분을 나누어주었다. 이때 TAIL 부분은 정렬에 고려하지 않아도되므로 정렬에 고려해야할 대상인 in..
programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 1. 파이썬의 정규표현식을 이용하여 -,+,* 부호만 뽑아낸 후 2. permutations 순열을 이용하여 해당 연산자로 나타낼 수 있는 조합을 따로 리스트에 담아줌 3. 연산을 쉽게 하기 위해서 숫자로만 이루어진 num 리스트와 부호로만 이루어진 cul 리스트를 정규표현식 re를 이용하여 따로 담아줌 4. 우선순위 부호부터 하나씩 순회..
programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr [ 알고리즘 ] 구현 [문제 접근] 1. combonations 를 이용해 조합을 구해주었고 2. Counter을 이용해 나온 횟수를 구해주었다. 처음엔 collections 에 있는 defaultdict을 이용해서 문자열들의 조합을 하나씩 세주고, 그 후 정렬을 한 후에 최대값과 같은 애들을 하나씩 구해줬는데 그렇게하니 실행 케이스에서 2개 정도 시간 초과가 나서 아예 처음부..
programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr [ 알고리즘 ] 그리디 [문제 접근] 1. 앞에서 부터 큰 수가 와야한다는 점 2. 삭제되는 값이 k개 이어야한다는 점 3. "9999"와 같이 같은 수로 이루어진 문자열이 존재하는 경우를 고려 4. k개가 아직 다 삭제되지 않았는데 문자열을 모두 순회했을 경우를 고려 이렇게 4가지를 염두해두고 풀이한 문제이다 que를 이용하여 문자열을 하나씩 담아주고, 해당 문자열이 이미 que에 들어가있는 숫자보다 크다면, 즉 이미 que에 담긴 숫자가 해당 숫자보다 작다면 pop으로 삭제를 해준다. 이때 k < 0 이면 더 이상 pop을 진행하면 안되기 때문에 k..
[ 알고리즘 ] 완전탐색,구현 [문제 접근] 주어진 numbers로 만들 수 있는 순열을 구해서 ( [1,2], [2,1] 은 다른 것임 ) 소수를 구할 땐 효율성을 위해 에라토스테네스의 체를 이용하여 구현하였다 [코드] from itertools import permutations def solution(numbers): answer = 0 n=len(numbers) #문자열 num=list(numbers) #리스트 result=[] #해당 숫자 조합으로 만들 수 있는 모든 숫자 조합 List=[] for i in range(1,n+1): List.append(set(permutations(num,i))) #체를 이용하여 해당수로 만들 수 있는 최댓값까지의 소수들 찾기 num.sort(reverse=T..
[1] Union-find [ 개념 ] - 서로소 집합을 찾는 것 = 공통 원소가 없는 두 집합을 의미함 - Union = 합집합 - Find = 찾기 [ 과정 ] 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다 A와 B의 루트 노드 A',B'를 각각 찾는다 A'을 B'의 부모 노드로 설정한다 반복 [ 최적화 ] - find 함수를 최적화하기 위해, 경로 압축을 이용한다 - find 함수를 재귀적으로 호출한 뒤에, 부모 테이블 값을 바로 갱신 [ 응용 ] - "무방향" 그래프 내에서의 사이클 판별시 - 두 노드의 루트 노드가 서로 같다면 cycle(사이클)이 발생한 것임 [ 코드 ] def find_parent(parent,x): if parent[x]!=x: parent[x..
- '하나'의 정점에서 다른 모든 정점으로 가는 최단 경로 [ 조건 ] - 음의 간선이 존재하지 않음 [ 기존의 선형탐색 방법의 다익스트라 ] - O(n^2) 의 시간 복잡도를 가짐 - 문제점은 노드의 개수가 10,000개가 넘어가는 문제라면 시간초과 가능성이 높음 [ 우선순위 큐를 이용한 다익스트라 ] - 힙을 이용하여 구현 - python 에선 heapq 라이브러리로 구현되어있음 - O(NongN) 의 시간복잡도 [ 과정 ] 최단거리 테이블을 초기화(자기 자신은 0, 직접 연결되어있지 않는건 무한대로 초기화) 처음엔 가장 가중치가 작은 값을 선택함 하나의 노드를 선택하고 해당 노드를 거쳐서 가는 경우를 모두 고려하여 가장 최소인 값으로 업데이트 (이때, 값이 새로 갱신된 경..