성댕쓰 똑똑한 생활

내가 만든 코드 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

문제는 다음과 같다. NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이 있는 부분은 1이다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결된 것으로 간주한다. 얼음 틀 모양이 주어질 때 생성되는 총 아이스크림 개수를 구하는 프로그램을 작성하라. 먼저 내가 짠 풀이는 BFS를 사용하여 구현하였다. from collections import deque from typing import List class IceBeverage: def __init__(self, graph : List[List[int]]) -> None: self.m_graph = graph self.m_col = len(graph[0]) self.m_row = len(graph) self.m_r..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 9. 16:44

DFS 깊이 우선 탐색 스택 자료구조 또는 재귀 함수 사용 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. # DFS 기초 # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 1번 노드부터 있다고 가정 graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] # 각 노드가 방문한 정보를 표현 (1차원 리스트) visited = [False] * 9 def DFS(graph, v, vi..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 6. 22:34

1. 알아야할 자료구조 - Stack : FILO python에서 list를 이용 stack = [] stack.append(5) stack.append(7) stack.append(2) stack.pop() stack.append(1) stack.append(4) stack.append(3) stack.pop() # 최상단 원소부터 출력 print(stack[::-1]) # 최하단 원소부터 출력 print(stack) ******** [4, 1, 7, 5] [5, 7, 1, 4] - Queue : FIFO python에서 list로 구현가능하나 시간 복잡도가 증가하므로 deque자료구조를 이용한다. from collections import deque queue = deque() queue.append..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 6. 21:42

문제: 주어진 String s에서 반복되지 않는 첫번째 character의 index를 return하여라 def FindFirstUniqueCharacter(stringParam : str) -> int: hashMap = {} for c in stringParam: if c in hashMap: hashMap[c] += 1 else: hashMap[c] = 1 for idx, c in enumerate(stringParam): if hashMap[c] == 1: return idx return -1 print(FindFirstUniqueCharacter("nocodeprogram")) print(FindFirstUniqueCharacter("nownocodeprogram")) **************..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 4. 22:52

파이썬 수 자료형 정수형, 실수형이 있다. 실수형 데이터는 정확도가 떨어지므로 round함수를 이용한다. a = 0.6 b = 0.3 print(a+b) if a + b == 0.9: print(True) else: print(False) if round(a + b, 4) == 0.9: print(True) else: print(False) **************** 0.8999999999999999 False True 다른 언어와 다르게 / 연산자는 실수형을 반환한다. 몫을 얻고 싶으면 // 를 사용한다. a = 7 b = 3 print(a/b) print(a//b) print(a%b) **************** 2.3333333333333335 2 1 리스트 자료형 데이터를 연속적으로 담는 자..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 4. 22:08

HashTable 자료구조는 insert, delete, find에 O(1) 시간 복잡도를 갖는다. Sort는 안된다. Hash function은 어떠한 input 값을 정수 output으로 바꾸는 함수이다. 다른 input에 같은 output을 return 할 수 있으며 이런 상황을 hash 충돌이라고 한다. 예를 들어 Hash function -> 은 "Apple" -> 23438881, "Banana" ->759342, "aadf" -> 759342 처럼 input을 정수로 return하며 "Banana"와 "aadf"는 hash 충돌 상태이다. Hash 충돌이 발생해도 HashTable 만드는데는 문제 없는데, 값을 array 공간에 각 index마다 linked list로 구성하면 되기 때문이다..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 3. 23:25

특정한 데이터를 레이블링하여 저장하는 컨테이너를 hash table이라고 한다. 문자 A와 문자 B를 서로 다르게 레이블링하여 저장하는 컨테이너가 그 예이다. A의 Ascill 코드는 65이고 B는 66이다. 이들 문자를 10으로 나눈 나머지값에 해당하는 인덱스에 문자를 저장하면 나중에 A를 찾을 때 나머지 연산으로 저장되어있는 위치를 빠르게 알 수 있다. class HashTable: def __init__(self) -> None: self.capacity = 10; self.basket = [""] * self.capacity def Add(self, alpha : str) -> None: self.basket[ord(alpha) % self.capacity] = alpha def Find(self..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 3. 22:11

circular queue는 capacity만큼의 공간을 가지고 있어서 max size를 넘으면 overflow가 발생한다. 이 점이 queue와 다른점이다. circular queue를 구현하기 위해 나머지 연산을 통해 idx를 구한다. # Title : Circular Queue # Chapter : Queue # 문제 : Circular Queue를 구현하여라 class CircularQueue: def __init__(self, k:int) -> None: self._data = [None] * k self._rearIdx = -1 self._frntIdx = 0 self._size = 0 def enQueue(self, value: int) -> None: self._fullCheck() cap..

똑똑한 개발/Algorithm 과 Data Structure 2021. 8. 5. 21:06