목록알고리즘/SWEA (72)
여름의 서재
📕 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. 입력값을 리스트로 만들어서 micros 리스트에 담는다. 2. 먼저 1시간이 지났을때의 각각의 위치를 변경하고 만약 빨간 약품으로 넘어가면 방향과 미생물의 개수를 바꾼다. 3. 정사각형 셀과 크기가 같은 matrix 를 만든다. 4. micros를 돌면서 matrix의 해당 위치에 숫자를 넣어주고, 만약 같은 위치에 여러개의 군집이 있다면 cnt를 합해주고 미생물의 개수가 ..
📕 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. 전선의 길이를 구해주는 length_wire 라는 함수를 만들어준다. 2. 코어들의 좌표와 전선이 방향이 담길 cores라는 리스틀 만든다. 3. 그래프를 돌면서 코어가 있는데 벽에 붙어있는 코어라면 좌표와 5가 담긴 리스트를 cores에 넣는다. 벽에 붙어있는 코어가 아니라면 좌표와 -1이 담긴 리스트를 cores에 넣는다. 4. dfs의 첫번째 인자는 현재 보고 있는 코..
📕 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. 다익스트라 알고리즘을 이용했다. 2. dp 2차원 리스트에는 출발점에서 부터 그 위치까지 갈 때 드는 최단시간이 담기게 된다. 3. 현재 위치에서 사방을 탐색해서 갈 수 있는 곳이라면 다음 위치의 dp값과 (현재 위치의 dp값 + 다음 위치 복구시간)을 비교해서 다음 위치의 dp값이 더 크다면 다음 위치를 deq에 담고 다음 위치의 dp값을 (현재 위치의 dp값 + 다음위치..
📕 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4xuqCqBeUDFAUx SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. dijkstra1은 각 집에서 인수의 집으로 가는 최단 거리를 구하는 함수이다. 2. 인수의 집을 출발지로 생각하고 반대로 거슬러 올라간다. 3. 그렇기 때문에 인접한지 인접하지 않은지 확인할때 다음 노드에서 현재 노드로 연결되어있는지를 확인해야 한다. 4. dp는 인수의 집(도착지)에서 각 노드들까지 가는 최단 거리가 담기게 된다. 5. dijkstra2은 인수의 집에서 ..
📕 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. 관계들을 입력받으면서 두 노드들을 union 시킨다. 2. 모든 관계들을 union하고 나면 그룹이 만들어지게 된다. 3. 각 노드들을 돌면서 노드들의 루트들을 찾으면 그 루트들의 개수가 그룹의 무리의 개수가 된다. def find_set(x): if x == parents[x]: return x return find_set(parents[x]) def union(x, y)..
📕 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. 미리 가중치를 구해서 인접 행렬의 해당 위치에 가중치를 저장해주었다. 2. 시작 노드인 0의 key 값을 0으로 바꿔준다. 2. key를 돌며 가장 작은 값을 가지고 있는 노드를 찾는다. 그리고 방문 체크를 해준다. 3. 2번에서 찾은 노드의 인접 노드들을 탐색하며 방문하지 않은 노드가 있다면 가중치와 해당 노드의 key값을 비교해서 현재 가중치가 key 값보다 작다면 ke..
📕 문제 https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 def dijkstra(s): distance[s] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): # 현재 위치에서 가장 가까운 거리에 있는 노드 찾기 min_idx = -1 min_val = float('inf') for i in range(N+1): if not visited[i] and distance[i] < min_val: min_idx = i min_val = distance[i] vis..
📕 문제 https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 💡 풀이법 1. 다익스트라 알고리즘을 이용했다. 2. matrix와 크기가 같은 2차행렬 dp를 만들어준다. 3. 0,0 부터 시작을 한다. 4. 현재 위치에서 사방을 탐색하고 갈 수 있는 위치라면 다음 위치가 현재위치보다 높이가 더 높다면 그 차이를 계산해서 가중치를 구한다. 5. 만약 dp에서 다음위치의 값이 현재 위치에서 가중치를 더한 값보다 크다면 deq에 다음 위치를 담아주고, dp의 값을 바꿔준다. (dp값이 현재위치에서..