백준
-
백준 1202번 보석 도둑알고리즘 2023. 8. 3. 09:38
N개의 보석의 무게 Mi 와 가격 Vi 가 주어지고, K개의 가방이 담을 수 있는 최대 무게 Ci가 주어졌을 때, 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제입니다. (가방 한 개에는 최대 한 개의 보석만 담을 수 있습니다.) 시도 1. 가장 큰 가격의 보석을 넣을 수 있는 가장 작은 크기의 가방을 선택하여 넣어주도록 했습니다. 우선 가방을 오름차순으로, 보석은 가격순으로 내림차순으로 정렬했습니다. 현재 보석의 무게보다 같거나 큰 가방 중 가장 작은 가방을 선택하도록 했습니다. 이를 위해 이분탐색을 선택해 대입했습니다. def search(num): s,e=0,len(bags)-1 m=(s+e)//2 while snum: e=m-1 else: s=m+1 m=(s+e)//2 while m
-
백준 알고리즘 풀이 (Gold) 1753번, 1655번알고리즘 2023. 7. 25. 13:16
1. 최단 경로 (1753번) 단방향 간선과 간선에 대한 가중치가 주어졌을 때, 시작점에서 다른 정점으로의 최단 경로를 출력하는 문제입니다. 정점에서 다른 정점으로 이동하는 최단 거리를 구하는 문제로 다익스트라 알고리즘을 활용했습니다. 첫 번째 시도 기존의 최단 거리를 구하는 문제들처럼 dfs와 정점까지의 가중치의 합을 저장하기 위한 dp배열을 선언하여 문제를 풀어주었습니다. stack = [[K,0]] dp[K] = 0 while stack: node,weight = stack.pop() for v,w in edges[node]: if weight+w
-
백준 DP 문제 풀이 (Silver) 11053번, 1932번, 1912번, 9461번 python알고리즘 2023. 7. 21. 15:03
1. 가장 긴 증가하는 부분 수열 (11053번) 숫자 수열이 주어질 경우 가장 길게 증가하는 부분 수열의 길이를 구하는 문제입니다. 예시) {10,20,10,30,20,50} 인 경우 가장 긴 증가하는 부분 수열은 {10,20,30,50}이고 길이는 4입니다. 앞에서부터 차례로 자신을 포함하는 가장 긴 부분 수열을 구하면 됩니다. 자신을 포함한 가장 긴 수열을 구하는 방법은, 자신보다 앞에 위치하면서 자신보다 작은 숫자 중 현재 가장 긴 증가하는 부분 수열을 가지는 숫자에 자신을 붙이면 됩니다. 위의 예시 중 4번째 인덱스의 30을 포함한 부분 수열을 구하는 예를 들어보겠습니다. 30보다 앞에 위치한 숫자 중 30보다 작은 10,20,10 중 증가하는 부분 수열 중 가장 긴 숫자는 20입니다. 그러므로..
-
백준 26124번 조명 배치알고리즘 2023. 3. 8. 10:30
문제 설명 이번 문제는 격자 칸에 조명을 배치할 경우 아래와 같은 규칙으로 각 격자칸의 영향력이 정해질 경우, 각 칸의 영향력이 정해진 격자칸이 주어졌을 때 필요한 조명의 최소 개수를 구하는 문제입니다. (해당 격자칸으로 조명 배치를 만들 수 없을 경우 -1 출력) 조명 L의 밝기가 c일 경우 L이 각 빈칸에 미치는 영향력은 다음과 같이 계산된다. L이 위치한 격자칸에 미치는 영향력은 c이다. L과의 거리가 1인 격자칸에 미치는 영향력은 c-1이다. … L과의 거리가 c-2인 격자칸에 미치는 영향력은 2이다. L과의 거리가 c-1인 격자칸에 미치는 영향력은 1이다. 그 외의 빈칸에는 영향력을 미치지 않는다. 어떤 빈칸에 영향을 미치는 조명의 개수가 2개 이상인 경우, 이 빈칸의 영향력은 영향을 미치는 조..
-
백준 23978번 급상승알고리즘 2023. 3. 7. 13:10
문제 설명 이번 문제는 효석이가 자신이 정한 N개의 날짜에 코인을 X원으로 급상승시키고 처음 코인 가격이 오른 날부터 한 개씩 매도할 때, K원 이상 현금화할 수 있는 가장 작은 정수 X를 구하는 문제입니다. (단, 코인이 X원으로 오른 뒤 하루에 1원씩 0원이 될 때까지 가격이 낮아진다.) 문제 풀이 아이디어 X를 알 때 최종 현금화할 수 있는 금액을 구하는 방법 정해진 N개의 날짜에 코인이 X원 상승한 뒤, 하루에 1원씩 작아집니다. 여기서, 코인이 급상승하는 날짜 사이의 일 수가 X보다 크다면 코인은 0원까지 떨어지게 될 것이고, 코인이 급상승하는 날짜 사이의 일 수가 X보다 작다면 코인은 X-{코인이 급상승하는 날짜 사이의 일수 } 까지만 떨어지게 됩니다. 이분 탐색 문제에서 주어진 N,K(1
-
백준 17251번 힘 겨루기알고리즘 2023. 3. 6. 10:42
문제 설명 이번 문제는 N명의 참가자들을 나열하고 기준선을 통해 팀이 나눈 다음 각 팀에서 가장 힘쎈 사람이 나왔을 때, 둘 중 더 힘 쎈 사람이 이기게 됩니다. N 명의 참가자의 힘을 나타내는 정수가 주어질 때, 이길 확률이 더 높은 팀을 구하는 문제입니다. 문제 풀이 아이디어 가장 힘 쎈 팀 구하는 방법 기준선이 어디에 있는지에 상관없이 항상 가장 힘이 갖아 쎈 사람이 있는 팀이 이기게 됩니다. 가장 힘이 쎈 사람이 한 명일 경우 가장 힘이 쎈 사람의 인덱스를 i라하면, 기준선이 1~i-1일 경우 블루팀이 이기고, i~N-1일 경우 레드팀이 이기게 됩니다. 여기서 두 팀이 이길 확률을 구해보면, 블루팀은 (i-1)/N이고 레드팀은 (N-i)/N입니다. 그러므로 두 팀 중 이길 확률이 높은 팀은 i-1..
-
백준 9935번 문자열 폭발알고리즘 2023. 3. 3. 12:17
문제 설명 문자열과 폭발 문자열이 주어집니다. 문자열 내부에 폭발 문자열을 포함하고 있다면, 폭발 문자열이 폭발해서 사라지고 남은 문자열을 이어붙입니다. 이어 붙인 문자열이 폭발 문자열을 또 포함하고 있다면 폭발 문자열을 폭발하고 남은 문자열을 이어붙입니다. 문자열 내부에 폭발 문자열이 없을 때까지 반복합니다. 문제 풀이 아이디어 문자열 내부의 폭발 문자열 찾기 문제 예제에 있는 문자열 'CC44'에서 폭발 문자열 'C4'를 찾을 경우를 생각해보겠습니다. 폭발 문자열의 첫 번째 글자 'C'부터 차례대로 문자열 내부에 있는 폭발 문자열을 찾는다고 하면, 문자열의 인덱스 0에서 'C'를 찾게 되지만, 그 다음 글자가 'C'이므로 다음 인덱스로 넘어갑니다. 문자열의 인덱스 1에서 'C'를 찾게되고 인덱스 2가..
-
백준 1715번 카드 정렬하기알고리즘 2023. 3. 2. 11:30
문제 설명 A(10개)와 B(20개) 숫자 카드 묶음을 합치려면 각 묶음의 카드 개수를 더한 만큼의 비교횟수가 필요할 때, 여러 카드 묶음을 한 개로 합치려면 최소한 몇 번의 비교가 필요한지 구하는 문제입니다. 문제 풀이 아이디어 최소 비용으로 합치는 방법 10,20,40개의 숫자 묶음이 있을 경우를 생각해보도록 하겠습니다. 10,20을 먼저 합치고 40을 합칠 경우 10+20, 30+40 -> 총 30 + 70 = 100의 비용이 필요합니다. 10,40을 먼저 합치고 20을 합칠 경우 10+40, 50+20 -> 총 50 + 70 = 120의 비용이 필요합니다. 20, 40을 먼저 합치고 10을 합칠 경우 20+40, 60+10 -> 총 60 + 70 = 130의 비용이 필요합니다. 그렇다면 10,20..