분류 전체보기80

• 

  [백준][Java] 28118 - 안전한 건설 계획 1. 문제정보https://www.acmicpc.net/problem/28118난이도 : G4유형 : 분리 집합2. 문제풀이문제 조건 "서로 다른 두 기둥을 연결하는 빔이 항상 존재하도록 보강 작업을 진행할 수 있음이 보장된다."을 통해 a 작업은 발생할 수 없음을 알 수 있다.서로 빔으로 연결된 기둥들을 한 개의 기둥으로 변환하여 이렇게 변환된 기둥들을 서로 연결되도록 간선을 이어주면 된다.서로 이어진 기둥들의 집단 개수 - 1 = 간선 수(정답)3. 코드uion by rank 기법을 사용하였지만 기본 disjoint set을 사용해도 무방import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;im.. Algorithm, Problem Solving/백준(boj) 2024. 7. 17.

• 

  [백준][Java] 2288 - 격자의 분리자 1. 문제 정보https://www.acmicpc.net/problem/2288난이도 : G5유형 : BFS, DFS, DP시간 : O(S)2. 문제 풀이최단 경로를 찾기 위해 위아래로 연결되어 있는 S 집합의 좌우 폭을 넓혀야 한다.넓히는 이유는 S로 이루어진 길에서 탐색의 경로의 경우의 수를 늘려 최소 거리를 찾기 위함이다. 문제 조건을 보면 B는 S로 변경할 수 있다, 단 왼쪽에 S가 있는 B만 변경할 수 있다.즉 S와 B가 붙어 있는 경우에만 B를 S로 변경할 수 있다 입력된 문자열을 통해 테이블을 초기화할 때각 줄마다 처음 등장하는 B를  S로 바꾼다 결과적으로 기존의 테이블에서 변경된 테이블의  S의 모양은 오른쪽으로 1칸씩 확장된 모양이다.(단, 문제의 제약사항에 따라 테이블의 꼭짓점에는 S.. Algorithm, Problem Solving/백준(boj) 2024. 5. 1.

• 

  [프로그래머스][Java] 광고 삽입 1. 문제 정보 https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 : 3 유형 : 누적합 시간 : 선형 2. 문제 풀이 프로그래머스 문제답게 문자열로 주어진 입력값을 처리하는 게 번거롭다. 이 문제의 핵심은 누적합을 범위로 처리하는 것이다. logs 배열을 쿼리라고 생각하면서 각 구간마다 경계에서 증감 연산을 누적합 배열에 적용한다. (매 쿼리마다 시작 시간부터 끝나는 시간까지 직접 반복문을 돌면서 구간을 업데이트 하는 것은 비효율적이며,.. Algorithm, Problem Solving/프로그래머스 2024. 4. 23.

• 

  [백준][Java] 2852 - NBA 농구 1. 문제 정보 https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1 1팀 -> 2팀 일시 동점의 상황이 발생하지 않은 경우 코드를 보면 이해가 쉬울 것이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.StringTokenizer; public class Main { public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)).. Algorithm, Problem Solving/백준(boj) 2024. 4. 22.

• 

  [백준][Java] 31650 - Maximizing Productivity 1. 문제 정보 https://www.acmicpc.net/problem/31650 31650번: Maximizing Productivity For the first query, Bessie will visit the farms at time $t = [9, 7, 8, 8, 13]$, so she will only get to visit farm $4$ on time before FJ closes the farm. For the second query, Bessie will not be able to visit any of the farms on time. For the third query, www.acmicpc.net 난이도 : S4 유형 : 정렬, 이분탐색 시간 : O((N + Q)logN) 2. .. Algorithm, Problem Solving/백준(boj) 2024. 4. 20.

• 

  [백준][Java] 11997 - Load Balancing (Silver) 1. 문제 정보 https://www.acmicpc.net/problem/11997 11997번: Load Balancing (Silver) Farmer John's \(N\) cows are each standing at distinct locations \((x_1, y_1) \ldots (x_N, y_N)\) on his two-dimensional farm (\(1 \leq N \leq 1000\), and the \(x_i\)'s and \(y_i\)'s are positive odd integers of size at most \(1,000,000\)). FJ wants to par www.acmicpc.net 난이도 : G3 유형 : 좌표압축, 누적합 시간 : O(N^2) 2. 문제 풀이 x.. Algorithm, Problem Solving/백준(boj) 2024. 4. 16.

