전체 글 썸네일형 리스트형 LCA(Lowest Common Ancestor) 최소 공통 조상 찾기 LCA란, 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드입니다. 트리의 특성상 싸이클이 없으므로, 두 정점 u와 v의 LCA를 w라 했을 때 u-w-v는 두 정점의 최단 경로라고도 할 수 있겠죠 :) LCA를 찾는 방법은 여러가지가 있는데, 세그먼트 트리를 사용하는 방법도 있지만, 저는 각 정점의 모든 정보들(깊이, 부모 정보, 부모의 부모 정보 등..)을 미리 저장해두고 LCA문제를 해결해보았습니다. 이렇게 하면 O(logN)만에 LCA를 찾을 수 있습니다. LCA를 가장 단순하고 쉽게 찾는 방법을 생각해보면, 모든 간선 정보를 저장한다. 각 정점의 깊이를 파악한다. (-> 완전 탐색 사용) 더 깊이가 깊은 정점에서 깊이가.. 더보기 node.js mongoDB 한국 시간 저장 mongoDB를 활용하여 서버를 구축하고 있는 중에, timestamp 변수로 현재 작성한 시간이 들어가야 합니다.구글링을 통해 Date.today() 를 활용하면 된다고 알아냈는데, 그 결과는 바로,, 다음과 같이 timestamp에 얼추 한국시간과 비슷한 다른 시간이 들어가게 되었습니다! 바로 mongoDB는 Date 형식으로 ISODate를 사용해서 생기는 문제입니다. 그렇다면 이를 해결하기 위해서는 한국시간을 넣어줘야겠쬬(?)!!해결방안은 두 가지가 있습니다. 첫 번째는 String으로 넣어주는 것과, 두 번째는 직접 ISODate에 들어갈 값을 한국 시간으로 포맷팅 해주는 것이죠 첫 번째 해결책은 다음과 같습니다 :) 1. npm Install moment2. npm install moment-.. 더보기 공공데이터 포털 OpenAPI 사용하기 - 미세먼지 개발을 위해서 미세먼지와 날씨정보 OpenAPI를 사용하였습니다. 이번 글에서는 미세먼지 OpenAPI 사용 방법에 대해 얘기하고자 합니다. 제가 사용한 미세먼지 데이터는 공공데이터 포털에서 대기오염통계서비스와 대기오염 정보 조회 서비스입니다. 전자는 주간 미세먼지 데이터를 위하여, 후자는 실시간 미세먼지 정보 데이터를 위하여 사용하였습니다. 1) 사용하고자 하는 API를 검색한다 2) 발급신청을 누른다. 3) 발급신청 순서를 진행한다.예시를 통하여 다른 OpenAPI 데이터를 신청하는 과정을 캡처하였습니다. 4) 미리보기를 통해 데이터 유형을 확인해본다.상세기능정보란에서 '미리보기 다운로드'를 실행하여 '▶미리보기' 버튼을 누르면 요청 데이터를 확인하실 수 있습니다. XML 형식으로 데이터가 주어진 것.. 더보기 JAVA HashMap 정리 HashMap이란 Key와 Value를 묶어 하나의 entry 로 저장한다는 특징을 갖고 있습니다. 그리고 hashing을 사용하기 때문에 많은 양의 데이터를 검색하는데 뛰어난 성능이 장점입니다. - Map 인터페이스의 한 종류로 (Key, value)로 이루어져 있습니다.- Key 값은 중복이 불가능하고, Value는 중복과 null값이 가능합니다. - 멀티쓰레드에서는 HashTable을 씁니다. HashMap 생성자/메소드 생성자/메소드 설명 HashMap() : HashMap객체 생성 ex) HashMap hm = new HashMap(); orMap map = new HashMap(); HashMap(int initialCapacity) : 지정된 값을 초기 용량으로 하는 HashMap객체 생성 .. 더보기 BFS 공부 BFS(너비 우선 탐색)은 깊이가 작은 노드부터 차례대로 방문하는 전체 탐색 방식이라고 말할 수 있다.보통 BFS는 큐로 많이 풀게 되는데, queue를 이용하여 문제를 푸는 순서는 다음과 같다. 1. queue의 가장 앞에 있는 노드 pop2. 현재 노드에 인접한 모드 노드 중 아직 방문하지 않은 노드를 queue에 push3. queue 가 비어있지 않으면, 1번부터 다시 실행 큐의 작동원리를 알고 계신다면, 깊이가 낮은 순서대로 탐색하는 것을 이해하실 수 있으실 겁니다 :) 위의 논리구조로 코드를 구현하게 된다면, queue에 방문 node offer();방문 배열[노드] = true;while(!queue.isEmpty()){v = q.poll();if(v와 인접한 노드 && 미방문 노드){que.. 더보기 java 자료구조 1. 스택import java.util.Stack; 사용법Stack stackname = new Stack(); 주 메소드 메소드 설명 boolean empty() 해당 스택이 비었으면 true, 그렇지 않으면 false E peek() 해당 스택의 제일 상단에 있는(제일 마지막 저장된) 요소를 반환함 E pop() 해당 스택의 제일 상단에 있는(제일 마지막 저장된) 요소를 반환함 + 해당 요소를 스택에서 제거함 E push() 해당 스택의 제일 상단에 전달된 요소를 삽입함. int search(Object) 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함.이 때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작 2. 큐import java.util... 더보기 JAVA input 처리(Scanner, String) 1. ScannernextInt() 사용 후, nextLine()을 사용하면 제대로 읽어들이지 않는 문제가 발생합니다. 그 이유는 nextInt() 메소드는 가장 마지막 개행 문자 '\n'까지 읽어들이지 않기 때문입니다. 따라서 그 개행문자는 다음에 호출된 nextLine()에서 읽어들이게 되어서 nextLine()에 아무것도 들어가지 않는(원하는 값이 들어가지 않는) 것이죠.이 문제를 해결하기 위해서 저는 2가지 방법을 사용하는데요, 1. 모두 nextLine()으로 읽어들인 후, 정수가 필요할 때 스트링안에서 처리를 해줍니다. 예를 들면 Integer.parseInt() 또는 {input}.charAt([index]) 같은 메소드를 사용하는 것이죠 2. 두번째로는 nextInt()이후에, [Scann.. 더보기 DFS(깊이 우선 탐색) 알고리즘 오늘 공부할 알고리즘은 깊이 우선 탐색, 흔히 DFS(Depth-First Search)로 알려져 있는 알고리즘이다. 이 알고리즘은 모든 노드를 방문하고자 하는 경우에 사용하게 된다. (cf. 맹목적 탐색(blind search)란, 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법)짧게 설명하자면 루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 1. 깊이 우선 탐색의 특징1. 자기 자신을 호출하는 순환 알고리즘의 .. 더보기 이전 1 ··· 4 5 6 7 8 9 10 11 다음
