매일 조금씩

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 Bellman-Ford 알고리즘이란? 최단 경로를 구하는 알고리즘 중에 하나이다. PS에 자주 사용되는 최단 경로 알고리즘으로 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있다. 벨만 포드 알고리즘의 특징은 간선의 가중치에 음수가 있을 때에도 최단 경로를 구할 수 있다는 점이다. 벨만 포드 알고리즘을 구현하는 단계는 아래..

문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 문제가 바로 이해하기가 힘든데, 교차로는 노드이고 도로는 간선으로 생각하면 된다. 문제의 핵심은 시작지점에서 목적지까지 최단 거리로 가는데 g-h 간선을 통과했다는 점이다. 따라서, s -> 목적지 까지의 최단 거리 == s -> g까지의 최단 거리 + g-h 도로의 가중치 + g -> 목적지의 최단거리 s -> 목적지 까지의 최단 거리 == s -> h까지의 최단 거리 + h-g..

문제 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 위상 정렬 알고리즘으로 풀 수 있다. 예시 1. 작년 순위 정보를 저장한다. 작년 순위 5 -> 4 -> 3 -> 2 -> 1 인접 노드에 대한 정보를 담을 자료 구조를 생성한다. 나는 ArrayList[] adjs = new ArrayList[] 을 이용하였다. 이 때, 중요한 것은 해당 팀보다 순위가 낮은 모든 팀의 정보를 넣어야 한다. adjs[5] 에는 4, 3, 2, 1..

참고 https://www.baeldung.com/java-8-streams-introduction https://www.baeldung.com/java-8-streams Stream API란? JAVA8의 새로운 기능 Stream 기능에는 시퀀셜한 데이터를 처리하는 클래스들이 포함되어있음 Stream 생성 collection이나 array의 stream() Stream의 of() String[] arr = new String[]{"a", "b", "c"}; Stream stream = Arrays.stream(arr); stream = Stream.of("a", "b", "c"); Empty Stream Stream.empy()로 element가 없는 stream을 생성할 수 있다. Stream str..

문제 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCk 조합을 구한는 문제로 조합의 성질을 이용하여 재귀함수를 구현하여 풀 수 있다. (메모제이션 기법도 적용) nCn =1, nC0 = 1 nCk = n-1Ck-1 + n-1Ck 소스코드 package math; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ11051 { public static ..

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 서쪽의 N개의 다리가 있고 동쪽에 M개의 다리가 있다. 다리를 겹치지 않게 배치할 수 있는 경우의 수는, 강 동쪽에서 M개의 다리 중 N개의 다리를 순서 없이 선택하는 경우의 수와 동일하다. 메모제이션 기법과 조합의 성질로 해당 문제를 풀 수 있다. 알아야 할 조합의 성질 nCn = 1, nC0 = 1 nCm = n-1Cm-1 + n-1Cm https://ko.wikipedia.org/..

문제 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 풀이 구현 문제이다. name, referral, amount를 멤버로 가지는 Seller 클래스와 key:name, value:Seller를 가지는 HashMap을 구현하여 문제를 풀었다. 소스코드 import java.util.*; class Seller { String name; String referral; int amount; public S..

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 복습 차원에서 풀어 보았다. 이전에 작성한 코드와 비교해보니 구현 방법에서 약간 차이가 보인다. 해당 문제는 이분 탐색으로 가장 긴 증가하는 부분 수열의 길이를 구한 후, 인덱스를 이용한 역추적으로 수열의 값을 도출하여 문제를 풀 수 있다. 2021.11.04 - [Algorithm] - [Algorith..

문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색을 이용해 풀 수 있다. 예시 3 5 5 5 4 오영식이 이미 가지고 있는 랜선의 개수가 3개 5 5 4 내가 필요한 랜선의 개수는 5개이다. 이 조건이 충족될 때까지 이분 탐색을 진행한다. 초기 값 left = 1 right = 5 첫 번째 탐색 left = 1 right = 5 mid = 3 5, 5, 4 를 3으로 나눈 몫을 모두 더하면 랜선의..

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 이게 왜 정답률이 높은지 모르겠다. 막상 풀면 쉬운데 접근법을 생각하기가 쉽지 않다. 구글링을 통해 힌트를 얻어서 풀었다. 예제 설명 예제는 다음과 같다. N = 3, k = 7 3 7 3*3 배열에 각각 행과 열을 곱한 값이 입력되어 있다. 1 2 3 2 4 6 3 6 9 위 값들을 일렬로 쭉 나열 하면 아래와 같다. 1, 2, 3, 2, 4, 6, 3,..