반응형 백준36 [알고리즘/백준] 11052번 카드 구매하기 Python 파이썬 이번 문제는 기존에 풀던 게임 문제집이 아닌 다이나믹 프로래밍 알고리즘으로 넘어와서 문제를 풀게 되었습니다. 저번에 풀면서 느꼈지만 DP는 아직 DFS나 BFS만큼 이해가 너무 안되어 있는 거 같아 한동안 지속해서 관련 문제를 풀 필요성을 느끼게 되었습니다. 해당 문제는 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램으로 DP에 어떤 값을 누적시킬 건지 중요한 문제인 것 같습니다. 처음에 고민했던 방향은 1. dp 의 i 번째마다 비교하여 i 장 카드 최댓값 넣기 2. dp 의 i 번째마다 비교하여 n 장 카드 최댓값 넣기 였는데 아무래도 dp 값을 활용하는 특징상 후자는 아닌 것 같아 전자로 잡고 문제를 풀게 되었습니다. 아쉽게도 아직 .. 2023. 4. 12. [알고리즘/백준] 2294번 동전2 Python 파이썬 이번 문제는 DP 문제로 이해하는데 좀 걸린 문제입니다. 아직 제대로 DP에 대해 알고 응용할 수 있는 정도까지는 아닌 것 같습니다. 다른 분의 풀이를 보면서 이해하는데 시간을 들었습니다. 동전의 종류와 특정 값이 주어지면 특정 값을 맞추기 위한 최소 동전 갯수를 구하는 문제입니다. 처음에 보았을 때 DP 문제인건 감을 잡았는데 어떻게 풀어나가야할지 값이 안 잡히더라고요 일단 DP 문제인 만큼 어떤 값을 누적시켜서 사용할 거고 dp 배열이 k+1 원만큼 만들어지면서 각 i원에 어떤 것을 저장시키지 않을까 생각했습니다. 그 이후에는 막혀서 결국 풀이를 찾게 되었습니다. 핵심은 "dp[i]에 dp[n-c1], dp[n-c2], dp[n-c3] 중에 가장 개수가 적은 경우를 택하고 +1" 한 값을 누적해주는 .. 2023. 4. 10. [알고리즘/백준] 2045번 마방진 Python 파이썬 이번 문제는 로직이 어렵지는 않은 코드가 더러운(?) 문제였다고 생각합니다. 저희가 아는 마방진에서 어떤 숫자가 지워졌을 때 해당 숫자를 구하는 문제로 보고 먼저 한 줄 합을 구하고(빠진 부분이 없는) 빠진 부분의 합에 대입해서 빠진 숫자를 구해야겠다고 생각했습니다. (식으로 하면 X + 12 = 33 이런식이겠죠) 또 3X3 사이즈도 고정이라 하드 코딩이 될 거 같다고 생각했습니다. 먼저 빠진 부분이 없는 줄 합을 구해야하는데 저 같은 경우 처음에 대각선으로 한 줄 합을 구할 수 있는지, 안되면 행, 안되면 열로 구했습니다. 이때 주의할 부분이 예외처리입니다. 저 같은 경우는 이 부분을 고려하지 않아서 실패가 떴고 후에 알아챘는데 바로 대각선이 다 0일 때 경우 입니다. 이 경우 위의 방식으로 줄 합을.. 2023. 4. 6. [알고리즘/백준] 2021번 최소 환승 Python 파이썬 이번 문제는 오랜만에 스스로의 힘으로 풀어볼 수 있었던 문제입니다. 노선별로 지나는 역들이 주어졌을 때 출발역과 도착역이 주어지고 최소 환승 회수를 구하는 문제입니다. 보고 탐색해야하는 문제이니 BFS 로 풀어야겠다고 생각하였습니다. 해당 문제를 쉽게 풀기 위해서 먼저 저장할 때 각 역별로 지나는 노선 번호, 노선별로 지날 수 있는 역 번호들로 리스트를 만들어 저장하였습니다. 그 다음 풀이한 로직을 설명하자면, 시작점이 주어졌을 때 1. 해당 역에서 지나는 노선을 확인한다. 2. 이미 탄 노선인지 아닌지 확인한다. 3. 만약 안 탄 노선이라면 해당 노선에서 갈 수 있는 역을 확인한다 4. 갈 수 있는 역에서 도착역이 있는 확인한다. 5. 도착역이 있다면, 이때까지 누적된 환승 회수를 비교해준다. 4. 도.. 2023. 4. 5. 이전 1 2 3 4 5 ··· 9 다음 반응형
