java

[백준] 1644 - 소수의 연속합 (자바 Java)

[Gold III] 소수의 연속합 - 1644 문제 링크 성능 요약 메모리: 32812 KB, 시간: 176 ms 분류 수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve), 두 포인터(two_pointer) 문제 설명 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에..

[백준] 1806 - 부분합 (자바 Java)

[Gold IV] 부분합 - 1806 문제 링크 성능 요약 메모리: 22944 KB, 시간: 220 ms 분류 누적 합(prefix_sum), 두 포인터(two_pointer) 문제 설명 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면..

[백준] 1987 - 알파벳 (자바 Java)

[Gold IV] 알파벳 - 1987 문제 링크 성능 요약 메모리: 12936 KB, 시간: 996 ms 분류 백트래킹(backtracking), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로..

[백준] 17143 - 낚시왕 (자바 Java)

[Gold II] 낚시왕 - 17143 문제 링크 성능 요약 메모리: 58532 KB, 시간: 792 ms 분류 구현(implementation), 시뮬레이션(simulation) 문제 설명 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕..

[백준] 12015 - 가장 긴 증가하는 부분 수열 2 (자바 Java)

[Gold II] 가장 긴 증가하는 부분 수열 2 - 12015 문제 링크 성능 요약 메모리: 322700 KB, 시간: 1716 ms 분류 이분 탐색(binary_search), 가장 긴 증가하는 부분 수열: O(n log n)(lis) 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) 출력 첫째 줄에..

[백준] 1520 - 내리막 길 (자바 Java)

[Gold III] 내리막 길 - 1520 문제 링크 성능 요약 메모리: 198548 KB, 시간: 928 ms 분류 깊이 우선 탐색(dfs), 다이나믹 프로그래밍(dp), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 ..

[백준] 11066 - 파일 합치기 (자바 Java)

[Gold III] 파일 합치기 - 11066 문제 링크 성능 요약 메모리: 29556 KB, 시간: 872 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성..

[Spring] 스프링 핵심 원리 기본편 - 4. 스프링 컨테이너와 빈

4. 스프링 컨테이너와 빈 ApplicationContext applicationContext = new AnnotationConfigApplicationContext(AppConfig.class); ApplicationContext : 스프링 컨테이너, 인터페이스 스프링 컨테이너를 생성할 때는 구성 정보를 지정해주어야 한다 @Bean 이 붙은 애들을 하나씩 호출 → 메서드 이름을 빈 이름으로, 반환하는 객체를 빈 객체로 등록 빈 이름은 항상 다른 이름을 부여 스프링 빈 의존관계 설정 설정 정보(AppcConfig)를 참고해서 의존관계 주입 스프링은 빈을 생성하고 의존관계를 주입하는 단계가 나누어져 있음 → 자바 코드로 스프링 빈을 등록하면 생성자를 호출하면서 의존관계 주입도 한꺼번에 처리 컨테이너에 등..

[백준] 7579 - 앱 (자바 Java)

[Gold III] 앱 - 7579 문제 링크 성능 요약 메모리: 17628 KB, 시간: 156 ms 분류 다이나믹 프로그래밍(dp), 배낭 문제(knapsack) 문제 설명 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라..

[백준] 17244 - 아맞다우산 (자바 Java)

[Gold II] 아맞다우산 - 17244 문제 링크 성능 요약 메모리: 99772 KB, 시간: 360 ms 분류 너비 우선 탐색(bfs), 비트마스킹(bitmask), 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, ..