백준실버부수기 13305 - 주유소 - 그리디알고리즘 문제링크 : 제일 왼쪽도시에서 제일 오른쪽 도시로 이동하는동안 최소의 비용을 계산해야한다. 즉 기름을 사는데 사용할 돈의 최소값이다. 다음 도시가 현재 도시보다 용량이 작은 기름이 나올때까지 계속 다음 도시를 확인한다. 만약 더 작은 기름이 나온다면 이전까지 지나왔던 도로의 길 * 기름값 만큼 더해주며 이 과정을 반복하며 목적지까지 간다. long long을 써주는 것을 주의해야한다. 항상 ... 백준실버부수기백준실버부수기 백준 11057 오르막 수 문제링크 : 숫자를 0으로 시작할 수 있다는것이 매우 큰 힌트이다. 인접한 수가 크거나 같아야한다. dp[현재 수][남은 수의 개수]로 메모이제이션을 하여 해결한다. dp[현재 수][남은 수의 개수]로 알고리즘을 짠 아이디어가 좋았다고 생각한다. 문제를 풀때 항상 base case를 잊지않고 잘 생각해서 짜야한다.... 백준실버부수기백준실버부수기 백준 9465 스티커 문제링크 : 스티커와 인접한 부분은 사용할 수 없다. 그렇다고하여 항상 엇갈리게 뽑는 것이 아니다. 첫번째줄, 두번째줄, 아무것도 선택안되었을 때 3가지 케이스가 있고, 그 케이스에 따라 메모이제이션으르 해야한다. 그 값들 중 최대 값을 찾으면 된다. 이 문제에서 중요한 아이디어는 1번째, 2번째 줄 모두를 선택하지 않고 넘어갈 경우이다. 이러한 경우도 잊지않고 넣어주어야한다.... 백준실버부수기백준실버부수기 백준 11052 카드구매하기 문제링크 : 최대한 돈을 많이 사용하도록 풀어야한다. 작은 값부터 순차대로 모든 경우의 수를 확인하여 문제를 해결한다. 단 이때 메모이제이션을 하여 시간복잡도를 낮춘다. 내가 해결하지 못하여 다른사람의 블로그를 참고하였다. 하지만 핵심은 하나다. 이 문제에서 N개의 카드가 주어지는데, 이러한 카드가 주어질 때 이 카드들 만으로 계산을 순차적으로 하면 된다. 이러한 테크닉을 배우게 되었다. d... 백준실버부수기백준실버부수기 5567 - 결혼식 - BFS 문제링크 : 상근이의 친구와 친구의 친구까지만 초대하는것이다. 문제를 제대로 읽어야한다. BFS로 문제를 해결하되, 상근이부터 시작하여 친구의 친구들 까지만 찾는 것이다. 몇번을 거쳐서 만들어 진건지에 대한 value값을 넣어 해결해준다. 중복인 친구를 넣지 않기위해 체크배열을 만들어준다. 간단하게 pair 자료구조를 사용하여 해결하였다. 이 문제를 풀때 친구의 친구까지만 찾는다는 것을 제대... 백준실버부수기백준실버부수기 1012 - 유기농배추 - DFS 문제링크 : 이것도 이전에 풀었던 단지구하기와 같은 문제이다. 이름만 영토에서 지렁이로 바뀐 것 뿐이다. 마찬가지로 dx, dy를 만들어서 이동한다. M, N 은 50이하이므로 시간과 공간은 충분하다. 문제는 쉬웠으나 또 문제를 제대로 읽지 않았다. 나는 항상 배열을 1부터 시작하는데 이 문제에서는 0에서부터 input이 들어오므로 +1 을 해주는것을 잊지말아야한다. 또한 문제에서 x가 먼저... 백준실버부수기백준실버부수기 백준 2193 이친수 문제링크 : 이친수는 반드시 1로 시작하고, 1이 두번 연속으로 나타나지 않아야 하는 제한조건을 가지고 있다. 1로 시작하기 때문에 2번째 숫자는 반드시 0이다. 5자리 숫자 10000 은 100 과 1000의 합으로 구성됨을 그림을 그리면서 파악한다. 오버플로우가 날 수 있음을 항상 잊으면 안된다. pinaryNum(n+1) = pinaryNum(n) + pinaryNum(n-1) 규칙만 ... 백준실버부수기백준실버부수기 1449 - 수리공 항승 - 그리디 알고리즘 문제링크 : 물이 새지 않도록 테이프를 붙여서 물을 막아준다. 물을 막을때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다는 것은 결국 구멍 하나당 테이프 길이 1이 필요하다는 말이다. 테이프의 위치를 나타내는 변수를 만들어 테이프의 위치로 구멍이 커버 가능하면 그 구멍은 그냥 패스하고, 그렇지 않고 새로운 테이프가 필요하거나 좌표를 이동하여야하면 그때의 따라 조건을 바꿔준다. tape라는... 백준실버부수기백준실버부수기 백준 9431 파도반수열 문제링크 : 규칙을 찾아야한다. 딱봐도 무슨 규칙이 있을것처럼 보이는 문제이기 때문이다. 예전에 고등학교 때 점화식을 풀던 모든 기억들을 되살려 풀면 된다. 수열은 다음과 같이 진행된다 1 1 1 2 2 3 4 5 7 9 12 16 21 이를 보면 5항씩 더해지는것이 반복된다. 3 = 2+1, 4 = 3+1, 5 = 4+1, 7 = 5+2, 9 = 7+2 이런 규칙을 알면 다음과 같은 식을 ... 백준실버부수기백준실버부수기 백준 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일때와... 백준실버부수기백준실버부수기 1743 - 음식물피하기 - DFS 문제링크 : 가장 큰 음식물의 크기를 구하라는 것은 사실상 쓰래기들의 영역중 가장 큰 영역을 구하라는 문제이다. 따라서 기존에 풀었던 문제들과 똑같이 DFS로 해결하면 된다. 영역의 크기를 구할때는 위에서 했듯이 ret += DFS(rr,cc) 이런식으로 모든 값들을 더해주면된다.... 백준실버부수기백준실버부수기 2776 - 암기왕 - 이분 탐색 문제링크 : 점수가 있나 없나 확인할때 이분 탐색을 사용해야한다. 범위는 정수라고 하기에 범위는 음수 양수 다 가능하다. 간만에 쉬운 문제였다. 이제 이분탐색을 잘 할수있을것 같다.... 백준실버부수기백준실버부수기
13305 - 주유소 - 그리디알고리즘 문제링크 : 제일 왼쪽도시에서 제일 오른쪽 도시로 이동하는동안 최소의 비용을 계산해야한다. 즉 기름을 사는데 사용할 돈의 최소값이다. 다음 도시가 현재 도시보다 용량이 작은 기름이 나올때까지 계속 다음 도시를 확인한다. 만약 더 작은 기름이 나온다면 이전까지 지나왔던 도로의 길 * 기름값 만큼 더해주며 이 과정을 반복하며 목적지까지 간다. long long을 써주는 것을 주의해야한다. 항상 ... 백준실버부수기백준실버부수기 백준 11057 오르막 수 문제링크 : 숫자를 0으로 시작할 수 있다는것이 매우 큰 힌트이다. 인접한 수가 크거나 같아야한다. dp[현재 수][남은 수의 개수]로 메모이제이션을 하여 해결한다. dp[현재 수][남은 수의 개수]로 알고리즘을 짠 아이디어가 좋았다고 생각한다. 문제를 풀때 항상 base case를 잊지않고 잘 생각해서 짜야한다.... 백준실버부수기백준실버부수기 백준 9465 스티커 문제링크 : 스티커와 인접한 부분은 사용할 수 없다. 그렇다고하여 항상 엇갈리게 뽑는 것이 아니다. 첫번째줄, 두번째줄, 아무것도 선택안되었을 때 3가지 케이스가 있고, 그 케이스에 따라 메모이제이션으르 해야한다. 그 값들 중 최대 값을 찾으면 된다. 이 문제에서 중요한 아이디어는 1번째, 2번째 줄 모두를 선택하지 않고 넘어갈 경우이다. 이러한 경우도 잊지않고 넣어주어야한다.... 백준실버부수기백준실버부수기 백준 11052 카드구매하기 문제링크 : 최대한 돈을 많이 사용하도록 풀어야한다. 작은 값부터 순차대로 모든 경우의 수를 확인하여 문제를 해결한다. 단 이때 메모이제이션을 하여 시간복잡도를 낮춘다. 내가 해결하지 못하여 다른사람의 블로그를 참고하였다. 하지만 핵심은 하나다. 이 문제에서 N개의 카드가 주어지는데, 이러한 카드가 주어질 때 이 카드들 만으로 계산을 순차적으로 하면 된다. 이러한 테크닉을 배우게 되었다. d... 백준실버부수기백준실버부수기 5567 - 결혼식 - BFS 문제링크 : 상근이의 친구와 친구의 친구까지만 초대하는것이다. 문제를 제대로 읽어야한다. BFS로 문제를 해결하되, 상근이부터 시작하여 친구의 친구들 까지만 찾는 것이다. 몇번을 거쳐서 만들어 진건지에 대한 value값을 넣어 해결해준다. 중복인 친구를 넣지 않기위해 체크배열을 만들어준다. 간단하게 pair 자료구조를 사용하여 해결하였다. 이 문제를 풀때 친구의 친구까지만 찾는다는 것을 제대... 백준실버부수기백준실버부수기 1012 - 유기농배추 - DFS 문제링크 : 이것도 이전에 풀었던 단지구하기와 같은 문제이다. 이름만 영토에서 지렁이로 바뀐 것 뿐이다. 마찬가지로 dx, dy를 만들어서 이동한다. M, N 은 50이하이므로 시간과 공간은 충분하다. 문제는 쉬웠으나 또 문제를 제대로 읽지 않았다. 나는 항상 배열을 1부터 시작하는데 이 문제에서는 0에서부터 input이 들어오므로 +1 을 해주는것을 잊지말아야한다. 또한 문제에서 x가 먼저... 백준실버부수기백준실버부수기 백준 2193 이친수 문제링크 : 이친수는 반드시 1로 시작하고, 1이 두번 연속으로 나타나지 않아야 하는 제한조건을 가지고 있다. 1로 시작하기 때문에 2번째 숫자는 반드시 0이다. 5자리 숫자 10000 은 100 과 1000의 합으로 구성됨을 그림을 그리면서 파악한다. 오버플로우가 날 수 있음을 항상 잊으면 안된다. pinaryNum(n+1) = pinaryNum(n) + pinaryNum(n-1) 규칙만 ... 백준실버부수기백준실버부수기 1449 - 수리공 항승 - 그리디 알고리즘 문제링크 : 물이 새지 않도록 테이프를 붙여서 물을 막아준다. 물을 막을때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다는 것은 결국 구멍 하나당 테이프 길이 1이 필요하다는 말이다. 테이프의 위치를 나타내는 변수를 만들어 테이프의 위치로 구멍이 커버 가능하면 그 구멍은 그냥 패스하고, 그렇지 않고 새로운 테이프가 필요하거나 좌표를 이동하여야하면 그때의 따라 조건을 바꿔준다. tape라는... 백준실버부수기백준실버부수기 백준 9431 파도반수열 문제링크 : 규칙을 찾아야한다. 딱봐도 무슨 규칙이 있을것처럼 보이는 문제이기 때문이다. 예전에 고등학교 때 점화식을 풀던 모든 기억들을 되살려 풀면 된다. 수열은 다음과 같이 진행된다 1 1 1 2 2 3 4 5 7 9 12 16 21 이를 보면 5항씩 더해지는것이 반복된다. 3 = 2+1, 4 = 3+1, 5 = 4+1, 7 = 5+2, 9 = 7+2 이런 규칙을 알면 다음과 같은 식을 ... 백준실버부수기백준실버부수기 백준 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일때와... 백준실버부수기백준실버부수기 1743 - 음식물피하기 - DFS 문제링크 : 가장 큰 음식물의 크기를 구하라는 것은 사실상 쓰래기들의 영역중 가장 큰 영역을 구하라는 문제이다. 따라서 기존에 풀었던 문제들과 똑같이 DFS로 해결하면 된다. 영역의 크기를 구할때는 위에서 했듯이 ret += DFS(rr,cc) 이런식으로 모든 값들을 더해주면된다.... 백준실버부수기백준실버부수기 2776 - 암기왕 - 이분 탐색 문제링크 : 점수가 있나 없나 확인할때 이분 탐색을 사용해야한다. 범위는 정수라고 하기에 범위는 음수 양수 다 가능하다. 간만에 쉬운 문제였다. 이제 이분탐색을 잘 할수있을것 같다.... 백준실버부수기백준실버부수기