성댕쓰 똑똑한 생활

정렬은 어떤 기준에 따라 데이터를 순서대로 나열하는 것. 여러 가지 정렬 방법에 대해 알아보자. 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 정렬방법이다. from typing import List # 선택 정렬 def SelectionSort(arr: List[int]) -> None: for i in range(len(arr)): minIndex = i for j in range(i+1, len(arr)): if arr[minIndex] > arr[j]: minIndex = j arr[i], arr[minIndex] = arr[minIndex], arr[i] # 스와프 print(arr) array = [7, 5, 9, 0, 3, 1, 6, 2,..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 29. 21:44

플로이드 워셜 알고리즘은 모든 출발점에서 모든 도착점까지 최단 경로를 구하는 알고리즘이다. 구하는데 시간복잡도가 O(N^3) 이기 때문에 N의 크기가 500이면 2억이 넘는다. N의 크기가 500 이상이면 알고리즘 수행 시간이 1초 이상 걸릴 수 있다. INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 무한으로 초기화 graph = [[INF]*n+1 for _ in range(n+1)] # 자기 자신에서 자기 자신으로 가능 비용은 0으로 초기화 for a in range(1, n+1): for b in range(1, n+1): if a =..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 19. 21:14

출발지에서 모든 노드로 가는 최단 거리(비용)을 구하는 알고리즘이다. 알고리즘은 다음과 같이 구현한다. 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