분류 전체보기 (47) 썸네일형 리스트형 펜윅 트리(fenwick tree) 펜윅 트리 바이너리 인덱스 트리(binary indexed tree)라고도 함 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있음 0이 아닌 마지막 비트를 찾는 법 : 특정 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서는 K & -K 계산하면 됨 트리 구조 만들기 : 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수 업데이트 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값 변경 (예시 = 3rd) 3번째 값이 변경되었다면, 3, 4, 8, 16이 3번째 인덱스에 대한 합 정보를 가지고 있는 인덱스이기 때문에 해당 인덱스들의 값을 업데이트 하면 됨 -> 시간 복잡도가 최악의 경우에도 O(logn)을 보장 1부터 N까지 누적합 구하기 : 0이 아닌 마지막 비트만큼 빼면서 구.. 탐욕법(Greedy) 탐욕법이란? 원하는 답을 재귀 호출처럼 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어감 모든 선택지 중 가장 좋은 답을 찾는 완전탐색/동적 계획법과 달리 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택 즉, 탐욕법은 지금의 선택이 앞으로 남은 선택에 어떤 영향을 미칠지 고려하지 않음 탐욕 알고리즘을 이용할 경우 알고리즘의 정당성을 증명하는 과정이 필요함 탐욕법이 적용되는 사례 탐욕법을 사용해도 항상 최적해를 구할 수 있을 경우 (동적 계획법보다 수행시간이 훨씬 빠름) 시간/공간적 제약으로 인해 다른 방법으로는 최적해를 찾기 어려울 경우(최적해 대신 근사해 찾는 것으로 타협) [예제] 회의실 예약 회사에 회의실이 하나밖에 없는데, n개의 팀이 각각 회의하고 싶은 시간을 제출했다... Quick DBD Home - QuickDBD Quick Database Diagrams (QuickDBD) is a simple online tool to quickly draw database diagrams by typing. www.quickdatabasediagrams.com Quick DBD란? Quick Database Diagram으로, ERD를 설계하는 툴이다. 블로그 후기를 작성할 경우, 무료료 1년의 free권한을 받을 수 있다. 작년에 데이터베이스 설계하는 프로젝트를 진행할때는 workbench의 ERD 툴을 사용했었는데, 해당 툴은 무료로 제공되지만 논리적 모델링을 지원하지 않기 때문에 설계에 있어서 살짝 어려움이 있었다. Quick DBD는 별도의 소프트웨어를 다운받을 필요 없이 아래와 같이 웹사.. 우선순위 큐 우선순위 큐 ADT (키, 원소) 쌍의 형태로 저장 예시 : 탑승 대기자(ex. 키: 예약 시간, 원소: 승객), 경매(ex. 키: 가격, 원소: 가격을 제시한 사람), 주식 시장 등 주요 메쏘드 insertItem(k, e) : 키 k인 원소 3를 큐에 삽입 element removeMin() : 큐로부터 최소 키를 가진 원소를 삭제하여 반환 일반 메쏘드 integer size() : 큐의 항목 수를 반환 boolean isEmpty() : 큐가 비어있는지 여부를 반환 접근 메쏘드 element minElement() : 큐에서 최소 키를 가진 원소 반환 element minKey() : 큐에서 최소 키를 반환 예외 emptyQueuException() : 비어있는 큐에 삭제/접근 시도할 경우 full.. [Unix] vi 에디터 사용하기 & Shell 명령 vi 에디터란? 최초의 유닉스용 화면 편집기 작고, 빠르고, 모든 유닉스/리눅스 시스템이 기본적으로 갖추고 있음 몇가지 기본적 기능만 갖추고 있으나 유닉스의 다른 명령들과 결합하여 매우 다양하게 확장/응용 가능 독특하지만 매우 빠르고 강력한 명령 체계 에디터 사용법 vi : 에디터 프로그램을 실행시작하라는 명령 vi myfile.c(파일이름) : myfile.c 파일을 만들어 vi 에디터프로그램 시작하는 명령 ▶ vi를 시작하면 기본적으로 들어가는게 명령 모드이기 때문에 편집모드로 변경해야함 ▶ (ex모드는 다른 파일을 읽어들일때, 편집을 마치고 파일을 저장할때 사용됨) vi 작성모드 이동 명령모드 → 편집모드 : 'i', 'a' 등의 명령 사용 ▶ i를 누르면 커서위치부터 수정, a를 누르면 커서위치의.. 표현 언어 EL 표현 언어란? 값을 표현하는 데 사용되는 스크립트 언어로 JSP의 기본 문법을 보완하는 역할을 함 제공 기능? JSP의 스코프에 맞는 속성 사용 집합 객체에 대한 접근 방법 제공 수치 연산, 관계 연산, 논리 연산자 제공 자바 클래스 메소드 호출 기능 제공 표현언어만의 기본 객체 제공 표현 방법? ${expr } 기본 객체? 데이터 타입? boolean : true/false 정수 : 0-9로 이루어져 있고, 음의 경우 -가 붙음 실수 : 0-9로 이루어져 있고, 소수점 사용 가능 및 3.24e3 처럼 지수형으로 표현 가능 문자열 : 따옴표로 둘러싼 문자열. 널 : null 객체 접근 규칙? ${.} 표현1이나 표현 2가 null이면 null을 반환한다. 표현1이 Map일 경우 표현2를 key로한 값을 .. Scope 4가지 scope Application : 하나의 어플리케이션이 생성되어 소멸될때까지 사용할 수 있는 scope Session : 세션 객체가 생성되어 소멸될때까지 사용할 수 있는 scope. 여러개의 요청이 들어와도 계속 남아있음 Request : 클라이언트가 요청하고 서버는 요청을 받아 응답을 보내는데, 이때 서버가 요청을 받아 어떤 일들을 수행한 다음 응답을 보낼때까지 계속 사용할 수 있는 scope Page : 선언된 Page 내에서만 사용 가능 Page scope PageContext 추상 클래스 사용 JSP페이지에서 pageContext라는 내장 객체로 사용 가능 forward가 될 경우 해당 Page scope에 지정된 변수는 사용 불가 (forward는 수행을 다음 페이지로 넘기는데 페이지.. [C++]백준 2630 색종이 만들기 문제 링크 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종.. 이전 1 2 3 4 5 6 다음
