분류 전체보기76 [6개월 안에 백준 플래티넘 달성하기] 15. 피보나치 수6 11444 해설 백준 Class4의 마지막 문제입니다. 마지막 문제인 만큼 꼭 풀고 싶었지만 결국 풀지 못하였습니다. 문제의 해설을 보고 이해하는 데까지 시간이 조금 걸렸습니다. 따라서 최대한 풀어서 해설을 작성해 보겠습니다. 참고로 행렬을 이용한 풀이가 아닙니다. 행렬을 이용한 풀이는 나중에 다시 푼다고 하더라도 도저히 생각해 낼 수 없을 거 같다고 판단을 하여서 좀 더 쉬운 풀이 방법을 작성하였습니다. 피보나치 수6 행렬 해설 블로그 피보나치 수 6 문제 문제 풀이 아마 여기까지 코테를 푸신 분들이라면 입력 가능한 n의 범위를 보고 바로 거듭제곱 관련 문제라는 것을 알아차리셨을 겁니다. 저도 마찬가지로 이를 이용하여 처음에는 제곱과 관련되어 규칙을 찾아보았지만 실패하였습니다. 해당 문제는 피보나치 식을 이용하여 약간.. 2023. 12. 31. [6개월 안에 백준 플래티넘 달성하기] 14. 후위 표기식 1918 후위 표기식 문제 풀이 처음 문제를 보았을 때는 굉장히 막막하였는데 예전 괄호 문제를 스택을 이용하여 푼 기억 덕분에 뭔가 비슷하게 스택에 연산자를 넣었다가 빼주면 될 거 같았습니다. 해당 문제도 비슷하게 스택을 이용하여 풀 수 있습니다. 아이디어는 다음과 같습니다. 피연산자는 따로 담아두고 연산자만 스택에 담아준다. 스택에 있는 연산자와 현재의 연산자를 비교하여 스택에 넣을지 말지를 결정한다. 이제 2번의 비교에 대한 경우를 신경 써주면 됩니다. 경우의 수는 총 3가지가 있습니다. 스택에 있는 연산자보다 우선순위가 낮은 연산자가 들어오는 경우 스택에 있는 연산자와 우선순위가 동일한 연산자가 들어오는 경우 스택에 있는 연산자보다 우선순위가 높은 연산자가 들어오는 경우 각 상황별 예시와 처리 방법입니다. .. 2023. 12. 30. [6개월 안에 백준 플래티넘 달성하기] 13. 아기 상어 16236 아기 상어 문제 문제 길이가 길어서 복잡해 보이지만 조건이 생각보다 단순합니다. 다만 먹이의 우선순위를 꼼꼼하게 신경 써줘야 합니다. (상좌우하로 안됨) 풀이 아기 상어가 공간 내의 먹이를 다 먹을 때까지의 시간을 구하는 문제입니다. 문제의 조건은 다음과 같습니다 인접한 상하좌우로 한 칸씩 이동이 가능하다. 아기 상어보다 큰 물고기가 있으면 못 지나간다. 아기 상어랑 같은 크기의 물고기가 있으면 지나갈 수 있다. 아기 상어보다 작은 크기의 물고기가 있으면 지나가면서 물고기를 먹을 수 있다. 물고기를 먹는 우선순위 가장 가까운 물고기 순으로 먹는다. 거리가 동일한 경우 가장 위에 있는 물고기를 먹는다. 이마저도 동일하면 가장 왼쪽에 있는 물고기를 먹는다. 아기 상어는 자신의 크기만큼 물고기를 잡아먹으면 크.. 2023. 12. 30. [6개월 안에 백준 플래티넘 달성하기] 12. 최소비용 구하기 11779 최소비용 구하기 2 문제 다익스트라를 조금만 응용하면 간단히 풀 수 있습니다. 풀이 도시 A에서 도시 B까지 최단 거리만 보면 다익스트라로 풀 수 있을 거 같습니다. 하지만 다익스트라만으로는 최소비용을 구할 수 있지만 경로에 포함된 도시의 개수와 경로를 방문하는 도시 순서를 얻지 못합니다. 따라서 어느 정도 응용을 해주면 쉽게 풀 수 있습니다. 제가 생각한 방법은 각 도시별 최소 비용을 가지는 minDist 배열에 최단 거리 정보뿐만 아니라 이전 도시의 정보를 추가하는 것입니다. 해당 방법으로 다익스트라 알고리즘을 진행한 뒤에 minDist를 역추적하면 도시의 개수와 도시 순서를 알 수 있습니다. 구현 방법은 더 간단합니다. 기존 다익스트라에서 최소 비용이 갱신될 경우에 minDist에 갱신된 최소 비용.. 2023. 12. 30. 이전 1 ··· 3 4 5 6 7 8 9 ··· 19 다음 반응형
