Language/JAVA

7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 해당 문제는 놀랍게도 가장 긴 증가수열 알고리즘을 활용해서 풀어야 한다. 생각보다 어려워서 구글링 하여 다른 분들의 코드를 확인하여 해결할 수 있었다. 다른 분들의 코드가 현저히 짧은 것을 보고 상심이 매우 컸다. 7570 문제는 줄의 맨 앞이나 맨 뒤로만 어린이들을 보내서 줄을 세워야 한다. 그렇기 때문에 연속된 수들 중 가장 긴 증가수열의 길이를 구하고 n에서 구한 길이를 빼면 최소 횟수를 구할 수 있다.

문제에서 시작 도시 A, 도착 도시 B 그리고 버스를 타고 이동하는 데 걸리는 시간 C가 주어졌다. 여기서 중요한 부분은 이동하는 데 걸리는 시간 C가 음수인 경우도 있다는 점이다. 웬만한 그래프 문제를 풀었다면 이동 시간이 음수가 주어지면 떠올려하는 알고리즘은 하나밖에 존재하지 않는다. 벨만 포드 알고리즘 벨만 포드 알고리즘은 정점의 개수만큼 반복문을 돌려서 모든 간선들을 확인하여 노드 간의 최단 거리를 갱신하는 알고리즘이다. 여기서 음수 간선 순환이 발생하는지 체크하고 싶다면 정점의 개수만큼 반복문을 돌리면 된다. n번째 반복문을 돌리는데 최단 거리가 다시 갱신이 된다면 음의 사이클이 존재하는 것이다.

1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 크레인의 무게 제한과 박스의 무게를 "crain", "box" 이름으로 ArrayList로 담았다. 그리고 해당 ArrayList들을 모두 내림차순 정렬을 시켰다. ArrayList를 내림차순 정렬을 할 때는 Collection.reverseOrder() 함수를 sort안에 명시해주어야 한다. 정렬된 두 ArrayList의 첫 번째 인덱스 값을 비교한다. 만약 크레인의 첫 번째 값이 박스의 첫 번째 값보다 작을 경우 모든 박스를 담을 수 없기 때..

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net

17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 17845번 DP문제 중에 knapsack 문제로 해결해야 합니다. bag[M][N]을 1부터 M+1번째 과목들을 대상으로 최대 N시간을 써서 얻을 수 있는 가장 큰 중요도를 구해야 합니다. 현재 i번째 시간으로 들을 수 있을 경우 이전 과목을 들은 경우와 현재 i번째 시간 전 + 현재 i번째 우선도를 비교해서 최대 값으로 bag [i][j]를 갱신해줘야 합니다. 현재 i번째 시간으로 듣지 못할 경우는 이..

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해당 문제는 이분 탐색으로 해결했습니다. 주어진 N만큼 반복문을 시행합니다. arr의 맨 뒤 값보다 현재 주어진 값보다 작을 경우 arr의 맨 뒤에 해당 값으로 업데이트 해줍니다. 그 반대일 경우 이분 탐색으로 주어진 값의 인덱스를 찾아줍니다. 파이썬 풀이 [Python][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열 2 - 컴도리돌이 풀이 과정 해당 문제는 bisect 라이브러리를 사용해서 해결하였다. bisect에 대해서는 아래 링크를 참조하면 좋..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 해당 문제는 투 포인터 알고리즘으로 해결하였습니다. 두 용액의 합이 0과 가장 근사한 한 쌍을 찾아야 하는 문제입니다. 입력받은 용액의 배열을 정렬을 시키고 왼쪽 인덱스의 값과 오른쪽 인덱스의 값을 더해서 절댓값이 minValue보다 작으면 출력 값(ans1, ans2)과 minValue를 업데이트합니다. 만약 minValue가 0이면 ans1과 ans2를 출력시키고 return 해줍니다. 왼쪽 인덱스의 값과 오른쪽 인덱스의 값..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 설명은 밑에 링크를 타시고 보시면 됩니다. 😶‍🌫️ [Python][백준 2212][정렬][그리디] 센서 - 컴도리돌이 풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 comdolidol-i.tistory.com import java.io.BufferedReader; import java...