CS
[Programmers] 행렬 테두리 회전하기
[Programmers] 행렬 테두리 회전하기 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/77485 💬설명 회전을 구현할 수 있냐고 물어보는 기본 구현 문제였다. 회전 방향을 dx, dy 배열로 선언해두고 direction + 1 해가면서 각 변의 길이만큼 회전해주면 된다. 처음 회전 문제를 풀어봤으면 헤맸을 수도 👩💻코드 # Programmers_행렬테두리회전.py def rotate(arr, query): dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] x, y = query[0] - 1, query[1] - 1 pre_value = arr[x][y] len_x = query[3] - query[1] len_y = query..
[BaekJoon] 백준 2638번 치즈
[BaekJoon] 백준 2638번 치즈 🎈문제 https://www.acmicpc.net/problem/2638 💬설명 bfs로 풀었다. 과정 bfs를 이용해 [0, 0]부터 시작해서 (치즈 내부에 있지 않은) 모든 빈공간을 탐색한다. 이때 치즈가 있는 곳의 좌표를 마주칠 때마다 개수를 카운트 해놓는다. 카운트 해놓은 개수로 2 이상인 치즈는 지운다. 1-2를 반복하고 만약 치즈가 다 녹아 없어진 경우 횟수를 출력한다. 👩💻코드 # BaekJoon2638.py from collections import deque N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] dx = [0, 0, 1, ..
[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 # 플로이드-와샬로 이동 가능한 보든 경로 구하..
[Algorithm] 플로이드 와샬(Floyd Warshall)
플로이드 와샬 하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 다익스트라와는 다르게 플로이드 와샬은 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 또한 다이나믹 프로그램에 기반을 두고 있다. 알고리즘 핵심은 "X에서 Y로 가는 최소 비용 vs X에서 선택된 노드로 가는 비용 + 선택된 노드에서 Y로 가는 비용" 중 최소값을 선택하는 것이다. 즉, 점화식으로 나타내자면 distance[i, j] = min(distance[i, j], distance[i, n] + distance[n, j]) int INF = 1000000; int a[4][4] = { { 0, 5, INF, 8 }, { 7, 0, 9, INF }, { 2, INF, 0, 4 }, { INF..
[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..
[Algorithm] 다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘이란? 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있음 다만 이때 음의 간선을 포함할 수 없는데(비용이 음수일 수 없음!) 현실에선 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 적합하다고 할 수 있다. 다이나믹 프로그래밍인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문'. 즉, 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 사용하게 된다. 알고리즘 출발 노드를 설정 출발 노드를 기준으로 각 노드까지 가는 비용을 최소 비용으로 저장하고 출발 노드를 방문한 노드로 체크 현재 방문한 노드들과 연결되어 있고 방문하지 않은 노드 중에서 가장..
[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 =..