의식이 흐르는대로 해보는 프로그래밍

접근 대표적인 0-1 BFS 문제. 또는 다익스트라로 해결할 수 있다. 0-1 BFS 문제 노드간의 간선이 0 또는 1인 그래프를 탐색하기 위해 사용하는 BFS 문제. 일반적인 BFS문제와 큰 차이점은 없지만, 간선의 가중치가 0이 존재하기 때문에, 일반 BFS로 풀면 최단거리가 보장이 되지 않을 수 있는 문제가 발생. 위와 같은 0-1 BFS의 예시로 느낌이 올 수도 있겠지만, 최단거리를 보장하기 위해서 BFS를 살짝 변형한 것이다. 해결 우리가 사용하는 일반적인 BFS를 의사 코드로 작성해보겠다. Queue = [시작 노드] distance = [inf, inf, inf, ..., inf] # 거리를 무한대로 초기화 해두면, 방문 체크를 위한 리스트 대신 사용 가능 distnace[시작 노드] = 0..

접근 문제 그대로 평범한 배낭 문제다. D.P.를 이용한 Knasack알고리즘을 사용해서 해결할 수 있다. (여담이지만, 올리고 있는 글순서를 보면 알겠지만 솔브닥 클래스 클리어중인데, 이 문제 2년전쯤 그리디 공부할 때 시도했다가 틀리고 안풀고있었던걸 이제 알았다.) (여담2이지만, 이번에 풀 때도 1초틀이었는데, 2년전에 시도했던 코드랑 구조가 똑같았다. 난 발전이 없는것인가...? 하지만 이번엔 해결했다. 내가 틀린 반례도 적어두겠다.) 해결 Knapsack 알고리즘을 사용하지 않고, 전체 탐색으로 해결 자체는 가능하다. 당연히 시간초과가 나겠지만. 그러니까 배낭문제는 그냥 배낭으로 풀자.. 변수는 아래와 같다. $ N $ : 물건의 갯수 $ K $ : 버틸 수 있는 최대 무게 dp Table은 $..

구간 합에 대해서 처음이라면, 이 문제를 봤을 때 아이디어가 바로 안떠오를 수 있다. 그렇다면, 아래 문제로 1차원단위의 구간 합을 먼저 이해해보고오자. https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 접근 구간 합 문제는 일반적으로, 누적 합을 저장해두고 구해야되는 구간의 값들을 빼서 구하는 방식으로 해결한다. 해당 문제도 똑같이 해결하면 되지만 2차원임으로 중복되는 부분을 조심해서 해결해야한다. 구해야하는 케이스에 대..

접근 피보나치 수를 구하는 문제이다. 하지만 범위가 괴랄한.. $ n

저작권 때문에 어디까지 입력을 해도 괜찮을지 모르겠지만 최대한 추상적으로 서술해보겠다. 1. 약수에 관련한 정수론적 문제 같았다. 키워드는 익숙하지만, 효율적으로 구상할 생각을 못했다. 주어진 값들이 완전탐색을 통해서 구하는 것 같았지만, 그렇다기엔 테스트 케이스의 결과값이 엄청나게 크게 주어졌다.. 고민을 해봐야 할 주제 2. 너무 유명한 케이스의 문제가 나왔다. 하지만 그걸로 끝이 아닌, 한발짝 더 나아간 것을 문제로 냈다. D.P.를 이용하여 효율성 개선을 하고, 후에 조건에 맞게 구현했는데 자꾸만 시간초과가 나서 해결하지 못했다. 3. SQL문제는 너무 간단한 문제 4. JOIN을 이용한 조건 탐색 문제 --- 아직 재학생 신분이기에, 코딩 테스트를 경험해보고자 지원했는데 탈탈 털린 기분이다.. ..

안녕하세요. 오랜 기간동안 포스팅을 하지못하고, 이제서야 포스팅을 합니다. 군대에 다녀오느라 처리할 시간이 너무 부족했었습니다. 각설하고, 오늘은 저번의 포스팅인 TensorFlow가 아닌 PyTorch라는 패키지를 설치해보겠습니다. PyTorch란 무엇인가? PyTorch는 페이스북에서 만든 딥러닝 프레임워크입니다. TensorFlow는 구글에서 만든 딥러닝 프레임워크입니다. 자세한 내용은 다른 아티클을 참고하시면 좋을거 같고, 이 정도로만 알면될것같습니다. PyTorch는 자율주행전기자동차로 유명한 Tesla 사에서도 사용하고 있고, 여러 논문에서도 입지가 넓어지고 있습니다. 그렇기 때문에, Study용으로 이제 올릴 포스팅에는 PyTorch로 사용해보도록 하겠습니다. 간단한 conda 커맨드는 저번..

2018/12/18 - [딥러닝(Deep Learning)] - 1-1. 딥러닝 개발환경 구축 (Anaconda 3 설치, Pycharm) 저번 글에는 아나콘다를 설치하고, Pycharm을 설치해봤습니다. 이번 글에는 설치한 아나콘다에 TensorFlow 개발환경을 위한 가상환경을 구성하고, TensorFlow 설치 및 Github 연동을 위한 Git 프로그램을 설치하겠습니다. 아나콘다 가상 개발환경 구성 아나콘다를 정상적으로 설치했다면, 이런식으로 윈도우메뉴에 여러가지 프로그램이 설치되어야합니다. 혹시, Anaconda Prompt만 설치되고, 나머지가 깔리지 않으셨다면, 앞에 1-1에서 언급한 주의사항을 다시 한번 봐주시길 바랍니다. Anaconda Prompt 를 '우클릭' 하여 자세히 -> 관리자..

딥러닝을 공부하기 위해서 책을 사고, 아무것도 모르는 상태로 시작하면서, 공부와 동시에 나중에 내가 혹은 나같이 막무가내로 접근하는 사람들을 위해 남기는 글이다. 필요 사항 TensorFlow, Keras를 공부하기 위해서, 아무 생각없이 내가 관심있는 분야의 딥러닝 책을 사버렸기 때문에, 기반이 되는 책은 김문권 저 이다. 파이썬과 케라스를 이용한 딥러닝/강화학습 주식투자 국내도서 저자 : 김문권 출판 : 위키북스 2018.05.29 상세보기 일단 요구하는 프로그램으로써는 Pycharm : 파이썬 개발을 위해 필요한 IDE프로그램이다. 평소에 파이썬 공부를 위해 이미 설치되어있는 상황이었다. Anaconda3 : 파이썬 개발할 때 필요로 하는 여러가지의 Lib를 한번에 설치, 관리의 용이성 때문에 사용..