공작소

문제 링크 : https://www.acmicpc.net/problem/11723첫 번째 과정파이썬의 set 자료형을 이용해 풀이했다.첫 번째 코드# 11723 : 집합import sysinput = sys.stdin.readlineS = set()m = int(input().rstrip())for _ in range(m): ope = list(input().rstrip().split()) if ope[0] == 'add': S.add(int(ope[1])) elif ope[0] == 'remove': if int(ope[1]) in S: S.remove(int(ope[1])) elif ope[0] == 'check': print(1 if int(o..

문제 링크 : https://www.acmicpc.net/problem/11659풀이 과정구간 합 배열을 O(N) 만에 구하여 들어오는 요청을 O(1) 씩 M번 수행한다.시간 복잡도 : $ O(N) + O(M) $전체 코드 # 11659 : 구간 합 구하기 4import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())arr = list(map(int, input().rstrip().split()))sums = [0]for i in range(n): sums.append(sums[-1] + arr[i])for _ in range(m): a, b = map(int, input().rstrip().split()) p..

문제 링크 : https://www.acmicpc.net/problem/21736풀이 과정I 부터 시작하는 너비 우선 탐색을 이용해 방문하는 P 의 개수를 셌다.전체 코드# 21736 : 헌내기는 친구가 필요해import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())maps = [list(input().rstrip()) for _ in range(n)]queue = deque()visited = [[False for _ in range(m)] for _ in range(n)]for i in range(n): for j in range(m): if maps[..

문제 링크 : https://www.acmicpc.net/problem/11403풀이 과정I번 정점에서 J번 정점으로 가는 길이 존재하는지에 대한 문제이다.정점의 최대 제한도 크지 않으니, Floyd-Warshall 알고리즘을 사용해 I번 정점에서 J번 정점으로 가는 최소 비용을 구했다.전체 코드# 11403 : 경로 찾기import sysinput = sys.stdin.readlinen = int(input().rstrip())dp = [list(map(int, input().rstrip().split())) for _ in range(n)]# Floyd-Warshallfor i in range(n): for j in range(n): if dp[i][j] == 0: dp[i][j] ..

문제 링크 : https://www.acmicpc.net/problem/9019첫 번째 풀이A에서 B로 바꾸는 최소한의 명령어를 구해야 하는 문제이다.D, S, L, R의 명령어를 사용하는 것을 그래프의 간선으로 인식하고 BFS (너비 우선 탐색) 을 사용하면 최소한의 명령어를 구할 수 있다.D, S, L, R 을 사용했을 때의 결과와 현재까지 사용한 명령어 현황을 저장해서 탐색했다. 아무 명령어나 출력해도 되기 때문에, 현재 상태가 B인 정점에 도달했다면 바로 사용한 명령어를 출력하고 종료한다.첫 번째 코드# 9019 : DSLRimport sysfrom collections import dequeinput = sys.stdin.readlinet = int(input().rstrip())for _ in..

문제 링크 : https://www.acmicpc.net/problem/7576풀이 과정익은 토마토 1을 시작으로, 너비 우선 탐색을 이용했다. 인접한 모든 토마토가 익는 날짜를 계산하면 된다.토마토의 전체 개수를 파악하여, 익지 않은 토마토가 존재하는지 여부 또한 파악해야 한다. 전체 코드# 7576 : 토마토import sysfrom collections import dequeinput = sys.stdin.readlinem, n = map(int, input().rstrip().split())arr = [list(map(int, input().rstrip().split())) for _ in range(n)]visited = [[False for _ in range(m)] for _ in range..