Blog Posts

Home /
Blog Posts

DTO에 대하여

Spring
2021년 4월 15일

Spring boot 공부하면서 DTO의 개념과 깔끔하게 관리하는 방법등 생각하게 되는 데 다른사람들의 의견도 듣고싶고 방법을 기록하기 위해 글을 작성한다. 1. 변환 수행 계층 Controller Service Repository 데이터의 전달을 수행하는 Controller단이 가장 일반적이고 적합하다고 생각이 들지만, 다른사람들의 글을 보면 Service나 Repository에서 수행하는 것을 보기도 했다.수정사항이 별로 없는 기능에 대해서는 Repository에서 바로 Dto를 이용한다면 별도의 Mapping이 필요없고 간단하다는 글을 어디서 봤는데 이는 계층의 영역을 침범하는 것 같고 수정사항이 생기면 수정이 힘들것 같다....

Intellij 시작시 바로 꺼지는 Error

Error
2021년 4월 15일

윈도우로 작업을 위해 IDE를 실행시켜보면 아래와 같은 에러가 발생하며 IntelliJ뿐만 아니라 Jetbrain사의 모든 IDE들이 실행이 안되는데 매번 어떻게 해결했더라 기억을 되짚고 그때마다 여러 글을 뒤져보는게 힘들어 기록을 위해 작성한다. 원래 해결했던 방법으로는 config 파일을 삭제하고 재실행하면 됐는데 여전히 실행이 안돼서 IDE를 삭제했다가 재실행을 수행했다. 하지만 삭제했다 다시 깔아도 문제가 해결되지 않아 c://user/사용자이름/AppData/Roaming/JetBrains 안에 있는 모든 설정파일도 삭제했다가 재설치를 진행했으나 결과는 똑같았다....

[APSP] Floyd Warshall 알고리즘

Algorithm
2021년 4월 12일

벨만-포드 알고리즘과 다익스트라 알고리즘과 달리 모든 최단 경로를 구하는 알고리즘이다. (물론 두 알고리즘도 모든 정점에대해 수행하면 모든 최단 경로를 구할 수 있다.) 1. 특징 음의 가중치 허용 optimal substructure 개념 이용 배열을 이용하여 구현 밀집그래프에서 모든 edge간 경로 구할때 적합 2. Pesudo Code 3. 구현 방법 그래프 edge가 주어졌을때, edge들의 정보를 이용하여 각 edge간 거리 정보를 저장할 distance 2차원 행렬과 경로를 구하기 위해 이전 노드를 저장할 previous 2차원 행렬 생성 distance 행렬은 Infinity로 previous 행렬은 NIL(-1)로 초기화 그래프 G의 edge들의 가중치의 정보를 이용해 distance행렬을 초기화하고 자기의 거리는 0으로 초기화 3중 반복문을 이용하여, 현재까지 계산된 i - j까지의 경로 값보다 사이에 k를 경유하는 경로 값이 더 작다면 값을 바꾸기 4. 시간복잡도 매번 모든 노드들의 조합에 대해서 현재까지의 최단 경로를 구하고 총 |V-1| 번 반복하기 때문에 O(|V|^3) 의 시간복잡도를 갖는다....

[MST] Prim 알고리즘

Algorithm
2021년 4월 12일

우선순위 큐의 방법을 이용하는 알고리즘으로 vertex를 한개씩 선택하며 최소 비용의 edge를 찾는 방법이다. decrease-key의 개념을 이용하며 decrease-key는 현재 계산된 v노드까지의 거리보다 현재 노드 u부터 v까지의 경로가 더 작다면 값을 갱신해주는 방법을 이용한다. 1. 특징 정점 선택 기반 시작 정점부터 출발하여 해당 노드까지의 최소 비용을 기록하는 배열을 이용하여 구하는 방식 자료구조중 하나인 우선순위 큐를 이용하며, 우선순위 큐를 어떻게 구현했는가가 시간복잡도에 영향 2. Pesudo Code 3. 구현 방법 vertex들의 key값을 Infinity로 초기화 start vertex의 key값을 0으로 초기화 (어떤 vertex를 선택하더라고 MST가 나온다.) 현재 vertex에 인접한 vertex들 중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex을 찾기 (exract-min = 최소값 추출) 현재 vertex를 선택 인접한 vertex중 vertex의 key값보다 간선의 가중치가 더 작다면 key값을 가중치로 갱신 (decrease -key) 인접한 vertex중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex를 기준으로 3번부터 다시 반복 모든 vertex가 선택되었다면 종료 1) 인접 행렬 위에 설명한 3번 방법의 extract-min을 아래와 같이 배열로 구현하며, 매번 V회 반복한다....

[Disjoint Set] Union Find 알고리즘

Algorithm
2021년 4월 12일

