전체 글 썸네일형 리스트형 [백준] 7677 Fibonacci 피보나치수를 구하는 문제였다.다만 N의 최대가 1,000,000,000이라 예전에 dp로 풀었을 땐 시간초과가 났다.이산수학에서 행렬을 배우고 다시 보니 풀 수 있을 것 같아서 다시 풀어봤다.풀이행렬의 거듭제곱을 이용해야한다.다만, N번 곱한다면 시간복잡도가 O(N) 이기에 이문제는 풀 수 없다.분할정복을 이용한 거듭제곱 알고리즘을 사용해 O(logN)으로 풀 수 있다.분할정복을 이용한 거듭제곱N이 짝수 A^N = A^(N/2) * A^(N/2)N이 홀수 A^N = A^((N-1)/2) * A^((N-1)/2) * A2*2라 그냥 2차원배열로 만들까 생각도 했지만 이번기회에 벡터사용에 익숙해지면 좋을 것 같아 벡터를 사용했다.우선 행렬 matrix를 vector를 이용해 선언해주고typedef vecto.. 더보기 최소신장트리 MST: Prim's algorithm 프림알고리즘은 최소신장트리, MST(minimum spanning tree)를 찾는 알고리즘이다.최소신장트리 는 무향그래프의 모든 정점을 잇는 신장트리 중 그 가중치의 합이 최소인 그래프이다.알고리즘은 다음과 같다.(1) 시작할 정점을 선택한다. 아무 정점이나 선택해도 된다.(2) 선택한 정점에서 갈 수 있는 다른 정점 중 가장 가중치가 작은 정점을 선택해 잇는다.(3) 이어진 정점들에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 선택해 잇는다.(4) 모든 정점을 선택할 때 까지 (3)과정을 계속 반복이어진 정점이라고 표기했는데 선택한 정점이 최소신장트리에 포함되는 것이며,지금까지 선택한 모든 정점들에서 선택하지 않은 정점까지의 가중치가 가장 작은 것 을 선택하는 것이다.작은 것들만 선택하는 것에서.. 더보기 다익스트라 알고리즘 다익스트라 알고리즘은 하나의 정점 에서 다른 모든 정점으로 가는 최단 경로 탐색 알고리즘이다.알고리즘에 대한 자세한 설명은 건너뛰고 구현위주로 작성하겠다.벡터배열우선순위 큐C++로 다익스트라 구현하기 위해 위 3가지가 필요하다.우선 정점의 개수가 N개라고 가정을 하자.벡터는 다음과 같이 선언할 것이다. (1번 정점부터 N번 정점까지 저장해야하기에 N+1)vector> vertex[N+1];vertex[i] : i번 정점vertex[i]의 원소 :pair( i에서 갈 수 있는 다른 정점 , 그 정점까지의 가중치 )예를 들어 다음 그래프에서 vertex[1]과 vertex[2]의 원소는 다음과 같다.방향성이 없는 그래프이므로 서로에 대한 정보를 가진다.vertex[1][0] = (2,3)vertex[2][0.. 더보기 스프링 JWT(1): 프로젝트 생성 이번에는 JWT를 위해 엔티티, 시큐리티 설정 등을 해보려고 한다. 프로젝트 생성우선 의존성은 다음과 같다.Spring WebData JPALombokSpring SecurityMySQL DriverMySQL 연동을 위해 다음과 같이 설정해주자.spring.application.name=jwt_practicespring.datasource.url=jdbc:mysql://127.0.0.1:3306/{db이름}?useSSL=false&useUnicode=true&serverTimezone=Asia/Seoul&allowPublicKeyRetrieval=truespring.jpa.properties.hibernate.dialect= org.hibernate.dialect.MySQLDialect# DB usern.. 더보기 이전 1 2 3 다음
