☁ 구름톤이뭐야? kakao x goorm 에서 주최하며, 제주도에서 3박4일간 펼쳐지는 해커톤 해커톤 주제 - #제주 #클라우드 #당일공개 (5기는 지역사회 문제 였다.) 모집 인원 - 30명 ( 가서 들었는데 7~800명이 지원했었다고 한다. ㅎㄷㄷ) 구름톤 참가자 모집! 하영 옵서예 #카카오 #구름 #제주 #해커톤 #K-Digital Platform 9oormthon.goorm.io 여느때와 같이 누워서 인스타 스토리를 넘기다 우연히 광고에서 구름톤의 링크를 발견했다. 아니 해커톤도 좋은데 그걸 제주도에서 한다니..! 보자마자 그냥 이건 내꺼다 싶어서 바로 저장해두었다. #성장 #몰입 #네트워킹 #제주도 모집안내문이 그냥 이해선 그 자체였다. 안그래도 너무 여행가서 개발이 하고싶었는데 이렇게 타이밍..
📌 mutable vs immutable 파이썬의 모든것은 객체로 이루어져있다. 흔히들 외우고 있어서 파이썬엔 mutable(변경가능) 객체와 immutable(변경불가능) 객체가 있다고 알고있을 것이다. 프로그램 실행 시 object의 type이 정해지는데 이후에 변경이 가능하면 mutable object, 변경이 불가능하면 immutable object 이다. immutable int, float, bool, str, tuple mutable list, set, dictionary 📌 객체 중심 파이썬 객체(object) 중심언어이다. 객체에는 세가지 속성이 있다. identity(id) – 컴퓨터 메모리에서 객체가 참조하는 주소 type – 생성되는 개체의 종류를 나타냅니다. ex) list, st..
문제 https://app.codility.com/programmers/trainings/2/rectangle_builder_greater_area/start/ Codility Your browser is not supported Please, update your browser or switch to a different one. Learn more about what browsers are supported app.codility.com from collections import Counter import itertools def solution(A, X): counterDict = Counter(A) answer = 0 candidateArr = [] for k, v in counterDict.it..
동적 계획법에 대한 자세한 내용 : https://haesummy.tistory.com/9 Dynamic Programming (동적 계획법) 문제 해결 방법의 종류 brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. divide and conquer approach dynamic programming approach gree haesummy.tistory.com what ia LCS? Longest Common Subsequence 는 의 subsequence이다. 는 와 의 common subsequence이다. Longest common subsequence? common subsequence들 중 가장 ..
P문제란? 다항시간 내(reasonable time)에 답을 구할 수 있다. 다루기 쉬운 문제 결정론적 다항시간 문제 NP문제란? Nondeterministic Plynomial time 다항시간 내 풀 수 없는 문제 다항시간내에 풀 수 있는지 없는지 모른다. 다루기 어려운 문제 비결정론적 다항시간 문제 -> 적어도 검산은 쉽게 할 수 있는 문제. 하지만 답을 찾기는 어려운 문제 Unsolvable problems 어떤 알고리즘으로도 풀 수 없는문제 Optimization/Decision problems Hamiltonian paths and cycles Traveling salesman problem Is P=NP? P⊆NP P=NP라면? 복잡하고 어려운 문제들을 다항시간 내에 반드시 풀 수 있다. 하..
Shortest Path Problem(최단 경로 문제) 정점 u 에서 v까지의 최단 경로 : 정점 u에서 정점 v까지의 경로 중에 경로의 값이 가장 작은 경로 정점 u를 시작점(source), 정점 v를 도착점(destination) 이라고 한다. δ(u,v) : u에서 v까지의 최단 경로 값 negative-weight cycles이 있으면 최단경로 문제는 정의되지 않는다. δ(u,v)=-∞가 나올 수 있음 positive-weight cycles, zero-weight cycles 는 구할 수 있다. (사이클 무시하면 됨) optimal substructure theorem(최적부분 구조 : 분할된 문제의 결과가 매번 같다)으로 greedy sub를 만족한다. δ(s,v) ≤δ(s,u)+δ(u,v)..
Graph(그래프)와 Tree(트리) 그래프 : 정점(vertex)과 그 vertex를 연결하는 간선(edge)을 하나로 모아둔 자료구조 트리 : 그래프의 한 종류 ,Cycle이 불가능, undirected, connected,노드가 N개인 트리는 항상 N-1개의 간선을 가진다. Weight Undirected Graph(가중 무방향성 그래프) 그래프(vertex,edge 로 이루어진 집합) + undirected (방향성을 가지지 않음) + 각 간선이 값을 가짐 G=(V,E) 간선 집합에 속하는 각 간선 (u,v)는 w(u,v)를 가진다. Spanning Tree(신장 트리), Spanning Forest Spanning Tree : 그래프에 있는 모든 vertex를 연결한 트리, 트리의 각각의 값을 ..
Greedy Algorithm optimization problem을 풀 때 사용 dynamic programming이 너무 과도할 때(복잡할 때) greedy로 더 쉽게 풀 수 있다. 현재 상황에서 최선의 답을 선택. 현재 상황의 최선이 전체의 최선이길 바라면서 푼다. Greedy choice property(앞의 선택이 이후의 선택에 영향을 주지 않는 조건)를 만족할 때 사용한다. 현재 상황에서는 최선이지만 전체에서 최선이라는 보장은 없다. greedy로 풀 수 있는 문제는 모두 dynamic programming으로 풀 수 있다. top-down 구조 (dynamic은 bottom up) ex) 가방채우기 문제, 허프만 코드, 크루스컬 MST, 프림 MST, SSSP Counting money 6...
문제 해결 방법의 종류 brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. divide and conquer approach dynamic programming approach greedy approach Dynamic Programming(DP) 주어진 문제를 하위문제로 나누어서 해결한다. 하위 문제가 서로 연관이 있을 때 사용 (divide and conquer은 서로 연관이 없을 때 사용) optimization problem(최적해를 구할 때) 를 풀 때 사용 (최적화문제 : 답이 여러개인 문제에서 가장 좋은 답을 찾는 문제 ex. 최단경로 문제) 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 ..
