느낌표 공장

문제 https://www.acmicpc.net/problem/1325 해킹한 컴퓨터 이므로 방문 개수를 반환 return sum(visited) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): com1, com2 = map(int, input().split()) graph[com2].append(com1) # com2에서 com1을 감염 시킬(방문 할) 수 있다. answer = [] max_v = 0 for i in range(1, n+1): tmp_v = bfs(i) if max_v < tmp_v: # 해킹할 수 있는 컴퓨터 수가 더 많은 경우 answer = [i] # 배열 초기화 max_v =..

문제 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 풀이 과정 1931번 회의실 배정 문제가 떠오르는 문제였다. 처음에는 회의실이 없다면 새로 만들고 회의실마다 시간을 비교해주면서 계산하는 2중 for문을 생각했는데 그렇게 하면 시간 초과가 날 것 같아 고민을 했다. 가장 먼저 끝나는 곳을 찾고 비교하는 것이 관건이었으므로 최솟값과 최댓값을 빠르게 찾는 heap이 생각나 이를 사용하여 해결할 수 있었다. 회의 끝나는 시간을 heap에 넣고..

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 과정 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구해야 하므로, 공장 두 곳을 이은 다리들 중 중량 제한이 더 큰 다리를 건너는 것이 좋다. 따라서 입력받은 다리 정보들을 다리의 중량 제한을 기준으로 하여 내림차순으로 정렬하고, 다익스트라를 사용하되 힙에 push 할 때, 중량을 마이너스를 붙여 push 하여 최대..

문제 https://www.acmicpc.net/problem/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 과정 동영상과 유사도를 가지고 그래프를 만들어 농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 여기서 주의할 점은 존은 두 쌍 사이의 동영상의 유사도를 그 경로의 모든 연결들의 유사도 중 최솟값으로 한다. MooTube (Silver) (BOJ 15591)에서는 각 노드마다 BFS를 돌려 ..

문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 과정 동영상과 유사도를 가지고 그래프를 만들어 농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 따라서 이어진 동영상의 유사도가 k이상이면 해당 동영상에서 또 이어진 동영상을 탐색해야 하는 과정을 반복해야 하고, 동영상 개수를 세야 하므로 BFS를 활용하였다. 여기서 주의할 점은 존은 두..

문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 풀이 과정 프로그래머스 - 다리 위를 지나는 트럭과 같은 문제였다. 큐를 이용하여 문제를 해결하였다. 트럭이 한 대씩 다리에 올라가게 된다. (다리 => 큐) 이때 다리에 트럭이 올라갈 자리가 있다면 1-1. 그리고 해당 트럭의 무게로 다리에 올라가도 된다면, 다리에 트럭을 추가해주고, 현재 다리의 무게를 기록한다. (시간 + 1) 1-2. 트..

문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 과정 투 포인터 방식으로 풀었다. 두 개의 포인터를 맨 왼쪽과 맨 오른쪽에 놓고 한 칸씩 이동하면서 회문인지 유사회문인지 일반 문자열인지 판별하였다. 코드 # 회문인지 체크하는 함수 def check_palindrome(l, r): while l < r: if string[l] != string[r]: return False l += 1 r -= 1 return True t = int(input()) for _ in..

문제 https://www.acmicpc.net/problem/24553 24553번: 팰린드롬 게임 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1\,000$) 둘째 줄부터 $T$개의 줄에 걸쳐, 돌 무더기에 쌓여 있는 돌의 개수 $N$이 주어진다. ($1 \le N \le 10^{18}$) www.acmicpc.net 풀이 과정 시간제한을 보고 구현은 아니겠다고 생각했는데, 그리디 방법을 찾는 것에 시간이 걸렸다. 그것은 주어진 돌의 개수 n이 10의 배수인지 아닌지로 바로 판단할 수 있다. n이 10의 배수인 경우는 승우가 아무리 머리를 쓰더라도 상윤이가 이기게 된다. 예) n = 10 / 승: 9(승우가 몇 개를 가져와도 나머지가 생김) / 상윤: 1 ➡︎ 상윤 승..

문제 https://www.acmicpc.net/problem/3048 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 풀이 과정 딕셔너리로 풀까, 한 칸씩 이동하도록 할까 등 여러 가지 방식을 고민하다가 0으로 채워진 리스트에 개미들을 넣는 방식으로 풀었다. 그래서 개미들을 각 자리에 맞게 넣어주도록 계산하는 것이 중요했다. 개미들이 들어갈 리스트를 만들어준다. 이때, 각 그룹마다 개미들을 두 칸씩 띄워 넣어줄 것이기 때문에 넉넉한 크기로 만들어준다. 첫 번째 그룹 개미들을 넣는데, 시간(t) 자리부터 넣어준다. (t * 2 ~ t * 2 + n1 * 2) (두 칸씩 띄..

문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이과정 구현문제로 토네이도 방향이 변화하는 것과 퍼지는 비율을 토네이도 방향대로 돌려주는 것이 핵심이다. 코드 import sys sys.stdin = open('input.txt') # 모래 이동 비율 ratio = [[0, 0, 0.02, 0, 0], [0, 0.1, 0.07, 0.01, 0], [0.05, 0, 0, 0, 0], [0, 0.1, 0.07..