생각정리

프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

N*M 행렬에서 (0,0)에서 (N,M)까지 도달하는 최단경로를 찾아야 하는 문제이다. 최단거리를 구할때는 BFS를 이용하는 것이 좋다. 왜냐하면 DFS는 노드의 끝까지 도달하기에 여러 경로를 비교하기에는 시간복잡도가 크기 때문이다. DFS와 BFS를 구현해본지 오래 되었기에 공부하는 차원에서 두가지 방법 모두로 풀어보려 했다. 먼저 DFS이다. DFS는 분기점에서 트리의 끝까지 탐색하고 돌아오기에 탐색 시간이 길고 deepcopy를 이용해 행렬을 탐색마다 새로 할당해주어야 해서 일반적으로 시간초과가 잘 난다. BFS가 아닌 방법으로 최단경로를 찾으려면 사실 DFS말고 DP를 쓰는게 시간복잡도면에서 좋긴하다. from copy import deepcopy import sys sys.setrecursion..

프로그래머스: 햄버거 만들기(파이썬, 스택)

파이썬의 index에 접근하는 기능과 스택을 이용하면 쉽게 풀 수 있는 문제이다. 보통 list에서 원소들이 문제 조건에 맞는지 판단하는 문제는 스택, while문, 재귀를 이용하면 풀린다. 이 문제는 원소의 순서가 중요하므로 스택을 이용하여 풀어보았다. 리스트에 원소들을 계속 집어놓고 -index를 이용하여 리스트의 원소끝부터 4번째 원소까지가 [1, 2, 3, 1]이라면 리스트의 원소들을 4번 제거하고 count를 1 증가시키는 방식이다. def solution(ingredient): s = [] cnt = 0 for i in ingredient: s.append(i) if s[-4:] == [1, 2, 3, 1]: cnt += 1 for i in range(4): s.pop() return cnt

프로그래머스: 문자열 나누기 (파이썬, 반복문)

레벨2를 집중적으로 풀던 중 레벨1에 새로운 문제가 추가되어 풀어본 문제이다. 수를 계속 세야하므로 while문, 재귀함수 혹은 stack등 다양한 풀이가 있겠으나 제일 구현하기 쉬운 while문으로 풀어보았다. 문자열이 하나 남는경우만 잘 처리해준다면 까다롭지 않은 문제였던 것 같다. 나는 python의 list slicing을 이용하여 첫번째 문자 x와 x가 아닌 문자들이 갯수가 같아질 때마다 전체 문자열 s를 줄여주고, 문자열이 남은 경우 답을 하나 더해줌으로써 해결하였다. def solution(s): answer = 0 i,j = 0, 1 # cnt1은 첫번째 문자를 카운트하기 위한 용도이므로 미리 1로 지정하고, 반복문 시작구간을 첫번째문자 +1로함 cnt1, cnt2 = 1, 0 while ..

프로그래머스: 전화번호 목록 (파이썬, hash, dictionary)

hash문제이다. 자바에서는 해시값을 사용하는 자료형이 hashmap이고 파이썬에서는 dictionary이다. 내가 푼 문제가 아닌건 블로그에 기록하지 않는데 풀이가 너무 좋아서 내 나름의 수정을 더해 코드와 깨달은 점을 올려본다. 전화번호부가 10^6이기에 완전탐색을 하면 시간복잡도가 O(n^2)이므로 10^12이 되어 시간초과가 날 것 같았다. 따라서 처음에 푼 풀이는 비교하려는 수보다 큰 수일때만 접두사가 될 수 있다는 점, 비교하려는 수보다 값이 커지면 더 비교를 할 필요가 없다는 점을 이용해 반복문에 조건문을 추가하여 탐색을 중간에 멈추게 함으로써 시간복잡도를 nO(logn)으로 만들어 6*10^6으로 풀려고 시도했으나 보기좋게 마지막시도에서 계속 시간초과가 났다. 예를 들어 [121, 83, ..

프로그래머스: 숫자블록 (파이썬, 구현)

프로그래머스에는 약수를 구하는 문제가 꽤 많은데 그 중 한 문제이다. 길의 길이는 10^9이고 블록의 길이는 최대 10^7이기에 완전탐색을 하면 틀리는 문제이다. 약수를 효율적으로 구하는 것이 문제의 핵심인데 약수는 일일이 나눠서 구해야하므로 완전탐색으로 구해야하고, 더 빠르게 구하려면 약수는 제곱근 전 후로 쌍을 이룬다는 성질을 응용하여 제곱근까지만 약수를 구하고 그 약수들로 수를 나누어 나머지 약수들을 찾아야 한다. 먼저 내가 푼 코드이다. from bisect import bisect_left def get_yaksu(num): # 1은 모든 수의 약수 yaksu = [1] # 제곱근까지 약수를 구함 으로써 탐색 범위를 줄임 for i in range(2, int(num**0.5)+1): if nu..

LightGBM GPU 사용방법 (Linux, window)

서론 LightGBM 학습 시 GPU를 사용해 학습하는 방법에 대해 알아보고자 한다. LightGBM Parameter에 'device_type'으로 gpu 혹은 cuda를 명시하면 되지만 설정하지 않고 gpu나 cuda를 사용하려 하면 error가 나온다. 따라하기만 하면 되지만 자료가 많이 없고 오래된 자료가 많아 나의 경험이 다른 사람들에게 도움이 되었으면 해서 글을 짧게 남겨본다. Linux(Ubuntu)에서 GPU 사용 방법 !git clone --recursive https://github.com/Microsoft/LightGBM !cd LightGBM && mkdir build && cd build !cmake -DUSE_GPU=1 .. !make -j4 !pip uninstall light..

Decision Tree부터 Random Forest, LightGBM까지(Ensemble Learning)

1. Intro 딥러닝을 처음 접하는 사람들의 통념과는 다르게 전통적인 머신러닝 기법들이 더 높은 예측성을 보이는 경우들이 있다. 특히 Decision Tree는 노이즈가 많은 데이터, 정형데이터 등에서 강점을 보이는데 공모전에서 그러한 데이터들을 다루기 위해 LightGBM을 사용하였고 이를 사용하기 위해 공부한 내용들을 bottom-up방식으로 정리해보고자 한다. Decision Tree에 대해 간략하게 알아보고 이를 개선한 Bagging, Boosting에 대해 살펴보겠다. Bagging과 Boosting의 개선판인 Random Froest, Gradient Boosting에 대해 다룬 후 Gradient Boosting의 개선판들에 대해 정리해보겠다. 2. Decision Tree Decision..

LightGBM: A Highly Efficient Gradient BoostingDecision Tree

링크: https://proceedings.neurips.cc/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf Introduction Gradient boosting decision tree (GBDT)는 분류, 회귀, 예측등에서 효과적인 머신러닝 기법이지만 데이터의 크기가 커짐에 따라 Split point들의 모든 경우의 수를 다 계산하느라 시간 소모가 너무 커지는 문제가 있었다. 논문에선 data instance와 feature들의 수를 줄이기 위해 두가지 새로운 기법을 소개한다. 하나는 Gradient-based One-Side Sampling (GOSS)이고 나머지 하나는 Exclusive Feature Bundling (EFB)이다. GO..