본문 바로가기

algorithm122

[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] 백준 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.
[Python] 백준 2230번 : 수 고르기 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 💡 문제 풀이 투포인터 문제이다. 요구사항에 맞게 구현하면 된다. ✔️ 느낀 점 이분 탐색을 풀고 싶었는데 투포인터에 더 가까운 문제라고 생각된다. 어려울 것이 없어서 패스... 💻 코드 import sys input = sys.stdin.readline def solution(n, m, arr): start, end = 0, 1 min_ = sys.maxsize while s.. 2023. 2. 23.
[Python] 백준 13023번 : ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 💡 문제 풀이 ✔️ 느낀 점 💻 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [[] for i in range(n)] visited = [False] * n for _ in range(m): a, b = map(int, input().split()) arr[a].append(b) arr[b].append(a) def dfs(idx, number): if number == 4: print(1) exit() .. 2023. 2. 23.

티스토리툴바