Mhwan
-
[알고리즘/플로이드] 플로이드-와샬(Floyd-Warshall) 알고리즘Mhwan's Study/Algorithms 2021. 2. 12. 03:49
플로이드 와샬 알고리즘은 다익스트라, 벨만포드 알고리즘과는 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍 기법을 사용한 알고리즘으로 O(V^3)이라는 시간복잡도가 필요하며, 다익스트라 알고리즘을 모든 정점 V만큼 반복한 것보다 더 빠릅니다. 또한 음의 가중치 간선은 존재할 수 있으나 음의 가중치 사이클은 없다고 가정합니다. # 경유점 경유점이라는 개념은 플로이드 와샬 알고리즘의 핵심입니다. 어떤 경로든 최단 경로사이의 경유지가 존재할 것입니다. 위 그래프를 가정하면 1->2를 가는 최단 경로는 (1->3->4->2)가 되고, 3, 4는 1->2사이의 경로에 존재하는 경유점이 됩니다. 즉, u->v로 가는 최단 경로가 있다면 이것은 크게 두가지로 나뉠겁니다. 1. 경로..
-
[Develop&Design] 'PICA' 안드로이드 App & ServerMhwan's Develope/Android App 2021. 2. 2. 00:43
[미출시 어플리케이션입니다.] ## 기능 - 나만의 추억을 간직하고 있는 사진을 모아 앨범으로 만들어 볼 수 있고, 이 앨범을 친구들과 공유하는 SNS 서비스 - 사진 필터 및 편집 기능, 사진에는 위치 데이터, 태그, 게시글과 같은 메타데이터를 함께 넣을 수 있음 - 인공지능을 통해 사용자의 앨범 중 '노을'과 같은 사진의 카테고리를 검색하면 관련된 사진을 함께 모아볼 수 있는 기능 ## 기간 및 역할 - 2020.01.06 ~ 2020.11.24 (일정 상 중간 딜레이로 인해 늦어짐, 실제 작업 기간은 약 5개월) - 전체 기획, 디자인, DB 구조 설계 및 SQL 쿼리 코딩, 안드로이드 앱, Spring 일부 개발, 인공지능을 활용한 검색 및 우선순위 평가 알고리즘 개발 ## 환경 및 API - J..
-
[알고리즘/벨만포드] 벨만-포드(Bellman-Ford) 알고리즘Mhwan's Study/Algorithms 2021. 1. 23. 03:12
벨만-포드 알고리즘은 이전에 한 다익스트라 알고리즘처럼 단일 시작점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 다익스트라와 달리 가중치가 음수인 간선을 포함하는 그래프에서 최단 경로를 정확히 구할 수 있고, 음수인 사이클을 판별해낼 수 있습니다. 다익스트라 알고리즘에 비해 시간복잡도가 좋지 않으므로, 음수인 간선을 갖는 그래프나 음수인 사이클을 판별할 때 사용하는 것이 좋습니다. # 완화 (Relaxation) 이 알고리즘의 가장 핵심이 되는 특성입니다. u에서 v까지의 최단거리 dis[v] cur.weight + nextNode.weight이 만족할 경우에만 우선순위 큐에 넣었습니다. 1 2 3 4 5 6 7 for (Node nextNode : graph.sparseList...
-
[JAVA/DataType & String] 데이터 타입과 String에 대해Mhwan's Study/JAVA & Kotlin 2021. 1. 21. 03:31
# Primitive Type VS Reference Type Primitive Type (원시형) : 자바의 기본적인 자료형으로 Stack 영역에 저장됩니다. - 정수형 : byte (1byte), short (2byte), int (4byte, 약 20억까지 표현가능), long (8byte) - 실수형 : float (4byte), double (8byte) - 논리형 : boolean (1byte) - 문자형 : char (2byte) Reference Type : 원시형을 제외한 모든 자료형, new키워드를 이용해 생성되는 데이터로, 모두 Heap 영역에 저장됩니다. (GC의 대상) # Wrapper class byte (Byte), short (Short), int (Integer), long..
-
[JAVA/Garbage Collection] 가비지 컬렉션에 관하여Mhwan's Study/JAVA & Kotlin 2021. 1. 21. 00:38
자바는 다른 언어와 달리 개발자가 직접 객체를 메모리에서 해제하지 않아도 됩니다. 바로 Garbage Collector가 있기 때문인데, GC는 힙 메모리 영역에 존재하는 객체를 메모리에서 삭제하는 역할을 합니다. # GC의 대상 1. 객체가 Null인 경우 2. 블럭 실행 종료 후, 블럭 안에서 생성된 객체 3. Null인 부모객체를 포함하는 자식 객체 현재 사용하지 않는 객체를 힙에서 지우는 것으로 가비지 컬렉션의 과정을 Mark And Sweep이라고 합니다. - Mark : JVM의 가비지 컬렉터가 스택에서 참조하고 있는 힙에 있는 영역을 모두 마킹합니다. 이 마킹 작업을 위해 현재 작업중인 모든 스레드를 중단(stop the world)하며, 이 때문에 System.gc()를 함부로 호출하면 안..
-
[JAVA/JVM & Compile] JVM과 컴파일Mhwan's Study/JAVA & Kotlin 2021. 1. 19. 02:23
JAVA는 OS에 독립적으로 실행되는 특징을 갖고 있다. 이는 JVM이 있기 때문에 가능한데, JVM은 자바 프로그램이 기기나 운영체제 상관없이 실행 될 수 있게 하며, 프로그램 메모리(스택, 힙 영역의 관리)를 관리하고 최적화한다. # JVM의 구성요소 Class Loader, Execution Engine, Runtime Data Area, Garbage Collector 여기서 Runtime Data Area (JVM의 메모리 영역 (메소드, 스택, 힙, PC 레지스터, 네이티브 메소드 스택)), Garbage Collector는 이후 더 자세히 적어보려고 한다. # 컴파일 과정 Java compiler가 소스코드를 컴파일해 바이트 코드(.class)로 변환한다. 바이트 코드는 JVM은 읽을 수 있..
-
[알고리즘/다익스트라] 다익스트라(Dijkstra) 알고리즘Mhwan's Study/Algorithms 2021. 1. 15. 04:10
그래프를 탐색하는 알고리즘에는 대표적으로 DFS, BFS가 있고 이들은 모두 간선을 이용할때 가중치가 없는 경우이다. 특히 BFS의 경우 가중치가 없는 경우 최단경로를 구할때 사용하지만 노드 사이의 간선을 이용할 때 가중치가 있는 그래프가 있고, 시작점으로 부터 목적지까지의 최소한의 가중치 비용을 갖는 최단 경로를 계산해야할 때는 다익스트라 알고리즘, 플로이드-와샬 알고리즘, 벨만-포드 알고리즘을 사용해야합니다. 오늘부터 이 세개의 알고리즘을 공부하며 포스팅 할 계획으로, 다익스트라 알고리즘부터 시작하겠습니다. 먼저, 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 거리를 구할 수 있습니다. 단, 간선의 비용은 음수이면 안됩니다. (음수의 간선일 경우 플로이드-와샬 알고리즘을 사용합니다..
-
[JAVA/Hash] JAVA의 HashMap과 충돌(Collision) 문제Mhwan's Study/JAVA & Kotlin 2021. 1. 9. 23:33
Hashmap이라는 자료구조를 java에서 내부적으로 어떻게 저장되는지, 해시 충돌과 관련된 내용입니다. # HashMap & HashTable 두 구조 모두 Hash를 사용해 Key, value 형태로 저장되는 자료구조입니다. - HashMap : JDK 2.0에서 부터 생긴 API로 현재까지 꾸준히 업데이트 되고 있습니다. - HashTable : JDK 1.0부터 있던 API로 현재는 자주 사용되지 않습니다. 가장 큰 차이로는 동기화(Synchronization)의 차이입니다. 먼저 HashMap의 경우 동기화를 지원하지 않기 때문에 멀티 쓰레드 환경에서 문제가 발생할 수 있습니다. HashTable의 경우 동기화를 지원해 멀티 쓰레드 환경에서 안전합니다. 하지만 현재 ConcurrentHashMa..