분류 전체보기

[python] 백준 - 4948. 베르트랑 공준

🤔문제 해결 S2 | 에라토스테네스의 체 에라토스테네스의 체를 사용하여 소수를 구하고 시작. 주어진 구간에 맞게 소수의 개수를 꺼냄 💻소스 코드 import sys def eratos(n): for j in range(n * 2, 123456 * 2 + 1, n): dp[j] = 0 dp = [1] * (123456 * 2 + 1) dp[0], dp[1] = 0, 0 for i in range(2, 123456 * 2 + 1): if dp[i] == 1: eratos(i) input = sys.stdin.readline while True: N = int(input()) if N == 0: # 입력 마지막 break print(sum((dp[N + 1:N * 2 + 1]))) 📕문제 확인 출처: BACK..

크루스칼 알고리즘(kruskal)

📔 크루스칼(kruskal) 이란 간선을 하나씩 선택해서 MST를 찾는 알고리즘 ( 프림은 정점을 선택, 크루스칼은 간선을 선택 ) 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다 사이클이 존재하면 패쓰 ( 사이클의 존재를 파악하는게 중요! ) V-1개의 간선이 선택될 때 까지 반복 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 disjoint-set 알고리즘을 이용한다. 📔 크루스칼(kruskal) 구현 def make_set(x): p[x] = x def find_set(x): if p[x] == x: return x else: p[x] = find_set(p[x]) return p[x] def union(x, y): px ..

[python] 백준 - 16234. 인구 이동(삼성 SW 역량 테스트 기출 문제)

🤔문제 해결 G5 | 시뮬레이션, BFS 1. 연합을 찾는다. 현재위치와 인접한 위치의 값의 차이가 조건에 맞으면 연합리스트에 넣어줬다. (BFS) 2. 만약 연합이 없으면 끝 3. 연합이 있으면 연합 내에서 인구 이동을 한다. 연합의 모든 인구의 평균값으로 바꿔준다. 4. (1,2,3)을 반복한다. while문으로 2번이 나올때까지 돌린다. 💨 시간초과가 나서 pypy로 돌렸더니 통과!!! 파이썬은 항상 느려서 이젠 그러려니 한다. 아니면 뭔가 더 좋은 방법이 있는 것 같다. 찾아보니 인접리스트를 활용해서 하는 방법도 있지만.... 나중에 도전해보겠다. 💻소스 코드 from _collections import deque def move_population(union_list): for union in ..

서로소 집합(Disjoint-set)

📔 서로소 집합(Disjoint-set) 이란 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들( 교집합이 없는 상태 ) 집합에 속한 하나의 특정 원소를 통해 각각의 집합들을 구분 ( 이를 대표자라고 함 ) 상호 배타 집합을 표현하는 방법 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표로 한다 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 트리 하나의 집합을 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 make_set(x) find_set(x) union(x,y) 📔 서로소 집합(Disjoint-set) 구현 def make_set(x): p[x] = x def find_set(x):..

[python] 백준 - 1931. 회의실 배정

🤔문제 해결 S2 | 정렬, 그리디 회의 시간이 긴 것과 상관 없이 회의가 끝나는 시각이 빠른것을 선택 회의가 끝나는 시각이 빠른 순으로 정렬 이전 회의가 끝난 시각과 비교하여 회의를 시작할 수 있으면 카운트 +1 없으면 통과 💨 끝나는 시각 뿐만 아니라 시작 시간도 두번 째로 정렬 해줘야 한다. 반례 [2,2], [1,2] 💨 sys.stdin.readline 과 input의 차이 (아래가 input()으로 받은 것) 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(key=lambda x: (x[1], x..

깊이 우선 탐색(Depth First Search, DFS)

📔 깊이 우선 탐색(DFS) 이란 깊이를 우선으로 하여 탐색을 수행하는 알고리즘 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법! ex) 미로탐색 - 막힐 때 까지 계속 가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가 다시 길을 찾는 것! 경로를 찾고 싶을 떄 스택와 그래프로 해결한다. ( 재귀함수를 써도 됨 ) 스택으로 사용시 이웃 중 가장 뒤에 있는 것부터, 재귀 사용시 이웃 중 가장 앞에 있는 것부터 탐색한다. 📔 깊이 우선 탐색(DFS) 구현 def dfs(c): print(c, end=' ') for neighbor in adj[c]: # c의 이웃 중 if visited[neighbor] == 0: # 방문 아직 안한 친구이면 visited[neig..