Algorithm Problem/Python

[python] SWEA - 1251. 하나로 / 1486. 장훈이의 높은 선반

1. 하나로 문제 해결 1. 프림 + 힙큐 2. 인접리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. key 리스트를 최솟값으로 갱신해가며 결과를 더해준다. 🔨 인접 행렬로 하다가 몇시간 날린 것 같다. 역시 난 인접리스트를 쓰는게 편하다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) x_location = list(map(int, input().split())) y_location = list(map(int, input().split())) tax = float(input()) # 인접 리스트 adj = {i: [] for i in range(n)} for s in range(n): fo..

[python] SWEA - 1249. 보급로 / 5521. 상원이의 생일파티

1. 보급로 문제 해결 1. 다익스트라 알고리즘 + 힙큐 2. 가중치 리스트와 방문 리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. 주변을 탐색하여 최소 가중치를 선택해 가중치를 점점 누적해 나아간다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) maps = [list(map(int, list(input()))) for _ in range(n)] # dist: 가중치를 누적한 리스트, visit: 선택했는지 안했는지 dist = [[float('inf')]*n for _ in range(n)] visit = [[False]*n for _ in range(n)] dx, dy = [-1, 1..

[python] 백준 - 16236. 아기 상어 (삼성 SW 역량 테스트 기출 문제)

문제 해결 1. BFS를 활용한 시뮬레이션 문제이다. (게임 같은 문제) 2. 먼저 상어의 위치, 레벨, 먹은 물고기수, 총이동거리 등을 정의 해준다. 3. 상어의 레벨에 따른 먹을 수 있는 물고기를 찾는다. 4. 물고기를 찾으면 (1) 거리가 가장 가까운 물고기 (2) 그런 물고기가 여러마리이면 가장 위에 있는 물고기 (3) 그런 물고기가 여러마리이면 가장 왼쪽에 있는 물고기를 선택한다. (sort함수를 사용하면 쉽게 얻을 수 있다.) 5. 먹을 물고기를 선택했다면 (1) 상어를 먹을 물고기의 위치로 옮겨준다. (2) 이동횟수와 먹은 물고기수를 더해주고 (3) 상어가 레벨업 할 조건을 만족한다면 레벨업! 6. 더 이상 먹을 물고기가 없다면 break -> 전에 한번 도전했다가 실패한 문제이다. 이번 해..

[python] 백준 - 4963. 섬의 개수

문제 해결 1. DFS or BFS를 이용해 몇개의 무리가 있는지 알아내는 문제이다. 2. while문 한 싸이클이 돌 떄마다 한무리를 체크할 수 있다. 3. visit배열을 따로 만들어 사용하거나, 지나온 곳을 다른값으로 바꿔주는 방법을 이용한다. 소스 코드 from _collections import deque while True: w, h = map(int, input().split()) if w == 0 and h == 0: break island = [list(map(int, input().split())) for _ in range(h)] # 상 우상 우 우하 하 좌하 좌 좌상 # 8방향 탐색을 위해 dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 1, 1, 1, 0..

[python] 백준 - 2606. 바이러스

문제 해결 1. 플로이드와샬 알고리즘 - 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 2. 라고 되어있지만 사실 잘 모르겠고, 이어져있는 정점들을 모두 찾는 문제이다. 3. 인접리스트를 만들고, BFS로 이어져있는 모든 정점을 찾으면 해결되는 간단한 문제! 소스 코드 from _collections import deque def bfs(vertex): # 속도가 빠른 디큐를 사용해서 BFS 탐색 q = deque() q.append(vertex) # 시작점 방문 체크를 True로 해준다음 visit[vertex] = True while q: # 큐에 쌓인 노드들 중에서 하나를 꺼내고 current = q.popleft() # 노드에 인접한 이웃들중 for neighbor in adj[current]..

[python] 백준 - 15683. 감시

문제 해결 완전탐색 시뮬레이션 1. 먼저 CCTV의 위차와 방향들을 따로 리스트에 저장해둔다 2. 각각의 CCTV마다 감시할 수 있는 방향들이 다르기 때문에 하드코딩이지만 방향을 다 설정해준다. (1) 여기서 5번 CCTV는 방향을 바꿀수 없기 때문에 처음부터 탐색할 수 있는 곳들을 모두 표기해준다. 3. DFS를 통해 모든 경우의 수를 계산해 준다. 4. 경우의 수를 하나 찾을 때마다 감시하는 영역을 표시해주어 사각지대가 최소인 부분을 찾는다. -> 뭔가 하드코딩한 것 같지만 시뮬레이션문제라 어쩔 수없는 것같다. 시뮬레이션 문제를 풀면 진이 빠지는 것 같다. 항상 너무 길다...😵 소스 코드 from copy import deepcopy def dfs(idx, maps): # idx : 몇 번째 cct..