백준

18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 오랜만에 백준 문제를 푸는데 실버, 브론즈 문제도 버벅거리네요.🥲 이번 문제는 가벼운 구현 문제예요. 시간제한이 조금 힘들어서 정답 비율은 낮지만, 원래 배열과 BufferedReader를 사용하시는 분들이면 어렵지 않게 구현할 수 있을 거예요 😆 문제에서 상위 15 % 와 하위 15 %를 제외한 나머지 인원에 대한 평균을 출력하는 문제입니다. n을 초기 입력받아서 array 크기를 할당시켜 줍니다. 그리고 개행마다 숫자를 n만큼 ar..

11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 근우가 왼쪽/오른쪽을 선택했을 때 명우가 선택할 카드의 합이 최소가 되어야 한다. 맨 왼쪽/오른쪽 카드의 수만 비교해서는 최선의 선택이 되지 않기 때문에 다이나믹 프로그래밍으로 접근해야 한다. 여기서 주의할 점은 근우와 명우의 차례에 따라서 구하는 식이 다르기 때문에 2차원 배열을 사용해야 한다. 근우와 명우가 카드를 선택하다가 남은 카드의 상태를 점화식을 세우고, dp [i][j] = i~j의 카드가 있을 때 근우가 선택할 수 있는 최대 합을 만들어야 한다. n이 ..

2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 세 용액의 합이 0과 가장 근사한 값을 찾아야 한다. 용액의 수가 5000 이하이기 때문에 최악일 경우 5000 * 2500 = 7500000의 연산을 계산하기 때문에 시간 복잡도에 대한 걱정 없이 해결할 수 있었다. 기준점 i번째의 값부터 n-1의 값까지 j번째와 k번째의 합들 중에서 최솟값을 구했다. 여기서 j번째는 i+1, k번째는 n-1번째로 설정하여 투 포인터 알고리즘으로 해결하였다. i, j, k번째의 합이 비교대상 comp과 비..

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의 첫 번째 인덱스 값을 비교한다. 만약 크레인의 첫 번째 값이 박스의 첫 번째 값보다 작을 경우 모든 박스를 담을 수 없기 때..

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번째 시간으로 듣지 못할 경우는 이..

풀이 과정 해당 문제는 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값보다 같거나..