1043 파이썬으로 union - find 를 통해 해결 거짓말을 할수 있는 사람과 아닌 사람으로 그룹을 2분화 할 수 있다. 2개의 집합은 서로소의 관계이다. 따라서 union - find 알고리즘을 통해 문제를 해결한다. Union & Find? node 에 대해 배열을 선언한 후에 (굳이 트리로 구현을 할 필요는 없다) parent ( 자기 위의 조상을 만들 리스트 ) 를 생성 후에 자신의 parent 노드를 담는다 초기 값으로는 자기 자신이다. Find 함수를 통해 자신의 최고 root를 찾고 같은 집합으로 만들 다른 노드를 union한다. 코드로 살펴보자 # Find def find(a): global parent if(parent[a] == a): return a else: find(paren..
다익스트라 사용할 때 그냥 큐에서 직접조회 방식으로 우선순위가 높은( 그리디 방법 으로 볼 수도 있다 ) 가격이 싼 노드를 찾아와서 문제를 해결했었는데 간단하게 우선순위 큐를 사용하면 문제를 더 쉽게 해결 할 수있다. 물론 시간적으로 우선순위 큐가 더 안좋다는 이슈를 얼핏 들은 것같기도 하지만 가지고 있는 라이브러리를 최대한 이용하는 게 중요하다고 생각한다. 우선 순위 큐란? 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 대표적으로 나누어서 보자 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 pop을..
연산 10억번 넘어가는 것 같으면 그건 잘못 되었다. 코드 연산시간 측정해보기 import time start_time = time().time() #측정 시작 # #프로그램 소스코드 # end_time = time.time() #측정 종료 print("time:", end_time - start_time) #수행 시간 출력 파이썬 자료형 보기 1. 문자열 문자열 변수를 초기화 할 때는 ", ' 를 사용 "를 쓸때는 '를 포함 가능 하고 "를 표현하고 싶으면 \를 앞에 두어 \"로 사용한다. 문자열 변수에 덧셈을 이용하면 Concatenate 가 된다. 양의 정수를 곱하는 경우 그 값만큼 여러 번 더해진다. 문자열에 대해서도 마찬가지로 인덱싱과 슬라이싱을 이용할 수 있다.( 단 특정 인덱스 값을 변경할 ..
- Total
- Today
- Yesterday