공부 기록
BOJ 1654 - 랜선 자르기
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 길이가 제각각인 K개의 랜선 (1
BOJ 2805 - 나무 자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net '최댓값'이라는 키워드 나왔으므로 이분 탐색 고려해보기. 원래 문제 원하는 길이 M만큼 얻을 수 있는 최대 절단기 높이는 얼마인가? 매개변수 설정 후 뒤집은 문제 정답인 절단기 높이를 매개변수 H로 설정 어떤 절단기 높이(H)로 잘랐을 때, 원하는 길이 M만큼을 얻을 수 있는가? Yes/No 문제로 변신 위의 Yes/No 문제를 한 번 물어보는 데 걸리는 시..
매개 변수 탐색 (Parametric Search)
Up-Down 게임 - A가 1~1000 사이 어떤 자연수를 선택 - B는 A에게 "생각한 숫자가 X 이상이야?" 라는 질문 가능 - A는 맞으면 1, 아니면 0 대답 - 최소 횟수로 질문하려면? 방법 1) Linear Search 1부터 1000까지 전부 물어보기 "생각한 숫자가 1 이상?" "생각한 숫자가 2 이상?" ... "생각한 숫자가 1000 이상?" -> 마지막 Yes인 대답이 정답! 최악의 경우 1000번 질문해야 한다. 더 빠른 방법은 없을까? 방법 2) Binary Search A가 생각한 숫자를 매개변수로 생각해서 이분탐색으로 찾기 L=1, R=1000인 구간 L~R에서 이분탐색! 탐색할 범위의 중앙 값과 찾아야 할 숫자 K를 비교를 통해 정답이 가능한 구간 [L, R]을 좁혀나가면서..
Blog 테이블 생성 - User
User 테이블 @Entity // 테이블화 시켜주기 @Data @NoArgsConstructor @AllArgsConstructor @Builder // 빌더 패턴 public class User { // 모든 테이블에는 private key가 있어야 한다. @Id // Primary key @GeneratedValue(strategy = GenerationType.IDENTITY) private int id; // 시퀀스, auto_increment // null이 될 수 없고 길이 제한 // username은 중복되지 않도록 @Column(nullable = false, length = 30, unique=true) private String username; // null이 될 수 없고 길이 제한..
BOJ 2470 - 두 용액
https://www.acmicpc.net/problem/2470 서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만드는 문제 아이디어 각 용액의 범위가 -10억 ~ 10억 이므로 두 용액을 합친 값의 범위는 -20억 ~ 20억이므로 int형 변수로 처리 가능하다. 가장 먼저 생각난 방법은 이중 for문으로 두 용액을 섞을 수 있는 모든 경우를 다 비교해보는 것이다. 이렇게 하면 시간 복잡도가 O(N^2)이 된다. 이러면 N의 최댓값이 10억이니까 100억이 되버리므로 시간이 초과된다. 왼쪽 용액(left)을 골랐을 때 오른쪽 용액을 뭘 골라야 더해서 0에 가장 가까울까를 생각해보면 정렬이 된 용액들 중 A[left]를 고른 후 A[left+1 ~ N] 범위 내에서 -A[left]와 가장 가까운 수..
yaml 설정
yaml 파일이란? yaml 설정 = 스프링 프로젝트 설정 스프링 프로젝트의 포트, DB 연결, 인코딩 등의 전반적인 설정을 yaml 파일에서 한다. 기존에는 xml이라는 파일에서 했는데 이젠 yaml(야물) 파일에 설정한다. yml 설정 root-context.xml : 보통 DB 설정. 한번만 객체 생성하고 더 이상 new할 필요 없이 싱글톤으로 관리되는 애들이 설정되는 곳이다. servlet-context.xml : 한번이 아닌 지속적으로 계속 new해서 사용해야 하는 애들이 설정되는 곳이다. 스프링에서는 application.yml 파일에 설정하기만 하면 돼서 위처럼 구분할 필요가 없다. application.yml : web.xml, root-context.xml, servlet-context...
Lombok 세팅
lombok 위치 프로젝트의 pom.xml을 들어가면 우리가 추가해둔 lombok이 있다. 경로 그대로 따라가보면 jar 파일이 있다. git bash를 열어서 jar 파일을 실행 후 STS 실행 파일에 설치해준다. 설치 후 다시 STS를 실행해보면 lombok을 사용할 수 있다. package com.cos.blog.test; import lombok.Data; import lombok.NoArgsConstructor; import lombok.RequiredArgsConstructor; // @Getter // @Setter @Data // @Getter + @Setter @AllArgsConstructor // 모든 필드 생성자 생성 // @RequiredArgsConstructor // final..
Maven
프로젝트 빌드 과정 각 프로젝트에 lib를 copy해서 빌드하는 경우 lib가 프로젝트마다 생성되어야 하는 문제가 있다. 그래서 프로젝트 외부인 C\lib와 같은 곳에 디폴트로 copy를 해두고 빌드할 때 이 곳에 연결하면 하나의 lib로 여러 프로젝트 빌드가 가능해진다. 이렇게 외부 폴더에 copy해서 빌드하면 하나의 파일로 여러 프로젝트를 빌드할 수 있는 장점이 있다. 대신 단점이 만약 배포를 해야할 때에는 따로 파일을 만들어줘야 해서 또 연결해줘야 하는 문제가 있다. 또한 다른 라이브러리를 다운받고 싶을 때 각 사이트별로 따로 다 다운을 받아야 해서 불편하다. ex) mysql, jsoup 등 각 공식 사이트에 가서 다운 일일히 받아줘야 함 Maven 역할 프로젝트의 pom.xml 파일을 읽고 중앙..
HTTP1.1 실습
POSTMAN 설치 HTTP1.1 어떤 데이터를 GET, POST, PUT, DELETE 요청할 것인지는 ? 뒤에 요청하는 데이터를 적어준다. stateless와 stateful stateless 방식은 클라이언트와 서버가 통신할 때 요청시 마다 스트림을 연결해서 Data를 응답하고 연결을 끊는 방식으로 서버 입장에서 부하가 굉장히 적어서 http에서 사용하고 있다. stateful 방식은 요청, 응답 후에도 지속적으로 연결되어서 Data를 주고 받는 채팅과 같은 통신에서 사용한다. 이 방식은 연결이 계속 지속되기 때문에 세션이 만들어진다. 세션이 만들어졌다는 것은 인증이 된 관계로 Data를 응답해줄 준비가 되었다는 뜻이다. 그래서 한 번 연결 후 계속 인증 없이 Data를 주고 받는 것이 가능하다. ..
[BOJ 7795] 먹을 것인가 먹힐 것인가
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 아이디어 A 원소의 크기가 B의 원소보다 작은 쌍을 구해야 한다. 먼저 순차 탐색을 생각해봤다. A의 모든 원소마다 B의 모든 원소를 비교하면 (1 ≤ N, M ≤ 20,000)이므로 시간 복잡도가 O(N^2) 즉, O(4*10^8) 이므로 1초 내에 풀 수 없다. 탐색 시간을 줄이기 위해 이분탐색을 이용한다. B를 정렬 후 A 원소들을 기준으로..