본문 바로가기

전체 글

 (124)
백준 15678번 연세워터파크 (JavaScript) 1번째 징검다리부터 N번째 징검다리를 순차적으로 확인하면서, 현재징검다리보다 d개 전까지의 징검다리중 최대 값과 현재의 징검다리의 값을 비교하여 최대값을 현재 징검다리 값으로 업데이트한다. d개전의 징검다리의 최대값을 그냥 구한다면 O(d)가 걸리겠지만, 세그먼트 트리를 구성하여 구한다면 O(log(d))가 된다. 따라서 이 문제를 O(nlog(n))으로 풀 수 있게 된다. 아래는 JavaScript 풀이 코드이다. const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = []; rl.on('line', function..
JavaScript Priority Queue 구현 JavaScript에는 Priority Queue가 없다. 참으로 슬프다. Priority Queue는 코딩테스트에서 자주 쓰이는 자료 구조이므로 직접 구현해보기로 했다. Priority Queue는 Heap이라는 자료구조를 바탕으로 구현이된다. 그래서 Heap의 구현과 Priority Queue를 따로 클래스를 만들어서 분리를 하는 것이 맞지만, 알고리즘 문제풀이를 위해서만 사용하므로 간단하게 둘을 합쳐서 구현하였다. Heap은 Binary트리의 일종으로 2가지 특징이 있다. 1. Root 노드는 가장 작거나 큰 노드가 오도록 저장이 되는 것이다. 이는 Comparator 구현에 따라서 다르며 원하는 값을 Root노드에 위치 시킬 수 있다. 2. 두번째는 Complete Binary Tree라는 것이다..
JavaScript Queue 구현 JavaScript로 Queue를 사용하기 위해 찾아다녔는데, Array의 Shift를 이용해 Array를 Queue처럼 사용할 수 있다는 사실을 알았다. Push와 Shift로 쉽게 큐를 만들어서 쓸 수도 있었지만, 시간복잡도가 내가 생각하는 Queue와 동일한지 살짝 의심이 되었다. 일반적으로 Queue는 Push와 Pop을 할 때 시간복잡도가 O(1)이 걸리게 된다. 보통 Linked List로 구현하기에 당연한 결과이다. 하지만, JavaScript로 push와 shift 연산이 동일하게 시간이 걸리는지 비교해보니 shift가 더 오래걸리는 것으로 확인이 되었다. 뭔가 수상하다...? let start = new Date(); let maxNum = 100000; let arr = []; for ..
LinkedHashMap 알아보기 HashMap은 Java에서 자주 사용하는 자료구조이다. 자료에 접근할 때 O(1)로 접근이 가능하여, 빈번하게 값을 찾아서 사용하는 경우 유용하게 사용할 수 있다. 다만, HashMap의 경우 저장된 값들을 순회하고자 할때 값을 넣은 순서가 아닌 무작위로 출력되게 된다. 이를 보완하고자 나온 것이 LinkedHashMap이다. LinkedHashMap은 doubly-linked list로 삽입한 값들을 관리한다. 그래서 삽입한 순서대로 값을 가져오고자할 때 사용할 수 있다. 아래는 LinkedHashMap과 HashMap에 들어간 값을 출력해보는 간단한 예제코드이다. public static void main(String[] args) throws Exception { LinkedHashMap link..
Servlet 이해하기 Servlet 이란 웹서버에서 안에서 클라이언트의 요청에 응답하는 자바 프로그램을 말한다. 우리는 서블릿을 만들기 위해 HttpServelt 클래스를 상속 받아서 만들게 되는데, 이는 Servelt Interface를 상속받아 만들어진 추상클래스이다. Servlet을 이해하기 위해서는 Servlet Interface가 어떻게 구성되어있는지 살펴보고, HttpServelt 추상 클래스에는 어떤 함수들이 구현되어있는지 살펴보면서 Servlet의 동작 과정을 이해해보려고 한다. 1. Servlet Inteface 주요함수 살펴보기 위 그림에서 볼 수 있듯이 Servlet에는 init, service, destory 세개의 함수가 정의 되어있다. 1)init public void init(ServletConfi..
Java String + 연산에 대한 이해 1. 자바에서 +연산으로 문자열 연결 Java String 클래스는 + 연산으로 쉽게 두개의 스트링을 잇는 것이 가능하다. public static void main(String[] args) throws Exception { String a = "Hello, "; String b = "World!"; a = a + b; System.out.println(a); // 출력결과 : Hello, World! } 정말 편리하게 사용하고 있는 기능이다. 그런데, String 은 불변 객체라고 알고 있기에, 내부적으로 어떻게 동작하는지 궁금해진다. 객체를 새로 만들어서 두개 스트링을 복사해서 붙여넣는 것일까? 그렇다면 이 과정은 비효율적이지는 않을까? 라고 생각해 볼 수 있다. eclispe나 vscode에서 브..
백준 11724번 연결 요소의 개수 (c++) 1부터 n까지 방문하지 않은 노드를 확인할 때마다, 해당 노드와 연결된 노드들 전부를 방문하고 정답에 +1을 해준다. 연결된 노드를 방문하는 방식은 BFS를 이용하면 된다. #include #include #include using namespace std; vector node[1010]; int visited[1010]; int main() { int n, m; cin >> n >> m; for (int i = 1; i > l >> r; node[l].push_back(r); node[r].push_back(l); } int answer = 0; for (int i = 1; i
백준 1764번 듣보잡 (c++) 듣도 못한 사람을 map에 저장한 뒤에, 보도 못한 사람을 해당 map에서 찾는다. map에서 결과가 있을 경우 이사람은 듣보잡이다. 이사람들을 모은 뒤에, 정렬하고 출력해주면 된다. #include #include #include #include #include using namespace std; unordered_map kiku; vector answer; int main() { int n, m; cin >> n >> m; string s; for (int i = 0; i > s; kiku.insert(make_pair(s, 0)); } unordered_map::iterator iter; for (int i = 0; i > s; iter..

티스토리툴바