본문 바로가기

파이썬45

[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.
[Algorithm] 이코테 만들 수 없는 금액 | 파이썬 (그리디) [문제]동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. [입력 조건]첫 째줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1≤N≤1,000)둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다.. 2024. 6. 24.
[Algorithm] 프로그래머스 체육복 | 파이썬 (그리디) ※ 42862 체육복https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 해결 TIP우선, 제한 사항 중 여벌 체육복을 가져온 학생이 도난당한 경우를 고려한 경우를 정리해준다. 이후 나눠줄 수 있는 앞 뒤  번호와 도난당한 학생의 번호를 비교하여 한 명씩 제외한다. 마지막으로, 남아있는 도난당한 학생 수를 전체에서 빼준다. 앞 번호부터 순차적으로 나눠주는 것이 중요함으로 정렬을 이용한다. 전체 코드def solution.. 2024. 6. 24.
[Algorithm] 프로그래머스 무지의 먹방 라이브 | 파이썬 (2019 KAKAO BLIND RECRUITMENT) ※ 42891 무지의 먹방 라이브https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 해결 TIP재귀함수와 if, for 문으로 구현하려 했지만 생각보다 까다로운 조건들이 많았다. 우선순위 큐를 활용하여 쉽게 구현할 수 있다. 시간이 적게 걸리는 음식부터 전체 시간 k에서 빼가며 순차적으로 계산해야 한다. 소요 시간과 음식 번호를 같이 저장하고 우선순위를 위해 heapq 모듈을 사용한다. 전체 코드import heapq.. 2024. 6. 24.

티스토리툴바