코딩은 잼있어

최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(mst)란 ? N개의 정점으로 이루어진 무방향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리 최소 신장 트리란 무방향 가중치 그래프에서 사이클을 형성하지 않고 가중치의 합이 최소를 구하는 트리 알고리즘 대표적인 알고리즘으로 Prim 알고리즘, Kruskal 알고리즘, dijkstra알고리즘이 있다 0. 목차 Prim 알고리즘 Kruskal 알고리즘 dijkstra 알고리즘 1. Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택면서 MST를 만들어가는 방식 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 1,2과정을 반..

[프로그래머스] 지형이동 문제 https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 코드 이 문제는 최근에 풀었던 알고리즘 문제중에서 가장 어려웠던것같다. 우선 가장 처음에 문제에 접근할때 사다리 없이 이동 가능한 그룹끼리 그룹을 생성 현재 자리의 4방향을 탐색하면서 나와 다른 그룹을 경우 높이차를 측정 최소 높이차를 측정하여 결과를 구함 이 ..

3. 신경망 시작하기 이번 포스트는 신경망이 가장 많이 사용되는 세 종류 문제인 이진 분류, 다중 분류, 회귀에 배운 것들을 적용해봅시다. 3.1 신경망의 구조 신경망 훈련에는 다음 요소들이 관련되있습니다. 네트워크(또는 모델)를 구성하는 층 입력 데이터와 그에 상응하는 타깃 학습에 사용할 피드백 신호를 정의하는 손실함수 학습진행 방식을 결정하는 옵티마이저 아래는 4가지 요소들의 관계를 나타낸 그림입니다. 3.1.1 층 : 딥러닝의 구성단위 층은 대부분 가중치라는 층의 상태를 가집니다. 가중치는 경사하강법에 의해 학습되는 하나 이상의 텐서이며 여기에 네트워크가 학습한 지식이 담겨있습니다. 층마다 적절한 텐서 포멧과 데이터 처리 방식이 다릅니다. 2D 텐서(samples, features)가 저장된 벡터데..

2. 시작하기 전에: 신경망의 수학적 구성요소 2.1 신경망과의 첫 만남 딥러닝의 아주 기초적인 데이터셋인 MNIST를 사용한 예제를 풀어보겠다. MNIST는 딥러닝계의 "hello world"라고 생각될정도로 기초중의 기초 예제다 MNIST 데이터셋 : 6만개의 훈련 이미지와 1만개의 테스트 이미지로 구성 이번 예제의 경우 케라스를 완벽하게 이해하지 않아도 된다. 이번 예제는 케라스의 전체적인 구성과 코드의 흐름만 파악하도록 하자 # 2-1 케라스에서 MNIST 데이터셋 적제하기 from keras.datasets import mnist from keras.utils import to_categorical (train_images, train_labels),(test_images, test_labels..

[프로그래머스] 길찾기게임 문제 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 코드 이 문제를 풀기위해 class를 이용한 트리구조생성과 전위순회, 후위순회를 다시한번 공부할수있었습니다. 우선 해당 문제의 조건에 맞게 class를 이용한 이진 트리(Binary Tree) 를 구현 이진트리의 각각의 노드의 property는 x, y, left, right, index를 갖고있습니다. 만들어진 이진트리에서 전회순..

자물쇠와 열쇠 문제 https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 코드 이 문제는 2차원배열의 범위가 작기때문에 모든 경우를 탐색하면 풀수있다. 하지만 모든 경우를 탐색하는것도 생각보다 어려웠다. 길이가 N인 2차원 배열 lock을 (M -1) * 2 + N 의 배열로 늘려서 lock을 가운데에 넣고 key를 0, 0부터 90도씩 회전시켜나가면서 모든 위치를 확인하면서 풀었다. empty_lock 함수를 통해 자물쇠에서 비어있는 위치와 잠겨있는 위치를 찾아..

python을 활용한 웹 크롤링 최근 진행한 프로젝트에서 CNN 알고리즘을 활용한 이미지를 분류하는 기능을 구현했는데, 정작 모델을 학습시킬 이미지를 구하는게 참 어렵다는걸 깨달았다.. 단순 학습이라면 tensorflow에서 제공해주는 데이터셋을 이용하면 되지만, 내가 필요로 하는 이미지가 없다면 직접 만들어야하는데 이때 유용하게 쓰이는게 바로 웹 크롤링이다. 크롤링에 하기에 앞서 우선 웹 자동화를 하기 위한 chromedriver을 다운받은뒤 경로를 기억하고 있자. 1. 웹 띄우기 from selenium import webdriver # bing.com baseUrl = "https://www.bing.com/images/search?q=" baseUrl2 = "&form=HDRSC2&first=1&..

Trie 트라이는 문자열 비교를 위해 필수적인 알고리즘이다. 특히 특정 긴 문장에서 임의의 단어를 찾기위해 효율적으로 쓰이는 자료구조이다. 문자열 비교를 할때 이진검색트리의 경우 한 레벨당 한문자씩 저장되므로 문자열의 최대길이 M을 곱한 시간복잡도 O(MlogN)이지만, 트라이를 이용할경우 O(M)의 시간복잡도를 갖는다. 아래는 Trie의 동작과정을 나타낸다. chj, ckv, bq, ba의 문자열이 있다고 가정할때, 아래는 해당 문자열의 트리구조를 보여준다 Trie 코드 # 트라이 구조에 필요한 노드 class Node(object): def __init__(self, char, data=None): self.char = char self.data = data self.children = {} clas..

SQL 개념 및 문법 1. Database(DB) 기본 여러사람이 공유하여 사용할목적으로 체계화하여 통합, 관리하는 데이터의 집합 [1] RDBMS (Relational Database Management System) 데이터베이스는 체계화된 데이터의 모임(데이터베이스를 관리하는 시스템) 파일 단위의 저장도 가능=> 하지만, 데이터를 얼마나 "빠르고 효율적으로 그리고 중복없이" 찾을수 있는지가 관건 RDBMS(Relational Database Management System) 관계형 데이터베이스 관리시스템 관계를 표현하기 위해서 2차원 표(table) 활용 [2] 기본용어 스키마 DB의 자료의 구조와 제약조건을 기술한것 테이블 열과 행을 사용해 조작된 데이터들의 집합 열(column)/필드 특정 종류의..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 백준의 빙산 문제는 dfs나 bfs를 이용하여 풀수있는 문제다. 실제로 해당 개념을 활용하여 약 30분내로 문제를 다 풀었지만, 결과는 처참했다. 계속해서 런타임 or 시간초과가 뜨고 시간을 최대한 줄이기위해 재귀대신 반복문으로 사용하고, 가지치기를 하면서 시간을 줄이기 위해 노력했다. 하지만 4시간 가까이 수정했음에도 10번이 넘도록 시간초과가 뜬다..ㅠㅠ 혹시나 python3보다 더 빠른 pypy3로 돌려봤더니 단번에 성공하는걸보고 python과 p..