algorithm88 [삼성 SW 역량테스트 기출] 메두사와 전사들 # N x N 크기의 마을에 도로가 깔려있다. (도로는 0, 비도로는 1)# 집에서 공원까지 산책# 메두사는 오직 도로만을 따라 최단 경로로 공원까지 이동# 메두사의 집과 공원은 항상 도로 위에 있으며(좌표는 서로 다르다고 가정해도 ok)# M명의 전사들이 메두사를 잡기 위해 최단 경로로 이동# 전사들은 도로와 비도로를 구분하지 않고 어느 칸이든 이동 가능# (메두사의 집에 전사들이 초기에 위치하는 경우는 없다고 가정해도 ok)# 메두사는 전사들이 움직이기 전에 그들을 바라봄으로써 돌로 만들어 움직임을 멈출 수 있다.# # # 모든 최단경로 계산은 '맨해튼 거리'를 기준으로 한다 ! ! ! ! !# 1. 메두사의 이동# 메두사는 도로를 따라 1칸 이동하며 공원까지 최단 경로를 따른다. # (만약 집에서 .. 2025. 4. 6. [Backtracking] 백트래킹 알고리즘의 정의 DFS(깊이 우선 탐색) 복습 DFS는 가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다. Backtracking 알고리즘이란 ? '백트래킹'이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다가 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, Backtrack 하는 알고리즘이다. 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 깊이 우선 탐색에서는 한 루트를 끝까지 들여다보고 정답이 없을 시 처음.. 2023. 8. 23. [백준 16236번] 아기 상어 from collections import deque n = int(input()) area = [] result = 0 shark_size = 2 ate_fish = 0 nx = [-1,1,0,0] ny = [0,0,-1,1] for i in range(n): area.append(list(map(int,input().split()))) for i in range(n): for j in range(n): if area[i][j] == 9: shark_location_x, shark_location_y = i, j def bfs(x,y,sharkSize): visited = [[False]*n for _ in range(n)] distence = [[0]*n for _ in range(n)] visite.. 2023. 5. 27. [HackerRank] Knapsack def unboundedKnapsack(k, arr): # Write your code here row = len(arr) col = k dp = [[0]*(k+1) for _ in range(row+1)] for i in range(1,row+1): dp[i][0] = 1 for i in range(1,row+1): for j in range(1,col+1): if j >= arr[i-1]: dp[i][j] = dp[i-1][j] + dp[i][j-arr[i-1]] else: dp[i][j] = dp[i-1][j] for i in range(col,-1,-1): if dp[row][i] != 0: return i 이번 문제는 주어진 배열(arr)의 원소들을 가지고 만들 수 있는 타겟 값(k)을 초과하지.. 2023. 5. 20. [HackerRank] Count Luck def countLuck(matrix, k): row = len(matrix) col = len(matrix[0]) nx = [-1,1,0,0] ny = [0,0,-1,1] start_x, start_y = 0, 0 count = 0 graph = [] for i in range(row): graph.append(list(matrix[i])) for i in range(row): for j in range(col): if graph[i][j] == 'M': start_x, start_y = i, j # Write your code here def dfs(area, x, y): # visited[x][y] = True if area[x][y] == '*': return True direct_count = .. 2023. 5. 19. [HackerRank] Caesar Cipher def caesarCipher(s, k): # Write your code here length = len(s) str_list = list(s) k %= 26 for i in range(length): char_ord = ord(str_list[i]) if char_ord >= ord('A') and char_ord ord('Z'): diff = ord('Z') - char_ord index = (ord('A')-1) + (k-diff) str_list[i] = chr(index) else: str_list[i] = chr(char_ord+k) elif char_ord >= ord('a') and char_ord ord('z'): diff = ord('z') - char_ord index = (ord(.. 2023. 5. 19. 이전 1 2 3 4 ··· 15 다음
