백준
[BaekJoon] 백준 16928번 뱀과 사다리 게임 - Python
[BaekJoon] 백준 16928번 뱀과 사다리 게임 - Python 🎈문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 💬설명 간단한 bfs문제 게임판 전체를 기준으로 주사위 1-6칸이 나왔을 경우를 하나씩 큐에 넣어가면서 해결하면 되는 문제 포인트는 사다리나 뱀을 만난 경우 이동하는 칸으로 update를 해줘야 한다는 것이다. 👩💻코드 from collections import deque..
[BaekJoon] 백준 7576번 토마토 - Python
[BaekJoon] 백준 7576번 토마토 🎈문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 💬설명 비슷한 문제를 여러개 풀어봤기 때문에 금방 풀었다. Bfs로 많이 푼 것 같은데, 큐를 쓰지 않고 풀었다. 아래와 같이 푸니까 pypy로 채점하지 않고 제한시간을 만족시킬 수 있었다. 아래와 같이 푼다. 토마토 위치를 먼저 배열에 저장해준다. 익은 토마토 개수와 모든 토마토 개수를 따로 저장해준다. (나중에 일일히 세지 않고..
[BaekJoon] 백준 7569번 토마토 - Python
[BaekJoon] 백준 7569번 토마토 - Python 🎈문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 💬설명 처음에 bfs로 큐를 써서 풀려고 하다가 적용하지 않고 풀어봤다. 대신 시간 초과에 걸려서 pypy로 채점했다. 확실하게 시간 단축해서 풀고 싶으면 queue로 풀어줘야 할듯 풀이는 간단하다. 매일 추가된 익은 토마토에 대해 6개 방향을 체크해서 익은 토마토의 개수와 전체 토마토의 개수가 같다면 출력 ..
[BaekJoon] 백준 10159번 저울
[BaekJoon] 백준 10159번 저울 🎈문제 https://www.acmicpc.net/problem/10159 💬설명 플로이드-와샬로 모든 점에서 다른 모든 점으로 갈 수 있는지를 모두 구하고, a -> b, b -> a인 경로가 있다면 무게 비교가 가능한 개수에 추가해서 출력하면 된다. 👩💻코드 # BaekJoon10159.py N = int(input()) M = int(input()) relation = [[False for _ in range(N)] for _ in range(N)] # 연결 배열 생성 for _ in range(M): a, b = map(int, input().split()) relation[a - 1][b - 1] = 1 # 플로이드-와샬로 이동 가능한 보든 경로 구하..
[BaekJoon] 백준 4358번 생태학
[BaekJoon] 백준 4358번 생태학 🎈문제 https://www.acmicpc.net/problem/4358 💬설명 문제에는 트라이 알고리즘이라고 적혀있었지만 dictionary로만 풀어도 풀리는 문제였다. 포인트 데이터가 크기 때문에 시간을 최대한 줄여줘야 했다. (pypy로 하지 않고 python으로 채점해도 되긴 함) 입력이 언제 끝나는지 따로 표시해주지 않는다. 입력이 끝났는지 따로 체크해줘야 함 출력 시 소수점 4째자리까지 반올림 해서 출력하라고 하는데 그냥 round만 쓰면 50 -> 50.0000으로 출력하지 않기 때문에 %.4f로 출력해줘야 한다. 👩💻코드 # BaekJoon4358.py import sys input = sys.stdin.readline dic = {} sum_t..
[BaekJoon] 백준 17144번 미세먼지 안녕!
[BaekJoon] 백준 17144번 미세먼지 안녕! 🎈문제 https://www.acmicpc.net/problem/17144 💬설명 - 단순한 구현문제였다. - 다만 python3로 채점하니 시간초과가 나서 pypy로 채점했다. 👩💻코드 # BaekJoon17144.py import copy # 변수 및 배열 초기화 R, C, T = map(int, input().split()) dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] A = [[] for _ in range(R)] cleaner = [] for i in range(R): A[i] = list(map(int, input().split())) for _ in range(T): # 확산 new_A = copy.deepcopy..
[BaekJoon] 백준 2098번 외판원 순회
[BaekJoon] 백준 2098번 외판원 순회 🎈문제 https://www.acmicpc.net/problem/2098 💬설명 간단하게 말하자면, 해당 문제는 사이클을 구하는데 그 사이클을 돌 때 가장 적은 비용이 드는 사이클을 구하는 것이다. 즉, 1->0->2->3->1 이렇게 돌아서 오는 경우와 2->3->1->0->2 이렇게 돌아서 오는 경우가 드는 비용이 같다는 것을 우선 염두에 두고 생각을 해보자. (편의상 0번 도시부터 있다고 가정하자.) 그렇게 되면, 우리는 모든 경우를 돌 때 0번 도시에서 출발한다고 가정해도 무방하다. 0->...->0 에서 ("..." 에 들어가는 도시들의 순서 + 모든 도시들을 돌았는지)만 고려해주면 되니까! 다시 말해서, 0번 도시에서 시작하는 경우만 생각하더라도..
[BaekJoon] 백준 2011번 암호코드
[BaekJoon] 백준 2011번 암호코드 문제: https://www.acmicpc.net/problem/2011 내코드 다이나믹 프로그래밍에 익숙하지 않아서 다이나믹 프로그래밍 문제를 찾다가 발견해서 풀었다. 즉, 다이나믹 프로그래밍 문제인 것을 알고 풀었다. 우선 점화식을 찾았다. f("25114")가 25114에서 나올 수 있는 암호의 개수라고 하자. f("25114") = f("2511") + f("251")이 된다. 즉, f(n) = f(n[:-1]) + f(n[:-2]) 이다. 이렇게 금방 점화식을 찾을 수 있다. 두번째로 생각해야 할 부분은 메모이제이션이다. 시간 초과를 피하기 위해 딕셔너리를 만들어 줬다. 여기서는 f(n)에서 n의 길이가 같다면 f(n)이 같다는 특징이 있다. 즉, 길..