💻 준성 개발 일지

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 BFS를 이용한 풀이 # 백준 10026번 문제 - 적록색약 from collections import deque dx, dy = [0,0,-1,1], [1,-1,0,0] n = int(input()) graph = [] for _ in range(n): graph.append(list(map(str, input()))) answer = 0 def bfs(x, y): queue ..

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 # 백준 4963번 문제 - 섬의 개수 from collections import deque dx = [0,0,-1,1,1,-1,1,-1] dy = [1,-1,0,0,1,-1,-1,1] def bfs(graph, x, y): queue = deque() graph[x][y] = 0 queue.append((x, y)) global cnt while queue: x, y = queu..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 먼저 BFS로 풀었을 때 시간초과가 나서 pypy3로 확인해봤더니 성공하였다. 왜 시간초과가 났는지 곰곰히 생각해보면서 시간복잡도를 계산해보고 연산을 최소화 시키도록 코드를 바꾸었다. # 백준 7562번 문제 - 나이트의 이동 from collections import deque import sys input = sys.stdin.readline dx = [1,1,-1,-1,2,2,-2,..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 # 백준 14502번 문제 - 연구소 from collections import deque import copy import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [] dx, dy = [0,0,-1,1], [1,-1,0,0] for _ in range(n): graph.append(list(map(int, i..

문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 # 백준 18352번 문제 - 특정 거리의 도시 찾기 from collections import deque import sys input = sys.stdin.readline n, m, k, x = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 from collections import deque t = int(input()) for i in range(t): p = input() n = int(input()) arr = input()[1:-1].split(',') queue = deque(arr) flag = 0 if n == 0: queue = [] for j in p: if j == 'R': flag += 1 elif j == 'D': if len(queue) == 0: pri..

문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 이번 문제는 푸는데 조금 생각도 많이 해보고 여러가지 방법으로 풀어보고 싶어서 시간이 오래걸렸다. 또한 플로이드-워셜 알고리즘을 처음 접해봐서 이해하는데 오래걸린 부분도 있었다. DFS 나 BFS로도 풀이가 가능하지만 플로이드-워셜 알고리즘도 사용해 보았다. DFS를 이용한 풀이 # 백준 11403번 문제 - 경로 찾기 # DFS n = int(input()) graph = [list(map(int, input().split()..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 # 백준 11286번 문제 - 절댓값 힙 import sys import heapq heap = [] n = int(sys.stdin.readline()) for i in range(n): num = int(sys.stdin.readline()) if num != 0: heapq.heappush(heap, (abs(num), num)) else: if not hea..

문제 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 풀이 # 백준 6064번 문제 - 카잉 달력 t = int(input()) for _ in range(t): m, n, x, y = map(int, input().split()) answer = -1 while x

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 # 백준 11725번 문제 - 트리의 부모찾기 n = int(input()) tree = [[] for _ in range(n+1)] for _ in range(n-1): root, child = map(int ,input().split()) tree[root].append(child) tree[child].append(root) visited = [0]*(n+1) def dfs(v): for i in tree[v]: if visited[i] == ..