문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 문제를 풀기 위해서 다음과 같은 점화식이 필요하다. 주어진 화폐 단위 별로 해당하는 금액을 완성할 수 있는 동전을 구성하는 개수를 찾아준다. 1. dp[0]을 1로 초기화합니다. 이는 금액 0을 만드는 방법이 하나밖에 없음을 의미합니다(아무 동전도 사용하지 않는 경우). 2. 모든 동전 단위 coin[i]에 대해 반복합니다. 3. 각 coin[i]에 대해 금액 coin[..

문제 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