Algorithm 38

[python]백준 11724번: 연결 요소의 개수(그래프)

# 11724 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ⭐ 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**7) N, M = map(int, input().split()) graph = [[] for i in range(N+1)] visited = [0] * (N+1) for _ in r..

Algorithm 2023.01.22

[python] 프로그래머스 안전지대(방향탐색)

# 120866 안전지대 https://school.programmers.co.kr/learn/courses/30/lessons/120866 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⭐ 코드 def solution(board): N = len(board) dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, 1, -1, 1, -1, 1] # 지뢰 설치 boom = [] for i in range(len(board)): for j in range(len(board)): if board[i][j] == 1: boom.a..

Algorithm 2023.01.19

[python]백준 1654번: 랜선 자르기(이진탐색)

# 1654 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 코드 K, N = map(int, input().split()) already = [int(input()) for _ in range(K)] start, end = 1, max(already) while start = N: start = mid + 1 else: end = mid - 1 print(end) 📝 풀이 주어진 랜선을 잘라서 필요한 ..

Algorithm 2023.01.18

[python]백준 8979번: 올림픽(implementation)

# 8979 올림픽 https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 코드 n, k = map(int, input().split()) grade = [] for _ in range(n): list_ = list(map(int, input().split())) grade.append(list_) grade = sorted(grade, key = lambda x : (-x[1], -x[2], -x[3])) for i in ran..

Algorithm 2023.01.10

[python]백준 9461번: 파도반 수열(DP)

# 9461 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 코드 T = int(input()) for _ in range(T): n = int(input()) dp = [0] * 101 dp[1] = 1 dp[2] = 1 dp[3] = 1 dp[4] = 2 dp[5] = 2 dp[6] = 3 for i in range(5, n+1): dp[i] = dp[i-1] + dp[i-5] print(dp[n]) 📝 풀이 그림과 같이 정삼각형의 ..

Algorithm 2023.01.08

[python]백준 2589번: 보물섬(BFS)

# 2589 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 코드 import sys input = sys.stdin.readline from collections import deque r, c = map(int, input().strip().split()) graph = [] for _ in range(c): graph.append(list(input())) # 상하좌우 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0]..

Algorithm 2023.01.07

[python]백준 1010번: 다리 놓기(Combination)

# 1010 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 코드 import math T = int(input()) for _ in range(T): n, m = map(int, input().split()) print(math.comb(m, n)) 📝 풀이 강을 기준으로 n이 서쪽이고 m이 동쪽이다. m에서 겹치지 않게 n만큼 뽑아주면 된다. 예제를 보면 2C2, 5C1, 29C13와 같은 값이 나온다. 그래서 딱 보자마자 조합 ..

Algorithm 2023.01.05

[python]백준 12851번: 숨바꼭질 2(BFS)

# 12851 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 코드 from collections import deque n, k = map(int, input().split()) visited = [0] * 100001 q = deque([(n, 0)]) fast, way = 10 ** 6, 0 while q: now, time = q.popleft() visited[now] = 1 if no..

Algorithm 2023.01.04

[python]백준 2579번: 계단 오르기(DP)

# 2579 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 코드 n = int(input()) list_ = [int(input()) for _ in range(n)] dp = [0] * n if len(list_)

Algorithm 2023.01.04

[python]백준 1463번: 1로 만들기(DP)

# 1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 n = int(input()) dp = [0] * (n+1) for i in range(2, n + 1): dp[i] = dp[i-1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] + 1) if i % 3 == 0: dp[i] = min(dp[i], dp[i//3] + 1) print(dp[n]) 📝 풀이 문제에서는 1로 만들기 위한 세 가지 가정을 제시했다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나..

Algorithm 2023.01.04
728x90