shine_hyun shine_hyun

문득 내가 즐겨쓰는 라이브러리들이 몇개 있는데, 걔네를 쓰지 말라하면, 어떻게 하나.. 고민하다 후다닥 구현 정리중.. min/max heap은 알고리즘에서는 '우선순위 큐'로 더 많이 이용되고 있다. 간단히 소개하자면, min heap이라면, 2진 트리 형태로, 무조건 parent노드가 child노드보다 더 작아야한다. 그래서, 최상의 root노드는 항상 최소의 값이 위치한다. 파이썬에서는 heapq로 사용하는데, life-of-h2i.tistory.com/17 [Python]Minheap 최소 경로를 구할때 많이 쓰이는Priority queue(Minheap) 정리 정렬된 상태로 원소 삽입, 삭제되는 자료구조 * Priority queue 구현 방법이 다양함 - Naiive 하게 배열로 정렬 - Li..

python에서 제공하는 itertools 라이브러리 중 조합에 관련한 4개! combinations(조합) , permutations(순열) , product(중복순열), combinations_with_replacement 요 4개를 직접 구현해보았다. 간단하게 재귀로.. DFS로도 구현이 된다하던데.. (이건.. 나중에.. 또 미룬다.. ㅋㅋ) 재귀로는 요런 식이다. ex > combinations(['a','b','c'],2)=[['a']+combinations(['b','c'],1)]+ [['b']+combinations(['a','c'],1)]+[['c']+combinations(['a','b'],1)] 아주 간단쓰하므로 빠르게 코드로 슉슉 combinations(조합) 서로 다른 n개중에 r..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net [풀이] 전형적인 다익스트라 문제. 단, A에서 B로 가는 길이 여러개일 수 있다는 함정이 존재! 그래서 간단히 처음에 가장 최소인 친구들로만 그래프를 구성해주면 된다. from heapq import heappush,heappop import sys def solution(s,d,X): x=X[s-1] q=[] v=[0]*len(x) for idx,i in enumerate(..

programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr [풀이] BFS로 접근했다. 단, 2차원 map이 아니라 3차원 배열로 visit 과 price를 계..

www.acmicpc.net/problem/2014 [푼 방법] 우선순위 큐 가장 최소인 값에 대해서 주어진 소수를 곱해서 다시 push하는 것을 반복한다. ex> 2,3,5,7-->2 pop -->2*2,2*3,2*5,2*7을 다시 push..--> 다시 pop 요러케..! 단, 같은 값이 계속 들어가는 것을 막기위해 나는 소수 오름차순으로 곱하도록 하고싶었다. 그래서 tuple로 곱한 수에 대한 정보를 같이 넣어서 반복이 없도록 진행했다. from heapq import heappush,heappop def solution(N,arr): q1=[] for i in arr: heappush(q1,(i,i))#1이 곱해졋다고 가정 count=0 while count=x: heappush(q1,(x*val..

데이터 전처리 과정에서 정말 중요한 것 중 하나가 '데이터 샘플링'이다. 나는 정말 별 생각 없이 Minor Class의 개수를 늘리거나, Major Class의 개수를 줄이는 언더샘플링/ 오버샘플링을 진행했다. 하지만, 더 좋은 방법들이 많으니, 정리해봐야지. 언더샘플링 : Major class의 일부를 제거해 알고리즘에 주는 영향을 줄이는 방법 1. Random Sampling 제일 단순하고, 직관적인 방법. Major Class의 일부를 랜덤하게 없앤다. 단순하지만, 효과적이라고 알려져있다. - 단순 랜덤샘플링 : 모든 클래스가 같은 확률로 뽑히도록하는 방법 (같은 개수로 언더 샘플링) - 계통 랜덤샘플링 : 시작 데이터를 임의로 정하고 임의의 K번째마다 데이터를 뽑는 방법 - Cluster 랜덤샘..

최소 경로를 구할때 많이 쓰이는Priority queue(Minheap) 정리 정렬된 상태로 원소 삽입, 삭제되는 자료구조 * Priority queue 구현 방법이 다양함 - Naiive 하게 배열로 정렬 - Linked List로 - Heap 자료구조를 사용 (Min heap 사용) *Min heap Binary tree 구조 부모노드의 키값이 자식노드의 키값보다 작거나 같은 Binary tree *Python heapq모듈을 사용하면 됨

from collections import defaultdict import heapq import sys def solution(s): r=[10000000]*(v+1) r[s]=0 q=[] heapq.heappush(q,[0,s])#(weight,v) while q: cur_w,cur_v=heapq.heappop(q) for i_v,i_w in g_map[cur_v]: if cur_w+i_w