문제https://www.acmicpc.net/problem/1753알고리즘다익스트라 알고리즘풀이BFS로 접근한 코드에는 다음과 같은 문제점이 있었습니다:1. 가중치가 다른 경로를 정확히 처리하지 못함BFS는 간선의 가중치를 무시하고 단순히 탐색 깊이에 따라 정점을 방문합니다.하지만 이 문제에서는 간선의 가중치가 1~10 사이의 값으로 다릅니다.가중치가 작은 경로를 우선 탐색하지 않으면, 더 긴 가중치를 먼저 처리하는 바람에 최단 경로가 잘못 계산될 수 있습니다2. 불필요한 방문으로 비효율적BFS는 간선의 가중치를 고려하지 않고 모든 경로를 탐색하기 때문에, 이미 최단 경로가 확정된 정점이라도 다시 방문하게 됩니다.이로 인해 시간 복잡도가 증가하고, 입력 데이터가 클 경우 시간 초과나 메모리 초과가 발생..

문제https://www.acmicpc.net/problem/1946알고리즘그리디 알고리즘풀이1. 서류 심사 성적을 기준으로 오름차순 정렬한다. 이렇게 하면 서류 심사 성적이 낮은 지원자 부터 비교할 수 있어서 이후에는 면접 성적만 고려하면 된다. 2-1. 첫 번째 지원자는 서류 심사 성적이 가장 높으므로 무조건 선발한다.2-2. 이후 지원자의 면접 성적이 현재 기준치보다 더 높은 경우에만 선발한다.2-3. 새로운 지원자를 선발하면 기준치를 업데이트 한다. 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Compara..

문제https://www.acmicpc.net/problem/29618알고리즘수학모듈러 연산풀이모듈러 연산 사용    숫자를 직접 생성하면 크기가 커져 메모리나 성능 문제 발생    숫자를 직접 생성하는 대신 나머지 연산을 이용해 효율적으로 계산1로만 이루어진 수를 이용해서 배수를 구해야하기 때문에 1, 11, 111, 1111.... 숫자들을 나눴을때 0이 되는 수를 구해야한다.remainder = (remainder * 10 + 1) % N 식 사용k개의 1로 이루어진 수 Sk를 S1 = 1, S2 = 11 로 정의한다.이 식을 변형하면1 mod N = 1 이고 Sk-1 mod n = rk-1 이므로식이 성립하게 된다.remainder가 0이 될때까지 반복을 하면서 자릿수를 더해주고 0이 되면 리턴한..

문제https://www.acmicpc.net/problem/23758알고리즘정렬수학풀이입력된 수 정렬    먼저 주어진 자연수를 오름차순으로 정렬한다. 중앙값을 구하기 위해서 반드시 정렬이 필요중앙값 찾기 및 2로 나누는 연산    0인덱스 부터 중앙값인덱스 까지 2로 나누는 연산을 반복 1이 될 때까지 count 계산한다.    이 표를 보면 중앙값 이후로는 숫자가 변하지 않는다. 이러한 특성 때문에 중앙값 이후의 값은 신경쓰지 않아도 된다.2379127911790179총 연산 횟수 계산    모든 연산 횟수를 더한 후, 1을 0으로 만들기 위한 추가 연산을 한다.코드import sysinput = sys.stdin.readlinedef sol(n, nl): k = (n + 1) // 2 ..

문제https://www.acmicpc.net/problem/1965알고리즘다이나믹 프로그래밍풀이각 상자를 최대로 겹친 숫자를 저장하는 배열 dp 생성각 요소를 하나씩 검사하면서 겹칠 수 있는지 검사 만약 겹칠 수 있다면 이전 상자의 겹침 최대수에서 +1boxes = [1, 7, 1, 8]dp = [1, 2, 1, 1]i = 3 일때boxes[0] = 1은 boxes[3] = 8보다 작기 때문에 dp[3]을 갱신 = 2boxes[1]은 boxes[3]보다 작기 때문에 dp[3]을 갱신 = 3boxes[2]은 boxes[3]보다 작지만 최대값보다 작으니 기존 값 유지코드def sol(n, s): dp = [1] * n for i in range(1, n): for j in range..

문제https://www.acmicpc.net/problem/21318알고리즘누적합풀이누적 합 배열 생성(실수를 누적해서 쌓는다.)초기 리스트 [573, 33283, 5572, 346, 906, 567]초기 prefix_sum = [0, 0, 0, 0, 0, 0]i = 1: 573 (nl[0])과 33283 (nl[1])을 비교 → 573 5572 (감소) → prefix_sum[2] = prefix_sum[1] + 1 = 1...최종 prefix_sum = [0, 0, 1, 2, 2, 3]감소횟수 계산   prefix_sum[y - 1] - prefix_sum[x - 1][5, 6]: 구간 [5, 6]은 nl[4]부터 nl[5]를 의미(906, 567). 감소 횟수 = prefix_sum[5] -..

문제https://www.acmicpc.net/problem/16400알고리즘1. 소수 구하기(에라토스테네스의 체)2. 구해진 소수로 다이나믹 프로그래밍에 사용풀이화폐를 소수만 이용하니 구입하려는 가격 범위 내에 소수를 모두 가져온다.이제 구해진 소수로 dp 배열을 정의해야한다.    dp[i]는 숫자 i를 소수들의 합으로 만들 수 있는 경우의 수를 의미한다. 이 배열을 크기 N + 1로 정의하고, 초기값을 설정한다.    dp[0] = 1 (0을 만들 수 있는 방법은 아무것도 선택하지 않는 1가지)dp배열 업데이트    소수들을 하나씩 돌면서 dp배열을 갱신, 소수를 사용해 숫자 i를 만들 수 있는 경우를 누적해서 계산한다.소수 2로 갱신dp[2] = dp[2] + dp[0] = 0 + 1 = 1 (2..