문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 주어진 지문을 그대로 구현하려고 노력했다. 다만 지문에 큰 오류가 있다. 지문의 "현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우"은 이미 청소를 한 구역이어도 지나갈 수 있다. 청소를 한 곳을 다시 방문하지 않게 코딩을 하다가 테스트 케이스를 통과하지 못해서 너무나도 고생했다.... 실제로 아래 짠 코드도 중복되는 코드도 많..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 이중 for문을 사용하면 시간초과가 발생할 수 있다. 파이썬은 1초당 2000만 번의 연산이 가능하다. 그렇기에 n은 최대 500,000이 입력 값으로 주어질 수 있다. 500,000,000,000 -> 5천억 번의 횟수는 주어진 시간제한인 1.5초에 위배된다. 그렇기에 스택을 사용해서 시간 복잡도를 줄여야 한다. 아래의 코드의 시간 복잡도는 O(n)이기에 50만 번의 연산이 이루어진다. ..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 BFS알고리즘을 적용해서 주어진 S초가 지난 뒤에 갱신된 grid에서 목표 값을 출력해준다. 코드 # 18405번 경쟁적 전염 import sys from collections import deque n, k = map(int, sys.stdin.readline().split()) grid = [] queue = [] for i in range(n): li = ..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 문제를 읽어보면 위상정렬 알고리즘임을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.c..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 위상정렬문제인데 입력값이 이전의 문제와 다르게 들어온다. **중복된 간선이 들어올 수 있기 때문에 주의해야한다. : 집합으로 해결해주었습니다. 코드 # 2623번 음악프로그램 import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [set() for _ in ..

https://www.acmicpc.net/status?group_id=13709 채점 현황 www.acmicpc.net 풀이 건물을 짓기 위해서는 선행으로 지어져야하는 건물이 존재한다. - 위상정렬 알고리즘을 적용해야함을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com 코드 # 1516번 게임개발 import sys from collections import deque n = int(sys.stdin.r..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 기본적으로 가르쳐야할 알파벳은 남극의 기본문법인 "a", "c", "i", "t", "n" 총 5개이다. (위의 5개의 알파벳을 가르치지 않으면 어떠한 단어도 읽을 수 없다.) combinations로 조합을 통해 추가로 가르칠 알파벳을 골라주었다. 이를 통해서 완전탐색으로 단어를 읽을 수 있는지 없는지 확인해주었다. 시간초과 문제로 인해 PyPy3로 제출해주었습니다. 코드(PyPy3..