Python

[python] 백준 - 7562. 나이트의 이동

🤔문제 해결 S2 | BFS BFS로 다 돌아주다가 도착지를 만나면 끝! 💻소스 코드 from collections import deque def bfs(): q = deque() q.append((start_x, start_y)) while q: cx, cy = q.popleft() if cx == end_x and cy == end_y: print(chess[cx][cy]) return for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

다이나믹프로그래밍(Dynamic Programming)

📔 다이나믹프로그래밍(Dynamic Programming)이란 하나의 문제는 단 한 번만 푸는 방법! 다이나믹프로그래밍 (이하 DP) 작은 문제를 해결하여 큰 문제를 해결하는 분할정복과 유사하다고 생각할 수 있지만, 분할정복의 경우 한번 풀었던 문제를 다시 푸는 비효율적인 단점을 가지고 있다. (일부 경우 제외 (병합정렬)) 분할정복과 DP의 차이를 보여주는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열: 바로 앞과 앞앞 두 칸의 숫자의 합을 구해서 나타내는 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 분할정복을 이용한다면 이미 구한 숫자들을 다시 계산하는 단점이 있다. 위의 사진을 보면 13을 구하는게 2번, 12 3번, 11 3번 계산하는 것을 볼 수 있다. 이런 문제를 ..

[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):..