1. Disjoint Set 번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set)으로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합이다. 2. Union-Find Union : 두개의 집합을 하나의 집합으로 합치는 것. Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것. 집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단할때 각 집합의 대표값(root)을 이용해서 집합이 같은지를 비교....

[MST] Kruskal 알고리즘

Algorithm
2021년 4월 12일

그래프 중에서 MST (Minumum Spannig Tree) 를 찾는 알고리즘중에 하나로 Union-Find알고리즘을 이용하며, 간선 (edge)의 가중치(weight)를 오름차순으로 정렬하여 가중치가 사이클이 생기지 않는 낮은 간선을 먼저 선택하는 방법이다. 사이클의 여부를 확인할때 union-find 알고리즘을 이용하여 찾는 알고리즘이다. union find 알고리즘 설명 보기 1. 특징 탐욕적인 방법 (Greedy) 간선 선택 기반 알고리즘 간선 선택 단계에서 사이클을 포함하지 않고 최소 비용 간선을 선택 부분 트리집합을 병합하면서 하나의 트리로 확장 희소그래프에 적합 ( V > E ) 정렬 속도가 시간복잡도에 영향 2. Pesudo Code 3. 구현 Note...

[SPSP] Dijkstra 알고리즘

Algorithm
2021년 4월 12일

그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 우선순위 큐의 방법을 이용하는 알고리즘이다. 가장 최적의 vertex를 한개씩 선택하며 최단 경로를 찾는 방법으로 relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다 현재 노드 u까지의 경로와 u에서 v의 가중치 ( e(u,v) ) 가 더 작다면 값을 갱신해준다....

[SPSP] Bellman Ford 알고리즘

Algorithm
2021년 4월 12일

그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 음의 가중치도 계산 할수 있는 알고리즘이다. Vertex의 개수가 N개일 때, 한 vertex에서 다른 vertex까지 가는데 거치는 edge수는 최소 1개부터 최대 N-1번 거치게 된다. 이때, relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다 현재 노드 u까지의 경로와 u에서 v의 가중치 (e(u,v)) 가 더 작다면 값을 갱신해주는 것이다....

Topological Sort (위상 정렬)

Algorithm
2021년 4월 12일

조건 : 방향이 있고 사이클이 없는 그래프 (Directed Acyclic Graph) DAG일때, 방향성을 거스르지 않고 나열하는 것으로 순서가 있는 작업을 차례로 수행해야할때 순서를 결정해주기 위해 사용하는 알고리즘이다. 대학 커리큘럼의 선수과목이나 엄무의 일정을 시간 순서대로 배치한것이 그 예 이다. 1. 특징 방향이 있는 그래프이어야 한다. (directed) 사이클이 없어야 한다. (Acyclic) 2. Pesudo Code 1) InDegree 이용방법 2) dfs 이용방법 3. 구현 방법 1) InDegree 이용 모든 vertex에 대해 InDegree값을 초기화 진입 차수 (indegree)가 0인 값을 큐에 삽입 큐에서 1개 vertex, v를 pop v를 stack에 쌓기 (정렬한 값을 담는 것이 stack) v에 연결된 vertex들의 indegree값을 1감소 진입 차수가 0인 정점들을 큐에 삽입 3-6번을 Vertex수만큼 반복 만약에 큐가 비어있다면, 사이클이 존재하는 그래프 (큐가 비어있다면 indegree가 0인 값이 없었다는 소리. 즉, 사이클 발생) 2) dfs 이용 방문하지 않은 vertex들을 dfs함수 진행. dfs 해당 vertex 방문표시 인접 vertex에 대해 방문하지 않았다면 dfs함수 진행 dfs함수 종료시 stack에 push 4. 시간 복잡도 indegree방법은 초기화하는데 O(V), 큐에 삽입, 제거 하는게 O(V)번씩 소요되며, indegree를 1감소 시켜주는게 O(E)번 일어난다. (indegree를 1감소해주는건 edge를 삭제해주는거와 같기 때문) 따라서, O(V+E)의 시간복잡도를 갖는다....

인증된 사용자 정보 조회

Spring
2021년 4월 11일

Spring Security의 Filter들을 모두 거쳐 인증에 통과한 User가 특정 Controller에 도달했을 때, User의 정보가 필요할때가 있다. 이때, Url의 도메인으로 id를 표시하거나 param/body로 계속 전달하기도 무리이며, Filter를 통한 인증시에 이미 한번 유저 정보를 조회하는 로직을 수행하게 된다. 그런데 한번더 select로 조회시 두번 조회하게 되는 비효율적인 상황이 발생하기 때문에 Spring Security의 Context Holder에 들어있는 인증 정보를 가져다 사용하면 Filter에서 인증을 수행한 User의 정보(Details)에 접근할 수 있다....