본문 바로가기

Python69

[Algorithm] 백준 1463, 이코테 1로 만들기 | 파이썬 (DP, Dynamic Programming) ※ 1463 1로 만들기https://www.acmicpc.net/problem/1463[문제]정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. ⓐ X가 5로 나누어 떨어지면 5로 나눈다.ⓑ X가 3으로 나누어 떨어지면 3으로 나눈다.ⓒ X가 2로 나누어 떨어지면 2로 나눈다.ⓓ X에서 1을 뺀다. 정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 1. 26 - 1 = 25 ( ⓓ)2. 25 / 5 = 5 ( ⓐ)3. 5 / 5 = 1 ( ⓐ) [입력 조건]첫째 줄에 정수 X가 주어진다.(1 [출력 조건]첫째 줄에 연산을 하는 횟수의 .. 2024. 7. 3.
[Algorithm] 백준 16234 인구 이동 | 파이썬 BFS ※ 16234 인구 이동https://www.acmicpc.net/problem/16234문제 해결 TIP모든 나라의 위치에서 BFS를 수행하여 인접한 나라의 인구수를 확인한 뒤에, 가능하다면 국경선을 열고 인구 이동 처리를 진행한다. visited 배열을 따로 두어 index를 확인하면서 더 이상 인구 이동을 할 수 없을 때까지 반복한다. BFS를 처리할 때 인구 분배를 같이 해나가는게 중요한 것 같다.   전체 코드 from collections import dequeN, L, R = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))#graph = [[50, 30], [2.. 2024. 7. 3.
[Algorithm] 백준 18405 경쟁적 전염 | 파이썬 BFS ※ 18405 경쟁적 전염https://www.acmicpc.net/problem/18405첫번째 문제 풀이 (시간 초과)문제를 보고 먼저 생각해낸 해결방법은1. 바이러스 번호 1번부터 graph에서 위치한 자리값을 position 배열에 저장한다.2. position 배열에서 하나씩 꺼내어 확산을 진행한다.N, K = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))S, X, Y = map(int,input().split())#graph = [[1, 0, 2], [0, 0, 0], [3, 0, 0]]dx = [-1,1,0,0]dy = [0,0,-1,1]def bfs(x,y,.. 2024. 7. 2.
[Algorithm] 백준 11724 연결 요소의 개수 | 파이썬 DFS ※ 11724 연결 요소의 개수https://www.acmicpc.net/problem/11724문제 해결 TIP간선 정보를 이용하여 몇개의 그룹이 만들어지는지 출력하는 문제이다. 기본 DFS 알고리즘을 이용하여 풀 수 있고, 주의해야 할 점은 RecursionError가 발생하는 것이다. 1000번 이상의 recursion이 발생하면 recursion error 가 뜨기 때문에 recursionlimit을 변경해주었다. 전체 코드import syssys.setrecursionlimit(10**7)input = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for i in range(M): u, v .. 2024. 6. 30.
[Algorithm] 백준 10026 적록색약 | 파이썬 BFS ※ 10026 적록색약https://www.acmicpc.net/problem/10026문제 해결 TIP유기농 배추 문제와 같이 처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 적록색약인 것과 아닌 것의 그래프를 애초에 따로 저장하여 bfs로 돌려주었다. 전체 코드from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]N = int(input())graph = [] #적록색약이 아닌 그래프for i in range(N): graph.append(list(map(str,input())))new_graph = [row[:] for row in graph] #적록색약이 보는 그래프# 새로운 그래프에서 'G' 값을.. 2024. 6. 29.
[Algorithm] 백준 7576 토마토 | 파이썬 BFS ※ 7576 토마토https://www.acmicpc.net/problem/7576문제 해결 TIP이코테의 미로 탈출과 비슷한 문제라고 생각했다. BFS를 이용하여 토마토를 전염시킨 후 최단 거리를 반환하는 것과 같이 전염하면서 이전 값에 1을 추가하여 값을 저장하도록 한다. 이때 주의할 점은 2차원 배열의 첫번째 원소부터 탐색 시작하는 것이 아닌, 1을 가진 토마토라면 동시에 전염이 시작되어야 한다는 것이다. 최종적으로 바뀐 2차원 배열 graph에 익지 않은 토마토가 있다면 -1을 반환하고 그렇지 않으면 최소 일수(graph에서 가장 큰 원소값-1)를 반환한다. 이때 이미 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하게 되어있는데, 어차피 graph에서 가장 큰 원소값이 1일테니 0을 반환할 .. 2024. 6. 27.
[Algorithm] 백준 1012 유기농 배추 | 파이썬 BFS ※ 1012 유기농 배추https://www.acmicpc.net/problem/1012문제 해결 TIP처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 바이러스 문제와 비슷하게 상하좌우 주변 노드들을 방문하며 큐에 삽입하고 탐색하는 방법으로 진행한다. 여기서 주의할 점은 문제에서 가로 길이를 M, 세로 길이를 N으로 주어진 점이다. 전체 코드from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def bfs(x, y): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in rang.. 2024. 6. 26.
[Algorithm] 백준 2667 단지번호붙이기 | 파이썬 DFS ※ 2667 단지번호붙이기https://www.acmicpc.net/problem/2667문제 해결 TIP이코테의 음료수 얼려 먹기 문제의 응용 버전이라고 생각하면 된다. DFS를 이용하여 연결된 모든 노드들을 방문하고 count를 해준다. 집이 있는 곳이라면, 문제에 나와 있는 것처럼 단지번호를 붙여준다. (집의 유무인 1과 헷갈리지 않기 위해 단지번호는 2부터 붙여주었다.) 집을 모두 방문한 후 그래프의 최종 상태는 마지막 주석을 확인하기 바란다. 전체 코드N = int(input())graph = []for i in range(N): graph.append(list(map(int,input())))#graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1].. 2024. 6. 26.
[Algorithm] 백준 2606 바이러스 | 파이썬 BFS ※ 2606 바이러스https://www.acmicpc.net/problem/2606문제 해결 TIP너비우선 탐색 알고리즘인 BFS를 이용하여 쉽게 풀 수 있다. 1번 컴퓨터부터 큐에 삽입하여 주변 노드들을 방문 처리해준다. 전체 코드from collections import dequeN = int(input())M = int(input())graph = [[] for _ in range(N + 1)]# 그래프 변환 작업for _ in range(M): node1, node2 = map(int, input().split()) graph[node1].append(node2) graph[node2].append(node1)#graph = [[],[2, 5], [1, 3, 5], [2], [.. 2024. 6. 26.

티스토리툴바