• 

  [백준][Java] 19951 - 태상이의 훈련소 생활 1. 문제 정보 https://www.acmicpc.net/problem/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 난이도 : G5 유형 : 누적합, 펜윅 트리, 세그먼트 트리 시간 : O((N + M)logN) 2. 풀이 업데이트 쿼리가 [2, 4] 일 시 "prefixSum[2] += 변화량, prefixSum[4 + 1] -= 변화량" 이 방식으로 처리하는 범위 누적합 기법을 사용하지 않고 펜윅 트리로 풀어 보았다. 웰노운 방식보다 느리지만 펜윅 트리로 범위 누적합 쿼리 문.. Algorithm, Problem Solving/백준(boj) 2024. 4. 14.

• 

  [백준][Java] 30088 - 공포의 면담 1. 문제 정보 https://www.acmicpc.net/problem/30088 30088번: 공포의 면담실 부서 $1$에는 $2$명의 직원이 있고 각 직원의 면담 소요 시간은 $5$분, $50$분이다. 부서 $2$에는 $2$명의 직원이 있고 각 직원의 면담 소요 시간은 $20$분, $10$분이다. 부서 $3$에는 $1$명의 직원이 있고 www.acmicpc.net 난이도 : S5 유형 : 정렬, 누적합, 그리디 시간 : O(NM + NMlongNM) (NM Algorithm, Problem Solving/백준(boj) 2024. 4. 14.

• 

  [백준][Java] 14170 - Counting Haybales 1. 문제 정보 https://www.acmicpc.net/problem/14170 14170번: Counting Haybales Farmer John has just arranged his N haybales (1≤N≤100,000) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer Q queries (1≤Q≤100,000), each asking for the www.acmicpc.net 난이도 : S3 유형 : 이분 탐색 시간 : O(QlogN), 정렬시간 제외 2. 문제 풀이 매우 기초적인 .. Algorithm, Problem Solving/백준(boj) 2024. 4. 4.

• 

  [SpringBoot] JDBC - Connection Pool을 미리 생성하여 초기 속도 개선 1. 문제 Connection Pool은 첫 번째 요청이 오기 전까지 생성되지 않는다. 애플리케이션이 시작 후 처음 받는 요청은 커넥션 풀이 생성되는 시간만큼 지연되어 클라이언트가 응답을 느려지게 된다. 2. 해결 방안 애플리케이션이 시작될 때 강제적으로 커넥션 풀을 미리 생성하여 문제를 해결 데이터베이스에 요청을 보내는 runner 메소드를 작성한 후 Bean으로 등록하면 된다. 애플리케이션이 실핼될 때 빈을 생성하는 과정에서 아래의 코드가 실행되며 커넥션 풀이 생성될 것이다. @Bean public ApplicationRunner runner(DataSource dataSource) { return args -> { // 데이터베이스에 요청을 보내어 미리 커넥션 풀을 생성 Connection conn.. spring 2024. 3. 31.

• 

  [백준][Java] 2631 - 줄세우기 1. 문제 정보 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 난이도 : G4 유형 : DP, LIS 시간 : O(N^2) 2. 문제 풀이 주어진 줄에서 가장 긴 증가하는 부분 수열을 찾아내면 된다. 가장 길게 증가하는 부분 수열을 제외한 나머지 원소들만 자리를 바꿔야 최소 값이 나오기 때문이다. 3 7 5 2 6 1 4 예시에서 주어진 줄을 보면 3 x 5 x 6 x x 부분 수열이 가장 길게 증가하는 수열이다. 이 부분 수열은 괜히 자리를 변경을.. Algorithm, Problem Solving/백준(boj) 2024. 3. 23.

• 

  [프로그래머스][Java] 다단계 칫솔 판매 1. 문제 정보 https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 : 레벨 3 유형 : DFS 2. 문제 풀이 이 문제에서 핵심적인 부분은 3개이다. 숫자가 아닌 문자열로 되어있는 인덱스 정보로 그래프 노드끼리 어떻게 연결시킬까? 그래프 탐색 시 종료 조건은? 판매 정보에 중복이 있을 수 있다. 1. 문자열 정보로 그래프 노드 매핑 굳이 문자열을 숫자로 따로 매핑하는 과정을 거치지 않아도 간단히 그래프를 그릴 수 있다. 해쉬맵을 이용하여 .. Algorithm, Problem Solving/프로그래머스 2024. 3. 22.