Computer Science19 [Baekjoon] 외계인의 기타연주 문제 : https://www.acmicpc.net/problem/2841 설명 : 6개의 기타 줄이 있고, P개의 프렛수가 주어진다. N개의 경우에 대해 줄의 번호와 프렛 번호가 주어질 때 최소 손가락의 움직임을 출력하는 문제이다. 풀이 :1번줄의 3번을 누르고 있다가 5번을 누르면 5번음이 연주가 된다. 단, 이때 2번음을 연주하고자 한다면, 누른 5번음과 3번음을 때야한다.한마디로 더 낮은 음을 연주하기 위해서는 그보다 높은 음을 떼야한다. -> LIFO구조의 스택을 이용 코드 :1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666.. 2016. 2. 22. [Baekjoon] 앱 문제 : https://www.acmicpc.net/problem/7579 설명 : N과 M이 주어지고, N개의 App에 대해 각각 사용중인 Bytes와 비활성화 했을 시에 대한 비용들이 주어진다. 이때 Mbytes를 확보하기 위한 최소한의 비용을 구하는 문제이다.처음 문제를 접했을 때, DP로 풀어야 겠다는 감은 왔지만...정말 오랜 시간이 걸린 문제이다. 풀이 : Mbytes를 확보하기 위해 드는 최대 비용은 당연 모든 비용들을 합한 값이다따라서 이 비용들을 배열의 인덱스로 잡고, DP를 풀어나갔다. (반복문을 돌며(App을 하나씩 거치며), 최소값을 수정해나갔다.)그러나 결과는....'실패' 였다.연습장에 표를 그리고 예제들을 써내려가보았다. 그리고 알게 된 사실... 예제에서는 비용이 3, 0, .. 2016. 2. 22. [Baekjoon] 네트워크 연결 문제 : https://www.acmicpc.net/problem/1922정점들이 주어지고, 정점간을 잇는 가중치가 주어졌을 때 모든 정점을 잇는 최소비용을 구하는 문제이다. * 풀이무방향 그래프에서 모든 정점을 잇는 간선의 비용이 최소로 되게끔 구현하는 MST구현 문제이다.일반적으로 MST문제는 Kruskal, Prim 알고리즘으로 구현한다고 배웠다. 처음에는 주어진 정점, 가중치들을 인접행렬로 나타낸 후, 가중치 순으로 오름차순 정렬하고 하나씩 이어나가는 Kruskal알고리즘으로 구현해 보았다. 그러나 cycle검사 처리를 dfs로 구현하다보니 2초라는 시간을 초과하였다. 해결책을 찾지 못하고 우선 Prim로 구현하여 해결하였다. *코드 12345678910111213141516171819202122.. 2016. 2. 9. 이전 1 2 3 4 5 다음