코딩못하는사람

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리가 검색을 할 때 자동으로 완성시켜주는 단어들을 보면 트라이가 사용된 예입니다. 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간복잡도를 갖고 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이의 형태 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"} 가 존재할 때 트라이의 예입니다. 다음과 같은 모양으로 트리를 만들어서 연산을 문자열의 길이만큼하는 시간복잡도를 갖게하는 것입니다. 이에 따라 트리의 특징은 시간이 O(M)..

Supervised Learning (지도학습) Linear Regression (예측) Binary Classification (이진 분류) Multi-label Classification (다중 분류) Linear Regression (선형 회귀분석) Cost function (Loss Function) 예측을 하는 값과 실제 결과 값의 차이를 나타내는 함수이다. 예측을 하는 데이터를 바꾸어가면서 실제 결과 값과 차이를 그래프로 나타낼 수 있다. 제일 적절한 예측을 하는 가설은 바로 cost function이 최소가 되는 가설일 것이다 경사 하강법 sklearn LinearRegression 사용법 from sklearn.linear_model import LinearRegression을 통하여 싸이..

1 NumPy 기본: 배열과 벡터 연산 Numpy 에서 제공하는 것 • 효율적인 다차원 배열인 ndarray는 빠른 배열 계산과 유연한 브로드캐스팅 기능 제공 • 반복문을 작성할 필요 없이 전체 데이터 배열을 빠르게 계산 할 수 있는 표준 수학함수 • 배열 데이터를 디스크에 쓰거나 읽을 수 있는 도구와 메모리에 적재된 파일을 다루는 도구 • 선형대수, 난수 생성기, 퓨리에 변환 기능 데이터 분석 에서 중요하게 생각하는 기능 • 벡터 배열 상에서 데이터 가공, 정제 , 부분집합, 필터링 변형 그리고 다른 여러 종류의 연산을 빠르게 수행 • 정렬, 유일 원소 찾기, 집한 연산 같은 일방적인 배열 처리 알고리즘 • 통계의 효과적인 표현과 데이터를 수집 요약하기 • 다양한 종류의 데이터를 병합하고 역끼 위한 데..

KMP 알고리즘이란? 우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다. 알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는 N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다. 하지만 KMP알고리즘은 O(N+M)정도로 줄여준다 KMP알고리즘에는 두가지 함수가 필요하다 전처리 테이블 KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다 접두사와 접미사 같을때의 최대길이를 저장해주는 것이다 코드로 구현하면 다음과 같다. KMP 함수구현 이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다 그림으로 보면 3번 인덱..

CCW ( Counterclockwise) 말 그대로 시계 반대 방향이다. 외적을 이용하여 유도할 수 있다. CCW알고리즘을 이용하여 세점의 방향성을 알 수 있다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 출처: https://jason9319.tistory.com/358 [ACM-ICPC 상 탈 사람] 각각의 점을 A(x1, y1) , B(x2, y2), C(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면, CCW 함수의 return값은 x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 이 된다.(신발끈 공식과 같다) RETURN값이 음수이면 시계방향. 양수이면 반시계방향. 0이면 세점이 평행하다. 이 알고리즘을 이용하여..

1.접근 N의 범위를 모르고 (1 ≤ N ≤ 100,000) 모든간선을 만드는 N^2으로 풀었다가 시간초과를 받았다. 그래서 NlogN으로 풀려고 정렬을 생각했다. 2.풀이 정점들이 주어진다고 해서 이전문제들 같이 모든 간선을 만들 수 없다. 근데 만들필요도 없다. 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이라고 했으므로 x,y,z축들의 값을 따로 따로 보면된다. 이 부분이 생각하기 힘들었는데 x,y,z축 좌표들을 각각 정렬해놓고 바로 앞,뒤 값들의 차이로 간선들을 만들고 힙에 넣으면 된다. 이렇게 되면 힙에서 빠져 나오는 값들은 비용의 최소값부터 나올 것이다. x,y,z축을 정렬해줄때 좌표의 값도 같이 넣어주어야 쉽다. 이후 유니온 파인드와 크루스칼 알고리즘을..

플로이드-와샬 알고리즘 다익스트라 알고리즘이 한 정점에서 모든 정점까지의 최단거리를 구해주는 알고리즘이라면 플로이드-와샬 알고리즘은 모든정점에서 모든정점으로의 최단거리를 구해주는 알고리즘이다. 다이나믹 프로그래밍을 기반으로 거쳐가는 정점을 기준으로 한다는 특징이 있다. 다익스트라와 다른점은 다익스트라는 힙을 이용하여 일차원 배열에 값을 나타냈으므로 입력을 받을 때 adj[시작점]=(가중치,목적지)를 받았다면 플로이드는 2차원배열 adj[시작점][목적지]=가중치로 저장한다는 차이가 있다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. 식으로 설명해보자면 현재의..

벨만-포드 알고리즘 다익스트라와 마찬가지로 SSP알고리즘인 벨만-포드 알고리즘은 음의 가중치를 다룰 수 있다. 그런데 다음과 같이 음의 가중치로 인해 순환 구조를 가진다면 최단경로를 구할 수 없다. 따라서 벨만-포드 알고리즘은 최단경로를 구하는 것과 이 그래프에서 최단경로를 구할 수 있는지 없는지를 판별하는 과정 두 과정으로 나눠진다. 벨만 포드 알고리즘은 V-1번 모든 간선을 Relax하는 작업을 수행한다. 최단경로구하기 동작과정은 각 정점들을 돌아 가면서 모든 간선들을 탐색한다, 단 맨 처음은 시작점부터 탐색한다( 처음 이후에는 순서 상관없음) D(s,v)=D(s,u)+w(u,v) 이 과정을 V-1번 탐색하는 이유는 s에서 v까지 가는 경우에서 v를 뺀 모든 경로가 각각 최단거리일 수 있기 때문이다(..

단일 출발지 최단 경로( Single Source Shortest Path ) 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것에는 두가지 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라와 벨만-포드의 차이는 음의 가중치를 다룰수 있냐 없냐의 차이이다.(벨만-포드가 가능) 다익스트라 알고리즘은 최소힙을 이용하여 구현할 수 있다. 우리가 알아볼 시작지점으로부터 다른 도착지점까지의 가중치 배열을 INF로 초기화한다.ans=[INF]*(v+1) 시작지점의 값을 0으로 초기화하고 heap에 (가중치,위치)을 넣어준다 while문을 사용하여 heappop을 통하여 최소값을 뽑아주고 뽑힌 (가중치+위치에 연결된 곳들의 가중치)로 연결된 곳들을 relax(경로가 더 효율적이면..

https://www.acmicpc.net/problem/13913 1.접근 bfs역추적을 방문했던곳인지 확인하는 check배열을 만들어 바로 전 값을 저장하도록 해서 추적하게 했다. 2.풀이 출발지점에서 도착지점까지 가는 +1,-1,*2의 3가지 뿌리로 bfs를 만들어준다. 여기서 방문했던 곳인지 확인하는 check 배열을 -1로 초기화 시킨다.bfs를 통하여 방문할때마다 cnt대신에 자신의 바로 전 위치를 집어 넣어주면 -1도 아니게 되고 어떤 경로로 현재 지점에 와있는지 알 수 있게된다. 따라서 큐에서 도착지점 값이 나올 때 cnt값을 반환하고 도착지점에서부터 시작지점까지 check배열을 순서대로 거꾸로 따라가보면 어느 경로로 왔는지 나온다.(마지막 while 문) 3.코드 4.배운점 처음에 che..