성댕쓰 똑똑한 생활

출발지에서 모든 노드로 가는 최단 거리(비용)을 구하는 알고리즘이다. 알고리즘은 다음과 같이 구현한다. 1. 모든 노드에 대해 비용이 무한인 배열 a를 선언한다. 2. a에 출발 노드는 0으로 세팅. 3. 모든 노드에 대해 방문 체크할 수 있는 배열 b를 선언한다. 4. b에 출발 노드 방문으로 체크 5. 출발노드와 연결된 노드를 탐색하면서 탐색노드로 가능 비용을 a에 업데이트 한다. 6. 방문하지 않는 노드 중 최소 비용 노드를 선택하고 연결된 노드를 탐색하면서 비용이 기존 a보다 작으면 a에 업데이트 한다. 7. 모든 노드를 방문할 때까지 6을 반복한다. 이를 구현한 코드는 아래와 같다. # 최단 경로를 선형으로 찾는 방법 INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드,..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 17. 20:47

내가 짠 코드 from bisect import bisect_left, bisect_right N, x = map(int, input().split()) array = list(map(int, input().split())) class CountOfNum: def __init__(self, _N: int, _array, _x:int) -> None: self.m_arrayLen = _N self.m_array = _array self.m_target = _x def UseBisect(self) -> int: left = bisect_left(self.m_array, self.m_target) right = bisect_right(self.m_array, self.m_target) if right == l..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 16. 15:57

내가 짠 코드 N,M = map(int, input().split()) cakeArray = list(map(int, input().split())) class RiceCakeMaking: def __init__(self, array, arrayLen:int, reqLength:int ) -> None: self.m_arr = array self.m_arrLen = arrayLen self.m_reqLen = reqLength def Solve(self) -> int: maxHeight = 2000000000 left = 0 right = maxHeight while left < right: mid = (left + right) // 2 spareLength = 0 # Get 자른 길이 합 for i i..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 16. 15:22

순차 탐색 : 리스트 안 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법 이진 탐색 : 정렬 되어있는 리스트에서 탐색 범위를 절반씩 좁혀 데이터를 탐색하는 방법 - 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. class BinarySearch: def __init__(self, array) -> None: self.m_array = array # 재귀적으로 구현 def SearchRecur(self, target : int) ->int: return self._searchRecur(target, 0, len(self.m_array) - 1) def _searchRecur(self, target : int, left : int, right : int) -> int: if left >..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 16. 15:17

LIS(최장 오름차순 부분수열 문제와 같은 문제이다. 문제를 보고 아이디어를 생각해내지 못했고 해답을 보고도 이해하는데 많은 시간이 걸렸다. 내가 짠 코드 N = int(input()) sol = list(map(int, input().split())) class SoldierPlacement: def __init__(self, soldierList, n : int) -> None: self.m_soldierList = soldierList self.m_n = n self.m_d = [1] * n def Solve(self) -> int: for i in range(1, self.m_n): for j in range(0, i + 1): if self.m_soldierList[j] > self.m_sold..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 16. 13:23

내가 짠 코드 class Repo: def __init__(self, goldList, row: int, col :int) -> None: self.m_goldList = goldList self.m_row = row self.m_col = col Repos = [] T = int(input()) for _ in range(T): n, m = map(int, input().split()) inputList = list(map(int, input().split())) goldList = [[0]*m for _ in range(n)] for i in range(n): for j in range(m): goldList[i][j] = inputList[i*m + j] print(goldList) Repos.ap..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 14. 22:55

문제풀이 아이디어 X원 만들기 위한 최소한의 화폐 개수는 X-a, X-b ... X-t 최소한의 화폐개수 중 최소값의 +1이다. 내가 짠 코드 from typing import List N,M = map(int, input().split()) l = [0] * N for i in range(N): l[i] = int(input()) class EffCurrency: def __init__(self, ll : List[int], t : int) -> None: self.m_cl = ll self.m_target = t self.m_d = [10001] * (t + 1) def Solve(self) -> int: for i in range(1, self.m_target+1): locMin = 10001 fo..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 13. 22:21

내가 짠 코드. 탑다운 방식이고 26이외의 입력 값외에 제대로 작동하는지 검증되지 않았다. 바텀업 방식을 생각해내지 못했다. X = int(input()) class MakeToOne: def __init__(self) -> None: self.m_dp = [0] * 30001 def Solve(self, a : int) -> int: if a == 1 : return 0 if self.m_dp[a] != 0: return self.m_dp[a] l = [] if a % 5 == 0: l.append(a//5) if a % 3 == 0: l.append(a//3) if a % 2 == 0: l.append(a//2) l.append(a-1) ll = [] for i in l: ll.append(self...

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 12. 21:46

내가 만든 코드 N = int(input()) foodList = list(map(int, input().split())) class AntWarrior: def __init__(self, foodList) -> None: self.m_foodList = foodList self.m_dp = [0] * 2 def Solve(self) -> int: self.m_dp[1-1] = self.m_foodList[0] self.m_dp[2-1] = max(self.m_foodList[0], self.m_foodList[1]) nowLen = 3 for i in range(nowLen, len(self.m_foodList) + 1): temp = self.m_dp[1] self.m_dp[1] = max(self...

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 11. 23:18

N x M 크기의 직사각형 형태의 미로에 갖혔다. 미로에는 여러마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출가능한 형태로 제시 된다. 이때 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하시오. 시작칸과 마지막 칸을 모두 포함하여 계산한다. 주어진 graph 공간에 최단 거리를 기록하고 탐색이 진행될 때마다 최단 거리를 update하는 아이디어가 핵심. graph에 최단 거리를 update할 생각을 못했다.. 아이디어를 듣고 만든 코드 from typing import List from collections i..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 9. 19:42