Algorithm Problem

[python] 백준 - 1051. 숫자 정사각형

문제 해결 1. (부르트포스) 완전탐색 문제이다. 2. '가장 큰' 정사각형을 구하라고 했으므로 만들수 있는 최대 크기에서부터 하나씩 줄여나갔다.(시간 효율) 3. 네 꼭지점의 크기가 같을 때 return + break를 걸어주어 바로 탐색을 종료 + 난이도가 적당한 2차원배열 + 완전탐색 문제이다. 소스 코드 def find_squre(s): # 정사각형의 꼭지점의 숫자 크기가 같은 경우를 찾는다. for i in range(n-s+1): for j in range(m-s+1): if numbers[i][j] == numbers[i][j+s-1] == numbers[i+s-1][j] == numbers[i+s-1][j+s-1]: return True return False n, m = map(int, ..

[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]..