개발 노트

BOJ 1238 파티 Java 풀이: 각 마을 -> 파티 목적지 에 드는 비용 + 파티 목적지 -> 각 마을 에 드는 비용 시작점을 파티 목적지로 설정하고 시작점에서부터 최소비용을 구하면 각 마을까지의 비용을 구할 수 있다. 하기 이미지의 파란색 글씨 중 1: 각 마을 -> 파티 목적지 2: 파티목적지 -> 각 마을 3: 1번마을->파티목적지까지의 연산. que.add(Node(To, Value)), 비용 Dist[], 방문여부 Visited[] 1번 마을 비용을 메인 Dist에 등록 4: 3번 마을-> 파티목적지까지의 연산. 5: 4번 마을-> 6: 파티목적지(2) -> 각 마을

BOJ 1197 최소 스패닝 트리 Java www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이: 여태껏 들었던 비용보다 적게 들 경우 그걸로 갱신해야한다.

BOJ 1920 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이: 세그먼트 트리, 이진탐색 모두 이용 가능 다만 데이터 수정이나 탐색해야하는 수의 범위가 없기 때문에 수 배열을 한 번만 정렬하면 계속 탐색 가능하므로 비교적 간단한 이진탐색 사용

BOJ 11404 플로이드 백준 11404 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이: 모든 도시를 탐색하며 최단 경로를 구해야함 A-B, A-C-B 케이스 모두 고려 필요

BOJ 2042 구간 합 구하기 java 백준 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이: 값도 계속 변경되고 구간도 계속 변경되므로 세그먼트 트리 사용. 입력값의 범위가 크므로 반드시 long 타입 사용 long 타입으로 파싱하는 부분 주의! (Long.parseLong(st.nextToken())) 트리 초기화 첫번째 값 변경

백준 10868번 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 풀이: 최소값을 구해야하는 범위가 계속 바뀌는 문제 미리 구간별 최소값을 구해놓는 세그먼트 트리 활용

문제 백준 2357번 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 풀이: 최소값과 최대값을 구해야하는 값의 범위가 계속 변함 세그먼트 트리를 이용하여 트리 구성 시 미리 최대값과 최소값을 구해두고 요구하는 범위에서 뽑아 쓰는 방식

정올 1809 탑 www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1082&sca=3020 JUNGOL www.jungol.co.kr 백준 2493 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 접근법: 이중 포문으로 풀 경우 타임아웃이 발생한다. 따라서 입력과 동시에 계산하는 방법으로 소요시간을 줄여야하며, 마지막에 사용한 값을 다시 사용할 수 있는 Stack이 효과적이다.

알고리즘 문제 해결 시 빠른 입출력을 위해 사용 BufferedReader 를 초기화할 때 Reader에 InputStreamReader 를 사용할 경우 프롬프트에서 키보드로 입력한 값을 받아들이게 됨 Reader에 FileReader 를 사용할 경우 지정된 파일을 읽어들이게 됨. 경로를 입력하면 해당 경로의 파일을, 파일명만 입력하면 상대경로를 사용하여 프로젝트\파일명 의 파일을 읽어들임 BufferedWriter 는 write를 통해 출력할 내용을 받아들이고, close를 호출할 때 프롬프트에 한 번에 출력하는 방식. static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 값 입력 br.readLine();/..

FILO(First In Last Out) 특징을 가지는 자료구조 마지막에 입력한 값을 사용할 빈도가 높은 경우 사용하기에 유용. 몇가지 자주 사용하는 메소드 정리 Stack stack = new Stack(); stack.add(0);// 값 추가 stack.peek();// 가장 먼저 나올 값 확인 stack.pop();// 값 꺼내기 stack.isEmpty();// stack 이 비어있는지 확인 stack.size();// stack 에 있는 값의 개수 확인