전.py 검색 결과

338 개의 검색 결과가 있습니다.

전.py

[python] 그래프 이론

# 서로소 집합 - 공통 원소가 없는 두 집합 1) 합집합 : 하나의 집합으로 합침 2) 찾기 : 특정 원소가 속한 집합이 어떤 집합인지 찾음 # 서로소 집합 알고리즘 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: return find_parent(parent, parent[x]) return x # 두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b # 노드..

2022. 3. 10. 14:47

전.py

[python] 미래도시 (최단 경로)

- 1번부터 N번까지 회사 - 특정 회사 도로로 연결 - 방문 판매원 A는 1번 회사에 위치, X번 회사에 방문해 물건 판매 - 양방향 이동 가능 - 소개팅 상대는 K번 회사에 존재 - A는 X번 회사에 가서 물건을 판매하기 전에 소개팅 상대 만남 - 1번 회사에서 출발 -> K번 회사 방문 -> X번 회사 - 방문 판매원이 회사 사이를 이동하게 되는 최소 시간 계산 => 플로이드 워셜 알고리즘 이용 INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n, m = map(int, input().split()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in rang..

2022. 3. 7. 14:19

전.py

[python] 전보 (최단 경로)

- n개의 도시 - 다른 도시로 전보를 보내서 다른 도시로 해당 메시지 전송 - 도시 C 에서 출발하여 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나감 - 각 도시의 번호와 통로가 설치되어 있는 정보가 주어짐 - 도시 C 에서 보낸 메시지를 받게 되는 도시의 개수는 총 개수, 모두 메시지를 받는 데까지 걸리는 시간 구하기 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수, 시작 노드를 입력받기 n, m, start = map(int, input().split()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] fo..

2022. 3. 7. 14:15

전.py

[python] 최단 경로

- 가장 짧은 경로를 찾는 알고리즘 - 노드 : 각 지점 - 간선 : 지점 간 연결된 도로 # 다익스트라 최단 경로 알고리즘 - 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 - 음의 간선이 없을 때 동작 - 그리디 알고리즘 1) 출발 노드 설정 2) 최단 거리 테이블 초기화 (무한으로, 자기 자신에 대한 노드는 0) 3) 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5) 3, 4 반복 import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, inpu..

2022. 3. 7. 13:33

전.py

[python] 백준 2117 원형 댄스

https://www.acmicpc.net/problem/2117 2117번: 원형 댄스 N(1 ≤ n ≤ 32767)명의 사람들이 잔치에서 춤을 추게 되었다. 처음에는 1번부터 N번까지의 사람들이 차례대로, 둥글게 손을 잡고 서 있다. 그리고 춤이 끝날 때에는 이 순서가 반대(거꾸로, 뒤집힌) www.acmicpc.net #[0, 0, 1, 2, 4, 6, 9, 12, 16, 20...] n = int(input()) if n==1 or n==2: print(0) elif n==3: print(1) else: start = 2 d = 2 cnt = 0 for i in range(n-4): start += d cnt += 1 if cnt == 2: cnt = 0 d += 1 print(start)

2022. 3. 7. 12:49

전.py

[python] 백준 2078 무한이진트리

https://www.acmicpc.net/problem/2078 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net # 시간초과 a, b = map(int, input().split()) node = [a, b] l, r = 0, 0 while True: if node[0] node[1]: node = [node[0]-node[1], node[1]] l += 1 else: break print(l, r) # 찾아봄.. a, b = map(int, inpu..

2022. 3. 7. 11:56

전.py

[python] 백준 2121 넷이 놀기

https://www.acmicpc.net/problem/2121 2121번: 넷이 놀기 첫 줄에 점들의 개수 N(5 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에 만들고 싶은 직사각형의 가로 길이 A(1 ≤ A ≤ 1,000)와 세로 길이 B(1 ≤ B ≤ 1,000)가 주어진다. 다음 N줄에 걸쳐서 점들의 좌표가 정수 www.acmicpc.net import sys n = int(sys.stdin.readline()) a, b = map(int, sys.stdin.readline().split()) data = set() for _ in range(n): data.add(tuple(map(int, sys.stdin.readline().split()))) cnt = 0 for i in data: i..

2022. 3. 4. 15:23

전.py

[python] 프로그래머스 튜플

https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr def solution(s): s = s.replace('{', '.').replace('}', '.') s = s.split('.') data = [] for i in s: if i != '' and i != ',': data.append(list(map(int, i.split(',')))) data.sort..

2022. 3. 3. 16:08

전.py

[python] 프로그래머스 시저 암호

https://programmers.co.kr/learn/courses/30/lessons/12926 코딩테스트 연습 - 시저 암호 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀 programmers.co.kr def solution(s, n): alpha1 = 'abcdefghijklmnopqrstuvwxyz' alpha2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' answer = '' for i in s: if i.isalpha(): if i.islower(): answer += chr((ord(i) - ord("a") + ..

2022. 3. 3. 15:43

전.py

[python] 백준 9095 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net t = int(input()) for _ in range(t): n = int(input()) dp = [0] * (n+3) dp[1] = 1 dp[2] = 2 dp[3] = 4 if n > 3: for i in range(4, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] print(dp[n])

2022. 2. 27. 21:08

전.py

[python] 백준 2579 계단 오르기

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net n = int(input()) data = [0] for _ in range(n): data.append(int(input())) if n == 1: print(data[1]) else: dp = [0] * (n+1) dp[1] = data[1] dp[2] = data[1] + data[2] for i in range(3, n+1): # 직전, 전전에서 오는 경우 중 최댓값 dp[i] = max(data[i]..

2022. 2. 27. 20:34

전.py

[python] 백준 1463 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net n = int(input()) d = [0]*(n+1) for i in range(2, n+1): d[i] = d[i-1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i//2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) print(d[n])

2022. 2. 27. 20:10

전.py

[python] 병사 배치하기 (다이나믹 프로그래밍)

- N명의 병사 무작위로 나열 - 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치 - 특정 병사 열외, 남아있는 병사 최대가 되도록 - 열외시켜야 하는 병사의 수 n = int(input()) array = list(map(int, input().split())) # 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환 array.reverse() # DP 테이블 초기화 dp = [1] * n # 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행 for i in range(1, n): for j in range(0, i): if array[j] < array[i]: dp[i] = max(dp[i], dp[j] + 1) # 열외해야 하는 병사의 최소 수를 출력 print(n - max(dp))

2022. 2. 25. 16:30

전.py

[python] 금광 (다이나믹 프로그래밍)

- n x m 금광 - 첫 번째 열부터 금 캐기 시작 - m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 중 하나의 위치로 이동 - 채굴자가 얻을 수 있는 금의 최대 크기 출력 => 3가지 위치만 고려 1) 왼쪽 위에서 오는 경우 2) 왼쪽 아래에서 오는 경우 3) 왼쪽에서 오는 경우 # 테스트 케이스(Test Case) 입력 for tc in range(int(input())): # 금광 정보 입력 n, m = map(int, input().split()) array = list(map(int, input().split())) # 2차원 DP 테이블 초기화 dp = [] index = 0 for i in range(n): dp.append(array[index:index + m]) index ..

2022. 2. 25. 16:22

전.py

[python] 효율적인 화폐 구성

- N가지 종류의 화폐 - 개수 최소한으로 이용해서 합이 M원 - 최소 화폐 개수 출력 n, m = map(int, input().split()) # 화폐 개수, 가치의 합 # N개의 화폐 단위 정보 array = [] for i in range(n): array.append(int(input())) # DP 테이블 초기화 d = [10001] * (m + 1) # 다이나믹 프로그래밍 (보텀업) d[0] = 0 for i in range(n): for j in range(array[i], m + 1): if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우 d[j] = min(d[j], d[j - array[i]] + 1) # =결과 출력 if d[m] ==..

2022. 2. 25. 16:14