반응형 Develop239 세그먼트 트리 개념과 구현 세그먼트 트리 = Segment Tree = Statisitc Tree 간격이 있는 숫자나 세그먼트에 대한 데이터를 저장하는데 사용하는 트리 구조 여러 데이터가 연속적으로 존재할 때, 특정 범위의 데이터 합을 구할 때 유용하다. 배열에 데이터가 아래와 같이 있다고 가정해보자. index 0 1 2 3 4 5 6 7 8 value 5 6 2 3 4 3 5 2 1 위 배열에서 인덱스 1부터 5까지의 합을 구하려면? index 0 1 2 3 4 5 6 7 8 value 5 6 2 3 4 3 5 2 1 위 범위의 데이터를 하나씩 더하는 방식을 사용하면 된다. (=선형적) 데이터가 N개면 시간복잡도가 O(N)이 된다. 이를 개선하기 위해서 세그먼트 트리를 이용한다면 시간복잡도를 줄일 수 있다. 위의 배열을 아래와.. 2021. 10. 22. Comparator와 Comparable 정리 백준 11650번을 풀다가 Comparator를 사용한 김에 개념 정리를 하려고 한다. 정말 간단한 문제니까 Comparator 재정의하는 연습용으로 괜찮은듯 ㅎ.ㅎ 🔻 문제 및 풀이 더보기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작.. 2021. 10. 21. [Thymeleaf] 타임리프란? (+기본적인 사용법) 간단한 CRUD를 구현하다가 org.thymeleaf.exceptions.TemplateProcessingException 에러를 너무 많이 겪어서 타임리프에 대해 잠깐 공부하기로 했다. (위 에러는 타임리프 문법을 잘못 쓰는 등의 이유로 특정 url을 찾지 못하거나 파싱 에러가 나는 경우에 자주 나는 에러이다.) Thymeleaf란? '템플릿 엔진'의 일종. html 태그에 속성을 추가해 페이지에 동적으로 값을 추가하거나 처리할 수 있다. 타임리프를 통해 속성을 대체할 수 있는데, 아래 예제를 살펴보자. input 태그는 th:value를 통해 item이라는 변수에 값이 존재하면 해당 값을 세팅해준다. 만약 item이 존재하지 않으면 value="test"를 통해 "test"라는 문자열을 세팅해준다. .. 2021. 10. 15. [Spring] HTTP 메시지 컨버터 HTTP 메시지 컨버터란? JSON 데이터를 HTTP 메시지 바디에서 직접 읽거나 쓰는 경우, HTTP 메시지 컨버터를 사용하면 매우 편리하다! HTTP 메시지 컨버터란, 요청 본문에서 메시지를 읽어들이거나(@RequestBody), 응답 본문에 메시지를 작성할 때(@ResponseBody) 사용하는 컨버터다. 🔻 포스팅을 보기 전, @ResponseBody를 다시 살펴보자. 더보기 웹 브라우저가 "localhost:8080/hello-api" 접근 서버를 거쳐 helloController 호출 helloController의 @ResponseBody를 통해 HttpMessageConverter가 호출 return 타입에 따라 JsonConverter 또는 StringConverter를 이용해 return.. 2021. 10. 10. 브라우저의 동작 원리 목차 1. Web browser 2. Render Engine 3. Parsing 3-1. Parsing-general 3-2. HTML Parser 3-3. CSS parsing 4. Render tree construction 5. Layout 6. Painting 7. Dynamic changes 1. Web Browser 웹 브라우저는 크롬, 익스플로러, 파이어폭스, 사파리, 오페라 등이 있다. 누구든지 인터넷만 있다면 언제 어디서나 이용할 수 있게 해준다. 내 데스크 톱이나 모바일 기기 등에 다른 웹으로부터 가져온 정보를 보여준다. HyperText Transfer Protocol (텍스트, 이미지, 비디오 등이 웹에서 어떤 방식으로 전송될지를 결정) 를 이용해 전송되는 이 정보는 전세계 어디서.. 2021. 10. 7. 페이스북이 멈췄다? (DNS와 BGP에 대해) 목차 1. 페이스북 네트워크 이슈 2. DNS의 개념과 작동 방식 3. BGP의 개념 1. 페이스북 네트워크 이슈 페이스북이랑 인스타가 먹통이라고? 오늘 새벽에 페이스북에서 운영하는 몇몇 서비스가 먹통됐다길래 궁금해서 찾아봤다. (페이스북 계열사의 모든 서비스가 중단됐던 모양이다. 페이스북, 인스타그램, 왓츠앱, ...) 많은 사람들이 DNS와 BGP에 대한 언급이 많았기 때문에 개념을 정리하기 위해 포스팅 한다. 페이스북이 먹통된 원인이 뭘까? 페이스북에서 공식적인 입장이 있지는 않았지만, Cloudflare 측에서 대규모 BGP 변경이 있었다는 트윗이 올라왔다. 이를 통해 BGP 설정 오류로 인해 네트워크가 통째로 내려갔다고 추측한다. 장애 5시간 반만에 BGP가 업데이트 되었고, 최소한의 서비스가 .. 2021. 10. 5. [Java] BufferedReader, BufferedWriter 프로그래머스 코테는 파라미터를 알아서 넘겨 받도록 되어있는데.. 백준은 직접 입력 받아야했다. Scanner와 sysout을 쓰다가 속도가 너무 느리게 나와서 BufferedReader/Writer에 대해 알아보려고 한다. 목차 1. BufferedReader 2. BufferedWriter 3. 주요 메소드 4. 예제 1. BufferedReader 문자 입력 스트림에서 텍스트를 효율적으로 읽을 수 있도록 문자를 버퍼링 엔터를 통해서만 입력받을 수 있어 ' ' 공백을 이용한 입력받기를 원한다면 StringTokenizer와 함께 사용 2. BufferedWriter System.out.println()을 대신해 사용하곤 한다. 3. 주요 메소드 메소드명 기능 BufferedReader(Reader rd.. 2021. 10. 4. 최적화 문제 - 완전 탐색, 동적 프로그래밍, 탐욕적 방법 목차 1. 최적화 문제 2. 완전 탐색 3. 동적 프로그래밍 3-1. 행렬 경로 3-2. 최장 공통 부분순서; LCS 3-3. 최장 증가 부분수열; LIS 4. 탐욕적 방법 4-1. 연속 배낭문제 4-2. 스케줄 짜기 문제 시작하기 앞서.. 해당 포스팅은 최적화 문제를 해결하는 방법 중, '완전 탐색, 동적 프로그래밍, 탐욕적 방법'에 대해 다룬다. 각 유형에 해당하는 몇 가지 문제를 예제로 보이며 언어는 Java를 이용한다. 대학생 때 공부한 것을 정리하는 차원에서 포스팅 하는거라 입문자에게는 어려운 내용일 수 있다😅 최적화 문제; Optimization problem 문제에 대한 하나 이상의 후보 해답이 존재하고, 각 후보 해답은 최적임을 판단할 근거가 되는 값을 가질 때, 이 들 중 최적값을 구하너.. 2021. 10. 3. [Oracle] SQL문으로 주말 구하기 🐱🐉 개요 날짜가 주어지면 이를 휴일인지 아닌지 구분해야 하는 문제를 겪었다. 공휴일은 보통 DB에 테이블을 따로 만들어서 관리하지만 주말은 굳이 그럴 필요 없이 SQL문으로 해결 가능하다. 🐱👤 주말 구하기 포인트는 주어진 날짜의 '요일'을 구하는 것이다. 해당 날짜의 요일을 구한 뒤, 토요일과 일요일인 경우만 조회하면 주말을 조회할 수 있다. Step 1 SELECT TO_CHAR(SYSDATE,'D') FROM DUAL; Step 1-1 : 날짜가 문자열 형태로 주어지는 경우 SELECT TO_CHAR(TO_DATE(:SEARCH_DATE),'D') FROM DUAL; Step 2 step 1의 쿼리문을 실행시키면 일요일부터 토요일까지 1 ... 7의 결과를 구할 수 있다. 이제 IN을 이용해 .. 2021. 8. 30. 이전 1 ··· 13 14 15 16 17 18 19 ··· 27 다음 반응형
