본문 바로가기

분류 전체보기96

7576번 - 토마토(Python 풀이최소 일수를 구해야 하므로, bfs를 이용하여 문제를 해결한다. 모든 익은 토마토의 좌표를 큐에 넣은 후, bfs를 실행하며 연결되어 있는 모든 토마토가 익을 때까지의 일수를 센다.bfs가 끝난 후, 아직 안 익은 토마토가 있다면 모두 익는 것이 불가능 한 것이므로 -1을 출력한다.모두 익었다면 계산한 ans를 출력한다.(ans는 -1부터 시작해야 오늘로부터 지나는 일수가 된다.)코드from collections import dequeimport sysinput = sys.stdin.readlineM, N = map(int, input().split())tomatoes = [list(map(int, input().split())) for _ in range(N)]dx = [-1, 1, 0, 0]dy .. 2025. 2. 17.
1931번 - 회의실 배정(Python) 풀이그리디 알고리즘을 이용해 문제를 해결한다. 회의 정보를 끝나는 시간을 기준으로 오름차순 정렬한다.가장 빨리 끝나는 회의부터 시작해서, 이후의 회의 중 이전 회의가 끝난 후 진행할 수 있는 회의를 다음 회의로 결정한다.끝나는 시간이 같다면, 먼저 시작하는 회의부터 진행한다.(3 3 회의와 2 3 회의가 있다면, 2 3 회의부터 진행해야 3 3 회의까지 진행할 수 있도록 된다.)코드N = int(input())meetings = [list(map(int, input().split())) for _ in range(N)]meetings.sort(key=lambda x: (x[1], x[0]))ans = 0end = -1for i in range(N): if meetings[i][0] >= end: .. 2025. 2. 17.
2468번 - 안전 영역(Python) 풀이높이를 1부터 99까지 탐색해가며 안전 영역의 개수를 센다.(높이가 100인 경우, 모든 영역이 잠기므로 제외한다.) dfs(bfs도 가능)를 이용해 특정 높이에서의 안전 영역을 구한다.이때, 해당 영역의 높이가 특정 높이보다 높은 경우만 안전 영역으로 생각한다. 각 높이에서의 안전 영역의 개수를 세가며 ans에 추가한다.이때, 안전 영역의 개수가 0이 나오면, 모든 영역이 잠겼다는 의미이므로 반복문을 종료한 후, ans의 최댓값을 정답으로 출력한다.코드N = int(input())height = [list(map(int, input().split())) for _ in range(N)]ans = [1]dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]for h in range(1, 9.. 2025. 2. 7.
14889번 - 스타트와 링크(Python) 풀이백트래킹을 이용해 나눌 수 있는 팀의 경우의 수를 모두 구한다. 우선, status[i][j]에 status[j][i]를 더했다. 따라서 status[i][j]는 i와 j가 팀이 되었을 때 더해지는 능력치의 합이 되었다.(i  이후에 스타트 팀에 0을 고정한 상태로, 스타트 팀에 들어갈 N//2 - 1 명을 백트래킹을 이용해 배정한다.(0이 링크 팀에 들어가는 경우는 스타트 팀에 들어가는 것과 대칭되므로 스타트팀에 속하는 경우만 계산한다.)이후에 스타트 팀에 속하지 않은 N//2 명을 링크 팀에 배정한 후 각 팀의 점수를 구해 두 팀의 점수차의 절댓값을 ans에 넣는다.백트래킹이 끝난 후 ans의 최솟값을 정답으로 출력한다.코드N = int(input())status = [list(map(int, i.. 2025. 2. 7.
1991번 - 트리 순회(Python) 풀이dictionary에 트리를 저장한다.이후에, 함수를 이용하여 각 순회에서 원하는 순서대로 함수를 호출하여 이들을 구현한다.코드N = int(input())tree = dict()for _ in range(N): root, left, right = input().split() tree[root] = [left, right]def preorder(root): if root != '.': print(root, end="") preorder(tree[root][0]) preorder(tree[root][1])def inorder(root): if root != '.': inorder(tree[root][0]) print(r.. 2025. 2. 5.
14888번 - 연산자 끼워넣기(Python) 풀이백트래킹 방식을 통해 입력받은 연산자의 순열 경우의 수를 모두 구한다.구해진 각각의 연산자 배열을 이용해 연산을 수행하고, 이를 저장한다.저장된 수들 중 max와 min 함수를 이용해 최댓값과 최솟값을 구한다.코드N = int(input())A = list(map(int, input().split()))numOfOperators = list(map(int, input().split()))stack = []nums = []ops = []visited = [False for _ in range(N-1)]for i in range(4): for j in range(numOfOperators[i]): nums.append(i)def dfs(): if len(stack) == N-1: .. 2025. 2. 4.

티스토리툴바