Language

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

2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 피자 A와 피자 B에서 나올 수 있는 피자 조각의 합 경우의 수를 각각의 딕셔너리에 저장한다. 하나의 피자에서 나올 수 있는 모든 경우의 수를 탐색한다. 하나의 피자에 존재하는 조각의 개수가 1000개 이하이므로 반복문 2개를 중첩하여 모든 경우의 수를 탐색하여도 시간 초과가 발생하지 않는다. 출력 딕셔너리_A [문제에서 요구하는 피자 사이즈] + 딕셔너리_B [문제에서 요구하는 피자 사이즈] + 딕셔너리_A [A에 있는 값] + 딕셔너리_B..

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에 대해서는 아래 링크를 참조하면 좋..

풀이 과정 해당 문제는 bisect 라이브러리를 사용해서 해결하였다. bisect에 대해서는 아래 링크를 참조하면 좋다. [Python] bisect - 컴도리돌이 알고리즘 문제를 해결하다가 다른 분의 블로그에서 제가 푼 알고리즘 문제를 파이썬에서 제공하는 표준 라이브러리인 bisect를 이용해서 간단하게 문제를 해결한 것을 보고, 요번 기회에 bisect 라 comdolidol-i.tistory.com 1. 입력받은 배열의 0번째 인덱스 값부터 순차적으로 반복문을 시행한다. 2. arr가 비어있으면 x 값을 arr에 insert 한다. 3. 현재 x 값이 arr의 마지막 인덱스 값보다 크면 insert 시킨다. 4. 마지막 인덱스 값보다 크지 않으면 bisect_left 함수를 이용해서 x값보다 같거나..