본문 바로가기

분류 전체보기180

[백준] 2343번 - 기타레슨 문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 입력 첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다. 사고의 흐름 우선 블루레이의 크기를 생각해본다. 늘 그랬듯이 하나씩 탐색해보는 완전탐색을 생각해보자. 강의의수는 최대 100,000개이고, 블루레이 갯수도 최대 10.. 2023. 12. 8.
[백준] 2729번 - 보석상자 문제 https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 사고의 흐름 색상 수의 범위가 1개에서 10^9개이다. (1) 완전 탐색 질투심을 알아야 하니 질투심을 기준으로 탐색을 해야 한다. 질투심을 1부터 10^9까지 하나씩 확인해보면서, 최솟값을 찾는다..? 시간복잡도로 인해서 시간초과가 날 것이다. 선형 탐색에 시간초과가 날 것 같으면 생각해야하는 방법은 이분 탐색이다. 이분탐색의 시간복잡도는 logN이므로.. (2) 이분탐색을 사용해서 최소의 .. 2023. 12. 8.
이분탐색 이분탐색이란 이분탐색은 어떤 경우의 수를 하기에는 조금 애매하거나 n이 무지막지하게 큰 경우 O(logN) 만에 처리해야 겠다는 생각이 들 경우 시도를 해보는 알고리즘이다. 정렬된 배열에 특정원소가 있는지를 확인하는 것을 logN만에 해결하는 알고리즘 정렬된 배열의 가운데를 살펴보고 찾고자 하는 원소가 그 안에 있는지를 확인한다. 만일 그 안에 있다면 멈춘다. 그 외에는 왼쪽에 있는지 오른쪽에 있는지를 판단하여 탐색을 진행한다. 할 때마다 절반으로 줄어들기 때문에 이 알고리즘의 복잡도는 logN이다. 예시문제 https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을.. 2023. 12. 7.
[백준] 2776번 - 암기왕 문제 https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 사고의 흐름 이중 포문으로 풀경우 : N x M 만해도 1000,000,000,000 시간초과가 날게 분명하다. 시간 복잡도를 줄일 수 있는 방법이 있을까..? 이분 탐색을 사용하자 이분 탐색을 사용하는 경우 MlogN이 되어 시간복잡도가 확 줄어든다. 풀이 코드 package 큰돌의터전알고리즘강의.three주차.암기왕; import java.io.BufferedReader; import java.. 2023. 12. 7.
[네트워크] HTTP 들어가기 앞서 이 글은 큰돌의 터전 님의 저서 「면접을 위한 CS 전공지식 노트」를 학습한 내용을 정리한 글입니다. 모든 출처는 해당 저서에 있습니다. HTTP는 앞서 설명한 전송 계층 위에 있는 애플리케이션 계층으로 웹 서비스 통신에 사용된다. HTTP/1.0부터 시작해서 발전을 거듭하여 지금은 HTTP/3이며 HTTP/1.0부터 HTTP/3까지 존재한다. HTTP/1.0 HTTP/1.0은 기본적으로 한 연결당 하나의 요청을 처리하도록 설계되었다. 이는 RTT(Round Trip Time) 증가를 불러오게 되었다. 서버로부터 파일을 가져올 때마다 TCP의 3-웨이 핸드셰이크를 계속 열어야 하기 때문에 RTT가 증가하는 단점이 있다. RTT 패킷이 목적지에 도달하고 나서 다시 출발지로 돌아오기까지 걸리는.. 2023. 12. 7.
엔티티 설계시 주의할점 엔티티에는 가급적 Setter를 사용하지 말라 Setter가 모두 열려있다면, 변경 포인트가 너무 많아서, 유지보수가 어렵다. 어디서 수정됬는지 알기가 어렵다. 모든 연관관계는 지연로딩으로 설정 즉시로딩(EAGER)은 예측이 어렵고, 어떤 SQL이 실행될지 추적하기가 어렵다. 특히 JPQL을 실행할 때 N+1 문제가 자주 발생한다. 실무에서 모든 연관관계는 지연로딩(LAZY)으로 설정해야 한다. 연관된 엔티티를 함께 DB에서 조회해야 하면, fetch join 또는 엔티티 그래프 기능을 사용한다. @XToOne(OneToOne, ManyToOne) 관계는 기본이 즉시로딩이므로 직접 지연로딩으로 설정해야 한다. 컬렉션은 필드에서 초기화하자 컬렉션은 필드에서 바로 초기화 하는 것이 안전하다. null 문제에.. 2023. 12. 6.
[백준] 14888번 - 연산자 끼워넣기 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 사고의 흐름 덧셈, 뺄셈, 곱셈, 나눗셈의 갯수를 재귀호출로 줄여나가면서 값을 계산해주자 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public .. 2023. 11. 30.
[백준] 1911 - 흙길 보수하기 https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net 메모하지 않고, 머리로만 문제를 풀기위해 사고하는 내 모습이 문제인거 같아, 앞으로 문제를 읽고, 바로 사고의 흐름을 적으려고 한다. 사고의 흐름 1 2023. 11. 30.
[백준] 15662 - 톱니바퀴 문제 https://www.acmicpc.net/problem/15662 15662번: 톱니바퀴 (2) 총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 혼자 못풀었다. 너무 어렵다. 알고리즘 내 사고 방식이 글러 먹은걸까? 진짜 내 힘으로 푸는 문제가 몇 안되는것같다. 짜증이난다. 풀이 접근법 12시 방향이 S인지 확인해야 하므로, 12시 방향에 어떠한 문자가 와있는지만 생각하면 된다. 즉 12시 방향에 현재 회전으로 인해 변화된 인덱스만 감지해주면 된다. 1. 회전하는 톱니의 포지션과 회전 방향을 입력받는다. 2. 회전하는 톱니.. 2023. 11. 29.

티스토리툴바