코딩 테스트 (29) 썸네일형 리스트형 [알고리즘 파이썬] 위상 정렬 그래프 알고리즘 중 하나인 위상 정렬은 BFS, DFS보다 효율적일 수 있다. 의미 : 순서가 정해져있는 작업를 수행할 때 사용하는 알고리즘 위상 정렬의 조건 주어진 그래프에서 위상 정렬을 하려면, 아래와 같은 조건을 만족하는 그래프여야 한다. 위상 정렬을 할 그래프는 간선이 방향을 가지는(유향) 그래프여야 한다. 내부에 순환(cycle)이 있으면 안된다. 큐(Queue)를 이용한 방식 주어진 그래프에서 위상 정렬을 하려면, 아래와 같은 조건을 만족하는 그래프여야 한다. 진입차수가 0인 정점을 큐에 삽입한다. (들어오는 연결선이 없는 노드) 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다. 2번, 3번 반복 [프로그래머스 Python] - 더 맵게(heap) programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr import heapq def solution(scoville, K): cnt = 0 heapq.heapify(scoville) while(1): min1 = heapq.heappop(scoville) if(min1=1): min2 = heapq.heappop(scoville) heapq.heappush(scoville,min1+min2*2) cnt+=1 else.. [파이썬 순열 조합 정리] 2. 구현(탐색) - from collections import Counter # 딕서녀리 - from itertools import permutations, combinations # 하나의 리스트에서 모든 케이스 구하기 - from itertools improt product # 두 개 이상의 리스트의 조합 구하기 3. DFS/BFS - from collections import deque [DFS] - 재귀함수 [BFS] queue = deque() (append, popleft, queue.reverse) - 최단거리(가중치 1) - 인접리스트 : graph = [[] for _ in range(3)] 5. 이진탐색 * 순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 .. [프로그래머스 Python] - 전화번호 목록 programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr def solution(phone_book): phone_book.sort() for a in range (0,len((phone_book)-1)): if phone_book[a] in phone_book[a+1]: return False return True [프로그래머스 Python] - 완주하지 못한 선수 onprogrammers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr from collections import Counter def solution(participant, completion): return list(Counter(participant) - Counter(completion))[0] 수식 표현 방법 (중위, 전위, 후위) 수식 표현 방법 중위표기법(Infix Notation) : 사람들이 일반적으로 사용하는 방식. 연산자가 피연산자 중간에 온다. (예 : 1+1, 5 * 3, 10/2) 전위표기법(Prefix Notation) : 연산자가 피연산자 앞에 오는 방식 (예 : +11, * 5 3, / 10 2) 후위표기법(Postfix Notation) : 연산자가 피연산자 뒤에 오는 방식 (예 : 1 1 +, 5 3 *, 10 2 /) * 중위표기법은 연산자 간 우선순위를 괄호를 통해 표현하기 때문에 연산에는 비효율적이다. -> 후위표기법을 이용하여 연산시간 단축한다. (스택이용) 스택을 이용한 후위표기법 변환 1. 입력 받은 데이터가 숫자(피연산자)라면 후위표기법변수에 저장 2. 입력 받은 데이터가 기호(연산자)라면 스택.. Array List vs Linked List ArrayList : 인덱스 기반이기 때문에 O(1)의 시간복잡도 LinkedList : 모든 요소를 순차적으로 탐색해야 하기 때문에 O(N)의 시간 복잡도 배열 ArrayList LinkedList 크기 크기고정 크기동적 크기동적 삽입,삭제 불가 가능 매우가능 효율 비효율 효율 매우효율 연속적 메모리 할당O 할당O(유한) 할당X(무한, 불연속적) 구현 용이 용이 어려움 탐색속도 빠름 느림 상황마다 다름 [파이썬 문법] Union find (Disjoint-set = 서로소 집합) [그래프 알고리즘]의 일종으로 상호 배타적 집합 이라고도 불리운다. 서로 중복되지 않는 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 찾는 알고리즘입니다. Find인덱스만 참조하므로 시간복잡도는 O(1) 노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union특정 집합의 원소들에 대해 상태를 바꿔줘야 하므로 시간복잡도는 O(n) 더 작은 값으로 묶는다. 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 parent = {} for i in range(1,11): parent[i] = i 우선, 모두 연결되지 않고 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신이 가리키도록 만든다. def find(x):.. 이전 1 2 3 4 다음
