CS/Algorithm 문제
[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] 백준 11909번 배열 탈출
[BaekJoon] 백준 11909번 배열 탈출 🎈문제 https://www.acmicpc.net/problem/11909 💬설명 dp로 푸는 문제 가장 마지막 점인 n,n위치까지 가는 최소 비용의 경로는 이전 경로들의 최소값에 기반하여 나온다. 따라서 이전 값들을 저장해두면서 계산한다. 처음에는 다익스트라 문제라고 생각해서 풀었는데 시간초과가 났다.. 다익스트라로도 풀수 있을 것 같긴한데 시간 고민해봐야 할 것 같다. 👩💻코드 # BaekJoon19236.py import sys input = sys.stdin.readline n = int(input()) board = [list(map(int, input().split())) for _ in range(n)] dp = [[0 for _ in ran..
[BaekJoon] 백준 13913번 숨바꼭질4
[BaekJoon] 백준 13913번 숨바꼭질4 🎈문제 https://www.acmicpc.net/problem/13913 💬설명 bfs로 풀면서 그냥 큐에 모든 경로를 저장하면 시간초과가 난다. before 배열에 해당 위치 직전에 방문한 곳을 저장해줘서 마지막에 한번에 출력했다. 👩💻코드 # BaekJoon13913.py from collections import deque N, K = map(int, input().split()) visited = [False for _ in range(100001)] before = [-1 for _ in range(100001)] # 이동 경로 저장 queue = deque([[N, 0]]) # 수빈이 위치 def print_path(time): global ..
[BaekJoon] 백준 19238번 스타트 택시
[BaekJoon] 백준 19238번 스타트 택시 🎈문제 https://www.acmicpc.net/problem/19238 💬설명 1시간 20분 걸렸다. bfs와 구현 문제 bfs를 구현할 때 visited = True 체크를 안해준다는 등 하나씩 자꾸 빼먹는 실수를 한다. 그리고 마지막에 계속 틀렸다고 나왔는데 벽에 막혀서 승객이 목적지에 도착하지 못하는 경우도 있다는 것을 고려 안했기 때문이었다. 문제가 어설픈건지 내가 이런 조건을 생각을 못한 건지.. 👩💻코드 # BaekJoon19238.py from collections import deque import sys input = sys.stdin.readline N, M, energy = map(int, input().split()) arr =..
[BaekJoon] 백준 20055번 컨베이어 벨트 위의 로봇
[BaekJoon] 백준 20055번 컨베이어 벨트 위의 로봇 🎈문제 https://www.acmicpc.net/problem/20055 💬설명 문제에서 주어진 대로만 하면 된다. 푸는데 40분정도 걸렸다. deque로 풀 수도 있었을 것 같다. 다음엔 그렇게 풀어봐야지 배열에 로봇 위치와 벨트 위치를 넣고 pop, push 해주면서 풀음 👩💻코드 # BaekJoon20055.py N, K = map(int, input().split()) A = list(map(int, input().split())) result = 0 robots = [0 for _ in range(N)] def rotate(): global A, robots, N # 컨베이어 벨트 회전 last = A.pop() A = [last..
[BaekJoon] 백준 20056번 마법사 상어와 파이어볼
[BaekJoon] 백준 20056번 마법사 상어와 파이어볼 🎈문제 https://www.acmicpc.net/problem/20056 💬설명 처음에 fireball을 어떤 방식으로 저장할지 고민하다가 헤매서 다시 풀었다. 풀고 나니 쉬운 문제였는데 2시간 30분이나 걸렸다.. 포인트는 이동시킬때 앞뒤가 이어져 있다는 점이랑 파이어볼을 지우거나 추가할 때 어떤 방식으로 처리할지 이렇게 2가지 인것 같다. 잘못하면 디버깅 하는데만 오래 걸릴수 있는 문제 👩💻코드 # BaekJoon20056.py import copy N, M, K = map(int, input().split()) fireball = {} fireball_n = 0 for i in range(M): fireball[i] = list(map..
[BaekJoon] 백준 16235번 나무 재테크
[BaekJoon] 백준 16235번 나무 재테크 🎈문제 https://www.acmicpc.net/problem/16235 💬설명 원래는 trees 배열에 [[x, y, 나무 나이], ...] 이런식으로 저장했는데 시간 초과가 나서 trees 배열을 3차원으로 해서 trees[x][y] = [나무들 나이] 이런식으로 바꿨다. 이런식으로 저장하게 되면 양분이 부족에서 나무가 죽게 되는 경우 뒤에 나무들을 굳이 체크하지 않아도 된다는 시간단축 효과가 있다. (나무들 더해줄 때 나이순으로 잘 추가해준다면) 처음에 구현자체는 빨리 했으나 시간 초과 때문에 다시 짜서 1시간 10분 정도 걸렸다. 👩💻코드 # BaekJoon16235.py import sys input = sys.stdin.readline N,..
[BaekJoon] 백준 20058번 마법사 상어와 파이어스톰
[BaekJoon] 백준 20058번 마법사 상어와 파이어스톰 🎈문제 https://www.acmicpc.net/problem/20058 💬설명 처음에 틀렸던 포인트 조건에 부합하면 얼음의 양을 감소시켜 줄 때, 루프를 통해 하나씩 돌게 되는데 루프에서 감소되서 0이 되는 경우 나중에 한번에 감소시켜줘야한다. 중간중간 감소시켜주면 뒤에 도는 부분에서 영향을 미쳐서 오답이 됨. 1시간 15분 정도 걸렸는데 초반에 회전하는 부분에서 잘못 풀었다가 다시 푸는 바람에 오래 걸렸다. 코드 자체도 효율적으로 푼 코드는 아니다. 다시 풀어봐야지 👩💻코드 # BaekJoon20058.py import copy from collections import deque n, Q = map(int, input().split(..