참고: https://www.acmicpc.net/problem/1966 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 문서의 개수가 100까지밖에 주어지지 않아서 2중 for문을 돌아도 괜찮을 것 같다고 생각을 했다. 그러고 나서 현재 Queue가 앞 뒤로 추가/삭제 되면서 해당 문서가 몇 번째 있는 지에 대한 기록을 어떻게 구성해야할지 생각해보던 중 딕셔너리를 이용하지 않고 리스트를 활용해서 스택을 2개 만들어준 뒤, 각각에 동일한 Queue 연산을 수행하여 문제를 풀 수 있겠다는 생각이 들었다. import sys input = sys.stdin.readline t = int(input()) for _ in range(t): n, m = map(int, input().split()) q = list(m..
참고: https://www.acmicpc.net/problem/4963 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 다음과 같이 예제 입력이 주어졌을 때, 상하좌우 및 대각으로 이루어진 1을 섬이라고 보기 때문에 0 1 1 3 1 9 (줄바꿈해서) 에 대한 출력이 나와야한다. (-1, -1) (-1, 0) (-1, 1) (0, -1) 기준점 (0, 1) (1, -1) (1, 0) (1, 1) 상하좌우를 기준으로 하던 기존 그래프 탐색과 다르게 대각선 4가지의 꼭짓점도 탐색해야하기 때문에 8번의 반복문을 돌아야한다. 그리고 섬은 대각선으로 이어진 1을 깊이 탐색하면서 방문 여부를 체크하고, 다 마친 dfs 탐색이 존재하면 섬의 갯수를 1씩 늘려가면서 세어주는 방식으로 코드를 작성하였다. import sys..
참고: https://www.acmicpc.net/problem/2178 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 문제에서 유난히 '붙어서'라는 글자가 굵게 볼드처리 되어있는데, 기존에 띄어서 입력을 받은 것에서 붙은 입력을 리스트로 저장하기 위해 split()이 아닌 strip()을 사용하여 리스트 형태로 만들 수 있다. 다음과 같이 현재의 수에서 넓게 탐색을 진행하면서 진행 방향에 현재의 수 + 1만큼을 해주게 되면, 마지막 수에는 지금까지 거쳐온 횟수인 15를 저장할 수 있게 된다. import sys from collections import deque input = sys.stdin.readline n,m = map(int, input().split()) maze = [list(map(int,..
참고: https://www.acmicpc.net/problem/7562 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 예제를 보면 반복할 횟수(테스트케이스)만큼 반복하면서 입력을 받고, 그 입력은 3줄로 주어지게 된다. 가장 처음 주어지는 값은 체스판의 크기 IxI가 되고, 그 다음은 현재 나이트가 있는 칸과 이동하려는 칸이 주어진다. 기존 그래프 문제와 다른 것은 나이트가 이동할 수 있는 방향에 대한 dy, dx의 설정값이라고 볼 수 있다. 문제에 주어진 나이트의 이동을 x, y축 방향으로 좌표를 적어보았다. x의 왼쪽은 음수, 오른쪽은 양수를 나타내고 y의 위쪽은 음수, 아래쪽은 양수를 나타낸다. 그러면 총 8가지의 좌표가 나오게 되고, 상하좌우의 4번 반복과는 다르게 총 8번의 반복을 진행하면서 숫자..
참고: https://www.acmicpc.net/problem/1260 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 출력의 첫 번째 줄에는 DFS의 수행 결과를, 두 번째 줄에는 BFS의 수행 결과를 출력하면 되는 문제이다. 앞서 DFS 기초가 되는 24479와 24480을, BFS 기초가 되는 24444와 24445를 풀었으면 해당 코드를 참고하여 쉽게 문제를 풀어낼 수 있다. import sys from collections import deque sys.setrecursionlimit(10**9) input = sys.stdin.readline n, m, v = map(int, input().split()) graph = [[0] * (n+1) for _ in range(n+1)] bfsVisite..
참고: https://www.acmicpc.net/problem/11074 ✔️ 문제 문제는 다음과 같다. ✔️ 풀이 해당 문제는 그리디 알고리즘 유형으로 최적의 해를 구할 수 있다면 해당 로직을 구성하여 빠르게 문제를 푸는 방식이다. 잔돈의 종류는 정해져있고, 나누어 떨어질 수 있는 해가 존재하기 때문에 간단한 계산 공식으로 풀 수 있다. import sys input = sys.stdin.readline n,k = map(int, input().split()) money = [int(input()) for _ in range(n)] money.sort(reverse=True) cnt = 0 for i in money: if i > k: continue cnt = cnt + (k//i) k %= i p..
