728x90 Algorithm 썸네일형 리스트형 [백준알고리즘] 2294번: 동전 2 -Python [백준알고리즘] 2294번: 동전 2 -Python https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 동적 계획법을 사용해서 문제를 풀었다. 주어진 코인으로 1부터 k까지 차례대로 만들 때 사용하는 코인의 최소 개수를 저장하도록 했다. 각 금액을 만들 때 모든 코인들을 사용해본다. 현재 만들려는 금액이 t라면, 각 코인을 사용해서 t가 되었다고 생각을 하면 된다. 주어진 예제입력을 예시로 들어보겠다... 더보기 [백준알고리즘] 2163번: 초콜릿 자르기 -Python [백준알고리즘] 2163번: 초콜릿 자르기 -Python https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 처음에는 Dynamic Programming 방식으로 풀었다. NxM크기의 .. 더보기 [백준알고리즘] 3109번: 빵집 -Python [백준알고리즘] 3109번: 빵집 -Python https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 문제에 대한 접근은 어렵지 않은 것 같다. visit 리스트를 만들고 오른쪽 위부터 우선적으.. 더보기 [백준알고리즘] 2023번: 신기한 소수 -Python [백준알고리즘] 2023번: 신기한 소수 -Python https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 www.acmicpc.net 처음에는 에라토스테네스의 체를 이용해서 10**8만큼의 리스트를 만들었었다. 만.. 더보기 [백준알고리즘] 1799번: 비숍 -Python [백준알고리즘] 1799번: 비숍 -Python https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다. www.acmicpc.net 이 한문제를 푸는데 굉장히 오래 걸렸다. 처음에는 N-Queen 문제랑 비슷하다고 생각하며 너무 쉽게 생각했다. N-Queen 문제와 비슷하기는 하지만 N-Queen은 한 행과 한 열에 하나씩 배치하기 때문에 배치할 공간이 훨씬 줄어들기 때문.. 더보기 [백준알고리즘] 1339번: 단어 수학 -Python [백준알고리즘] 1339번: 단어 수학 -Python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 처음에는 DFS처럼 거의 완전탐색처럼 푸는 것 같다. 알고리즘 분류만 봐도 백트래킹으로 나와있다. 하지만 백트래킹으로 풀었을 때, 시간 초과가 발생했으며 시간을 줄이는 방법이 마땅치 않다. 실제로 다른 분들의 코드를 봐도 백트래킹처럼 푼 풀이는 보지 못했.. 더보기 [백준알고리즘] 2661번: 좋은수열 -Python [백준알고리즘] 2661번: 좋은수열 -Python https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 한 번에 통과가 안돼서 오히려 당황하는 바람에 시간이 좀 걸리게 되었다. 1, 2, 3을 순서대로 대입해주는 방식으로 문제를 풀면 만들어낸 수열의 길이가 n일 경우 바로 출력하는 것이 가장 수가 적은 상태가 된다. 그래서 바로 출력해주고 끝내면 되는데, 이 부분을 다 구해보면서 비교해서 시간초과가 나왔었다. 필요 없는 코드들을 다 지워버리니 바로 통과했다. .. 더보기 [백준알고리즘] 15686번: 치킨 배달 -Python [백준알고리즘] 15686번: 치킨 배달 -Python https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 브루트 포스 방식으로 문제를 풀 수 있었다. 모든 집에서 최대 m개의 치킨집을.. 더보기 이전 1 ··· 10 11 12 13 14 15 16 ··· 27 다음