본문 바로가기

문제 풀이262

[Python] 백준 14499번 : 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 💡 문제 풀이 기본적인 구현 문제이다. 요구사항에 맞게만 구현하면 된다. ✔️ 느낀 점 최적의 코드를 짜고 싶었다. 하지만 알고리즘은 시간과의 싸움 아닐까..? 그냥 구현하는 게 맞는지 잘 모르겠단 고민이 들었다. 💻 코드 import sys ; input = sys.stdin.readline UP, DOWN, LEFT, RIGHT.. 2023. 3. 2.
[Python] 백준 25341번 : 인공 신경망 https://www.acmicpc.net/problem/25341 25341번: 인공 신경망 첫째 줄에 입력층의 입력 크기 $N$, 은닉층의 인공 신경 개수 $M$, 출력값을 계산해야 하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N,M,Q \leq 2\,000)$ 둘째 줄부터 $M$번째 줄에 걸쳐 은닉층의 www.acmicpc.net 💡 문제 풀이 수학 문제이다. 주어진 조건대로 구현하면 무조건 시간초과가 발생한다. 따라서 연산회수를 줄어야 할 필요가 있다. 결합법칙을 생각해서 구현하면 쉽게 풀 수 있다. ✔️ 느낀 점 그대로 구현하면 시간 초과가 발생해서 조금 손을 봐줘야한다. 이걸 보면서 약간의 DP의 느낌이 났다..! 💻 코드 import sys ; input = sys.std.. 2023. 3. 1.
[Python] 백준 15686번 : 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 문제 풀이 기본적인 구현, DFS 문제이다. ✔️ 느낀 점 💻 코드 import sys from itertools import combinations input = sys.stdin.readline N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] chick.. 2023. 2. 27.
[Python] 백준 1520번 : 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 💡 문제 풀이 그래프 탐색(DFS)에 DP를 곁들인 문제이다. 그냥 DFS로 구현하면 시간초과가 발생한다. 그래서 이미 지나온 길에 대해서는 이전에 방문한 결과를 바로 전달해 주는 방식으로 중간에 순회하는 시간을 줄일 수 있다. ✔️ 느낀 점 그냥 DFS 문제인 줄 알았지만 DP가 곁들인거 보고 큰코다쳤다. 💻 코드 import sys input = sys.stdin.readline dx = [.. 2023. 2. 26.
[Python] 백준 17396번 : 백도어 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 💡 문제 풀이 기본적인 다익스트라 문제이다. 추가적으로 특정 조건에 값을 추가할지 말지 확인하는 로직만 추가하면 된다. ✔️ 느낀 점 오타 나서 한참 찾았다.. 💻 코드 import heapq, sys INF = int(1e9) input = sys.stdin.readline def dijkstra(start): q = [] heapq.heappush(q, (0, sta.. 2023. 2. 25.
[Python] 백준 1956번 : 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 💡 문제 풀이 플로이드-워샬 문제이다. 각 노드 사이의 최단거리를 구하고 만들어지는 사이클에 대한 최솟값을 구하면 된다 사이클은 단순히 시작점에서 목표 지점과 목표 지점에서 시작점을 접근할 수 있는지만 확인하면 된다.. 일방통행이라 다양한 경우를 따지지 않아도 괜찮다. ✔️ 느낀 점 중간에 사이클을 어떻게 고려할까 고민을 조금했는데 생각해 보면 간단한 문제였다. .. 2023. 2. 23.

티스토리툴바