백준실버부수기 11399 - ATM - 그리디 알고리즘 문제링크 : 각 사람이 돈을 인출하는데 필요한 시간의 최솟값 구하기 단 뒤에서 돈을 뽑는 사람들은 앞에서 뽑는 사람들이 돈을 뽑을 때까지 기다려야한다. 따라서 최솟값을 구하기 위해선 돈을 인출하는데 걸리는 시간이 적은 사람부터 순차적으로 뽑을 때 가장 효율적이다. 인출하는 시간이 짧은 사람부터 뽑는다는 그리디 알고리즘이다ㅏ. 사실 아직 그리디 알고리즘은 당장 눈앞에 보이는 최적의 상황만을 쫓... 백준실버부수기백준실버부수기 18405 - 경쟁적 전염 - BFS 문제링크 : 번호가 낮은 바이러스부터 차례대로 큐에 넣어줘야한다. 이후 BFS로 바이러스들의 이동을 해결해주고, 해당시간이 되면 종료하게끔 코드를 짜야한다. 백터를 하나 더 만들어서 번호가 낮은 바이러스부터 순차적으로 증식할 수 있도록 코드를 짯다.... 백준실버부수기백준실버부수기 백준 11052 카드구매하기 문제링크 : 최대한 돈을 많이 사용하도록 풀어야한다. 작은 값부터 순차대로 모든 경우의 수를 확인하여 문제를 해결한다. 단 이때 메모이제이션을 하여 시간복잡도를 낮춘다. 내가 해결하지 못하여 다른사람의 블로그를 참고하였다. 하지만 핵심은 하나다. 이 문제에서 N개의 카드가 주어지는데, 이러한 카드가 주어질 때 이 카드들 만으로 계산을 순차적으로 하면 된다. 이러한 테크닉을 배우게 되었다. d... 백준실버부수기백준실버부수기 5567 - 결혼식 - BFS 문제링크 : 상근이의 친구와 친구의 친구까지만 초대하는것이다. 문제를 제대로 읽어야한다. BFS로 문제를 해결하되, 상근이부터 시작하여 친구의 친구들 까지만 찾는 것이다. 몇번을 거쳐서 만들어 진건지에 대한 value값을 넣어 해결해준다. 중복인 친구를 넣지 않기위해 체크배열을 만들어준다. 간단하게 pair 자료구조를 사용하여 해결하였다. 이 문제를 풀때 친구의 친구까지만 찾는다는 것을 제대... 백준실버부수기백준실버부수기 1012 - 유기농배추 - DFS 문제링크 : 이것도 이전에 풀었던 단지구하기와 같은 문제이다. 이름만 영토에서 지렁이로 바뀐 것 뿐이다. 마찬가지로 dx, dy를 만들어서 이동한다. M, N 은 50이하이므로 시간과 공간은 충분하다. 문제는 쉬웠으나 또 문제를 제대로 읽지 않았다. 나는 항상 배열을 1부터 시작하는데 이 문제에서는 0에서부터 input이 들어오므로 +1 을 해주는것을 잊지말아야한다. 또한 문제에서 x가 먼저... 백준실버부수기백준실버부수기 백준 10844 쉬운계단 수 문제링크 : 0과 9에서 예외조건이 발생하므로 이를 잘 생각해야한다. 0과 9를 제외한 나머지 조건은 다음식을 만족한다. dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1] 즉 4번째 숫자 5를 예를 들면, 이 항의 값은 3번째 숫자 4의 개수와 3번째 숫자 6의 개수의 합으로 계산할 수 있는 것이다. 이 문제는 해결하지 못하여 다른 사람의 블로그를 보았다. 여기서 0일때와... 백준실버부수기백준실버부수기 1389 - 케빈베이커의 6단계 법칙 - BFS 문제링크 : 사실상 한 노드에 다른 모든 노드로 가는 거리의 합중 가장 작은 것을 찾는 것이다. 노드는 최대 100개 이고, 시간은 2초이므로 나는 모든 노드들의 거리를 BFS로 찾아 그 중 최소값을 찾을 것이다. 모든 사람들은 친구로 연결되어 있다는 조건 덕분에 딱히 특별히 까다로운 조건을 세울 필요는 없다. 문제만 케빈베이커 ~~~ 하면서 어렵게 만든거지 사실상 한 노드에서 다른노드들로 ... 백준실버부수기백준실버부수기 1743 - 음식물피하기 - DFS 문제링크 : 가장 큰 음식물의 크기를 구하라는 것은 사실상 쓰래기들의 영역중 가장 큰 영역을 구하라는 문제이다. 따라서 기존에 풀었던 문제들과 똑같이 DFS로 해결하면 된다. 영역의 크기를 구할때는 위에서 했듯이 ret += DFS(rr,cc) 이런식으로 모든 값들을 더해주면된다.... 백준실버부수기백준실버부수기 2146 - 다리만들기 - BFS 문제링크 : 섬과 섬을 연결한다는 것을 알기 위해, 섬과 섬을 구별해야한다. 따라서 먼저 각 영역을 분리해주었다. N은 100이하이고 각 영역당 계산의 최대값은 N^2이므로 최대 N^2개의 영역이기 때문에 N^4이 되어도 시간은 충분하였기 때문에 다 찾아보았다. 영역마다 이어질때까지 BFS로 찾았다. 체크배열을 만들어 중복되는 부분은 방문하지 않았다. DFS와 BFS를 같이 조합시키는 재미있... 백준실버부수기백준실버부수기 11724 - 연결요소의 개수 - DFS 문제링크 : 시간은 충분하다. 문제에서 요구한 연결요소의 개수란 단순이 서로 연결되지 않은 그룹들의 개수 라고 생각하면 된다. 역시 input과 output을 잘 분석하고 문제를 잘 읽어야한다. 단순히 DFS로 연결관계를 파악할 수 있다. 연결요소라는 용어가 무엇인지 몰라 input과 output을 비교해가며 이게 무슨뜻인지 알게되었다. 역시 문제를 제대로 분석하는것이 제일 중요하다.... 백준실버부수기백준실버부수기 2805 - 나무 자르기 - 이분 탐색 문제링크 : 나무를 몇미터에서 자를지가 중요하다. 하지만 나무의 개수는 1000000으로 N^2으로 해결하면 문제를 풀 수 없다. 따라서 NlogN으로 만들기 위해 이분 탐색을 사용한다. M은 2,000,000,000 이고 N은 1,000,000이다. 따라서 int형으로는 나무의 높이의 합을 계산할 때 부족할 수 있다. 따라서 long long을 사용해주어야한다. 먼저 높이를 선정하고, 그 ... 백준실버부수기백준실버부수기
11399 - ATM - 그리디 알고리즘 문제링크 : 각 사람이 돈을 인출하는데 필요한 시간의 최솟값 구하기 단 뒤에서 돈을 뽑는 사람들은 앞에서 뽑는 사람들이 돈을 뽑을 때까지 기다려야한다. 따라서 최솟값을 구하기 위해선 돈을 인출하는데 걸리는 시간이 적은 사람부터 순차적으로 뽑을 때 가장 효율적이다. 인출하는 시간이 짧은 사람부터 뽑는다는 그리디 알고리즘이다ㅏ. 사실 아직 그리디 알고리즘은 당장 눈앞에 보이는 최적의 상황만을 쫓... 백준실버부수기백준실버부수기 18405 - 경쟁적 전염 - BFS 문제링크 : 번호가 낮은 바이러스부터 차례대로 큐에 넣어줘야한다. 이후 BFS로 바이러스들의 이동을 해결해주고, 해당시간이 되면 종료하게끔 코드를 짜야한다. 백터를 하나 더 만들어서 번호가 낮은 바이러스부터 순차적으로 증식할 수 있도록 코드를 짯다.... 백준실버부수기백준실버부수기 백준 11052 카드구매하기 문제링크 : 최대한 돈을 많이 사용하도록 풀어야한다. 작은 값부터 순차대로 모든 경우의 수를 확인하여 문제를 해결한다. 단 이때 메모이제이션을 하여 시간복잡도를 낮춘다. 내가 해결하지 못하여 다른사람의 블로그를 참고하였다. 하지만 핵심은 하나다. 이 문제에서 N개의 카드가 주어지는데, 이러한 카드가 주어질 때 이 카드들 만으로 계산을 순차적으로 하면 된다. 이러한 테크닉을 배우게 되었다. d... 백준실버부수기백준실버부수기 5567 - 결혼식 - BFS 문제링크 : 상근이의 친구와 친구의 친구까지만 초대하는것이다. 문제를 제대로 읽어야한다. BFS로 문제를 해결하되, 상근이부터 시작하여 친구의 친구들 까지만 찾는 것이다. 몇번을 거쳐서 만들어 진건지에 대한 value값을 넣어 해결해준다. 중복인 친구를 넣지 않기위해 체크배열을 만들어준다. 간단하게 pair 자료구조를 사용하여 해결하였다. 이 문제를 풀때 친구의 친구까지만 찾는다는 것을 제대... 백준실버부수기백준실버부수기 1012 - 유기농배추 - DFS 문제링크 : 이것도 이전에 풀었던 단지구하기와 같은 문제이다. 이름만 영토에서 지렁이로 바뀐 것 뿐이다. 마찬가지로 dx, dy를 만들어서 이동한다. M, N 은 50이하이므로 시간과 공간은 충분하다. 문제는 쉬웠으나 또 문제를 제대로 읽지 않았다. 나는 항상 배열을 1부터 시작하는데 이 문제에서는 0에서부터 input이 들어오므로 +1 을 해주는것을 잊지말아야한다. 또한 문제에서 x가 먼저... 백준실버부수기백준실버부수기 백준 10844 쉬운계단 수 문제링크 : 0과 9에서 예외조건이 발생하므로 이를 잘 생각해야한다. 0과 9를 제외한 나머지 조건은 다음식을 만족한다. dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1] 즉 4번째 숫자 5를 예를 들면, 이 항의 값은 3번째 숫자 4의 개수와 3번째 숫자 6의 개수의 합으로 계산할 수 있는 것이다. 이 문제는 해결하지 못하여 다른 사람의 블로그를 보았다. 여기서 0일때와... 백준실버부수기백준실버부수기 1389 - 케빈베이커의 6단계 법칙 - BFS 문제링크 : 사실상 한 노드에 다른 모든 노드로 가는 거리의 합중 가장 작은 것을 찾는 것이다. 노드는 최대 100개 이고, 시간은 2초이므로 나는 모든 노드들의 거리를 BFS로 찾아 그 중 최소값을 찾을 것이다. 모든 사람들은 친구로 연결되어 있다는 조건 덕분에 딱히 특별히 까다로운 조건을 세울 필요는 없다. 문제만 케빈베이커 ~~~ 하면서 어렵게 만든거지 사실상 한 노드에서 다른노드들로 ... 백준실버부수기백준실버부수기 1743 - 음식물피하기 - DFS 문제링크 : 가장 큰 음식물의 크기를 구하라는 것은 사실상 쓰래기들의 영역중 가장 큰 영역을 구하라는 문제이다. 따라서 기존에 풀었던 문제들과 똑같이 DFS로 해결하면 된다. 영역의 크기를 구할때는 위에서 했듯이 ret += DFS(rr,cc) 이런식으로 모든 값들을 더해주면된다.... 백준실버부수기백준실버부수기 2146 - 다리만들기 - BFS 문제링크 : 섬과 섬을 연결한다는 것을 알기 위해, 섬과 섬을 구별해야한다. 따라서 먼저 각 영역을 분리해주었다. N은 100이하이고 각 영역당 계산의 최대값은 N^2이므로 최대 N^2개의 영역이기 때문에 N^4이 되어도 시간은 충분하였기 때문에 다 찾아보았다. 영역마다 이어질때까지 BFS로 찾았다. 체크배열을 만들어 중복되는 부분은 방문하지 않았다. DFS와 BFS를 같이 조합시키는 재미있... 백준실버부수기백준실버부수기 11724 - 연결요소의 개수 - DFS 문제링크 : 시간은 충분하다. 문제에서 요구한 연결요소의 개수란 단순이 서로 연결되지 않은 그룹들의 개수 라고 생각하면 된다. 역시 input과 output을 잘 분석하고 문제를 잘 읽어야한다. 단순히 DFS로 연결관계를 파악할 수 있다. 연결요소라는 용어가 무엇인지 몰라 input과 output을 비교해가며 이게 무슨뜻인지 알게되었다. 역시 문제를 제대로 분석하는것이 제일 중요하다.... 백준실버부수기백준실버부수기 2805 - 나무 자르기 - 이분 탐색 문제링크 : 나무를 몇미터에서 자를지가 중요하다. 하지만 나무의 개수는 1000000으로 N^2으로 해결하면 문제를 풀 수 없다. 따라서 NlogN으로 만들기 위해 이분 탐색을 사용한다. M은 2,000,000,000 이고 N은 1,000,000이다. 따라서 int형으로는 나무의 높이의 합을 계산할 때 부족할 수 있다. 따라서 long long을 사용해주어야한다. 먼저 높이를 선정하고, 그 ... 백준실버부수기백준실버부수기